domingo, 16 de enero de 2011

Problema

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} )

7 comentarios:

Diego627 dijo...

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}

Manuel Alejandro dijo...

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)

angel95 dijo...

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

Flavio dijo...

fibonacci n+2

DANIELIMO dijo...

bno, chance esta muy obvio, pero esta interesante, y no me lo sabia, y puede que les sirva alos demas

Jorge 'Chuck' dijo...

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

Georges dijo...

jajaja conocidísimo! ya lo habíamos visto en Morelos pero creo que con n=10 ó algo asi

Publicar un comentario