domingo, 6 de junio de 2010

Palabras binarias

Sea 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:

José Luis Miranda Olvera dijo...

A que te refieres con palabras binarias?

IrvinG dijo...

Se les dice palabras binarias porque están formadas sólo con 0`s y 1`s.

IrvinG dijo...

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.

IrvinG dijo...

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.

Leo dijo...

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?

DANIELIMO dijo...

ya me salio, con recursion e induccion, pero no me gusto mi solución, ahoita la escribo

DANIELIMO dijo...

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}

Georges dijo...

Tengo una solucion usando unas recursiones, pero estoy buscando una solucion por biyección. Si me sale al rato la escribo.

Georges dijo...
Este comentario ha sido eliminado por el autor.
Leo dijo...

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.

Leo dijo...

Bien Daniel! Si quieres una más bonita, puedes pensar en encontrar una biyección.

Georges dijo...

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