C={1,2,3....,n}
¿De cuantas formas puede elegir un subconjunto S de C tal que en S no haya dos elementos que son numeros consecutivos?
(para n=3, son 5, {1}{2}{3}{1,3}{vacio} )
domingo, 16 de enero de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
7 comentarios:
es bastante obvio el problema, no? Si c_n es el numero que queremos, entonces c_{n}=c_{n-2}+c_{n-1}, ya que si el n esta en S entonces n-1 no esta y ahora se elegirian S' en {1,2,...,n-2} con esa propiedad y S=S'U{n}. Si n no esta en S entonces hay c_{n-1}. c_1=2,c_2=3 Con f_0=0,f_1=1. tenemos que c_n=f_{n+2}
Sólo es necesario analizar los primeros casos.
Sea f(n) el numero de subconjuntos que cumplen para {1,2,...,n}
Observmos que f(0)=1. f(1)=2
Ahora, demostraré que para n, tenemos que f(n) = f(n-2)+f(n-1).
Vemos que la hipótesis es cierta para f(2).
Suponemos que es una hipótesis cierta hasta cierto k-1. Entonces, pd que f(k)=f(k-2)+f(k-1), lo cual lo analizamos de la siguiente forma. f(k-2) cuenta la cantidad de subconjuntos que contienen a k, ya que esta es la cantidad de subconjuntos que no contienen a k-1, por lo cual es posible tomar al elemento k. Vemos que f(k-1) cuenta todos los casos en que no consideramos a k. Entones f(k-2)+f(k-1) cuenta cada subconjunto que contiene a k y cada subconjunto que no contiene a k y sin repetición. Ahora lo relacionamos con la sucesión de fibonacci y vemos que f(n)=fibonacci(n+1)
Si n esta en el subconjunto, entonces la cantidad de subconjuntos posibles es la que se pueda formar con los elementos del 1 al n-2, ya que el n-1 no puede estar es ente subconjunto. Si n no esta en el subconjunto, entonces los subconjuntos que se pueden formar son los que se formen con los elementos del 1 al n-1. ya que estos dos casos son ajenos entonces no hay repeticiones y se consideraron todos los subconjuntos, entonces la cantidad de subconjuntos de Cn es Cn-1 + Cn-2. Ya que esta cantidad es 2 para C1 y 3 para C2, entonces considerando fibonacci de la sig forma F1=1, F2=1, Fn=Fn-1 + Fn-2 para n>=3. Entonces la cantidad para Cn es Fn+2
fibonacci n+2
bno, chance esta muy obvio, pero esta interesante, y no me lo sabia, y puede que les sirva alos demas
Hemos visto problemas muy parecidos no? Simplemente es ir sumando los dos casos anteriores, por ejemplo si buscamos c(n) sabríamos que c(n)=c(n-1) + c(n-2) ya que en todos los diferentes conjuntos que tiene c(n-2) contabilizados, metemos al n y sigue cumpliendo, mientras que si no está n, hay c(n-1) y entonces se forma recursivamente.
Sale que c(n)=f_(n+2) siendo f la suceción de fibonacci si es que f_0=0 y f_1=1
jajaja conocidísimo! ya lo habíamos visto en Morelos pero creo que con n=10 ó algo asi
Publicar un comentario