la cantidad de palabras binarias de n dígitos tales que no tengan tres términos consecutivos 0, 1, 0 en ese orden.Sea
la cantidad de palabras binarias de n dígitos tales que no tengan cuatro términos consecutivos iguales a 1,1,0,0 ó 0,0,1,1, en ese orden.Demuestra que
para toda n.
12 comentarios:
A que te refieres con palabras binarias?
Se les dice palabras binarias porque están formadas sólo con 0`s y 1`s.
Bueno, pues creo que ya tengo este problema. Haciendo algunas recursiones llegué a que:
a_{n+1}=a_{n}+a_{n-1}+a_{n-3}
b_{n+1}=b_{n}+b_{n-1}+b_{n-3}
Cumplen las dos sucesiones la misma recursión. Para mostrar lo que pide el problema sólo tenemos que checar a que la relación que queremos se cumpla para valores de n pequeños, al menos hasta n=3. Para concluir usamos inducción.
Es fácil ver que
a_{1}=b_{1}=2
a_{2}=b_{2}=4
a_{3}=7, b_{3}=8
a_{4}=13, b_{4}=14
Con estos valores podemos hacer la base de inducción. Ahora el paso inductivo es fácil con ayuda de la recursión:
b_{n+1}=b_{n}+b_{n-1}+b_{n-3}
=2[a_{n-1}+a_{n-2}+a_{n-4}]=2a_{n}
Al rato pongo en un nuevo post cómo llegué a las recursiones.
Sí, eso que dice Irving son las palabras binarias. Bien Irving! Luego nos cuentas tu recursión. ¿Alguien se apunta para encontrar una solución por biyección?
ya me salio, con recursion e induccion, pero no me gusto mi solución, ahoita la escribo
Sea A_{n} el conjunto de palabras binarias de n dígitos tales que no tengan tres términos consecutivos 0, 1, 0 en ese orden.
Sea B_{n} el conjunto de palabras binarias de n dígitos tales que no tengan cuatro términos consecutivos iguales a 1,1,0,0 ó 0,0,1,1, en ese orden.
Sean X_{n},Y_{n},Z_{n} la cantidad de palabras en A_{n} tal que empiezan con 10,11,0 respect.
Notamos que
a_{n}=X_{n}+Y_{n}+Z_{n}
X_{n+1}=Z_{n}
Y_{n+1}=X_{n}+Y_{n}
Z_{n+1}=Y_{n}+Z_{n}
Sean P_{n},Q_{n},R_{n} la cantidad de palabras en B_{n} tal que empiezan con 00,011,010 respect.
que por simetria tambien es la cantidad de palabras que empiezan con 11,100,101 respect.
Notamos que
b_{n}=2[P_{n}+Q_{n}+R_{n}]
P_{n+1}=R_{n}
Q_{n+1}=P_{n}+Q_{n}
R_{n+1}=Q_{n}+R_{n}
Vemos que
P_{4}=X_{3}=2
Q_{4}=Y_{3}=2
R_{4}=Z_{3}=4
y usando como base y viendo que las recursiones son iguales es facil ver por inducción que
P_{n+1}=X_{n}
Q_{n+1}=Y_{n}
R_{n+1}=Z_{n}
que nos lleva a 2(a_{n})=b_{n+1}
Tengo una solucion usando unas recursiones, pero estoy buscando una solucion por biyección. Si me sale al rato la escribo.
Si tienes una palabra binaria de longitud, ¿cómo puedes obtener una de longitud n+1? Hay varias formas, enlisten todas las que se les ocurran.
Bien Daniel! Si quieres una más bonita, puedes pensar en encontrar una biyección.
Pero para el problema no serviria mas poner, para cada palabra binaria de longitud n encontrar dos de n+1?
Que puede ser, poner 0 al principio y luego 1. ( o en cualquier lugar) O siempre agregar 0 al principio, pero poner esa palabra y la que se forma invirtiendo los dígitos.
O para encontrar solo una palabra de longitud n+1 partiendo de una de n, se puede contar si hay un número par de 0 se pone un 0 al final, y si hay un número impar se pone un 1.
No se... se me ocurrieron varias cosas asi, pero no cheque bien si servian.. voy a intentarlo a ver si funcionan.
Publicar un comentario