Latest Posts:

11 de agosto de 2015

Cinco problemas equivalentes al de Fibonacci

Voy a plantear en este post cinco problemas de combinatoria que son equivalentes al problema de los conejos de Fibonacci, en el sentido de que dan lugar a la misma sucesión (y a la misma recurrencia). La solución de cada uno de ellos se detiene en el modelo, es decir, en el razonamiento por recurrencia que conduce a plantearlo. 

1. Subconjuntos sin consecutivos

¿De cuántas formas se puede elegir un subconjunto de {1,2,,n} de manera que no contenga números consecutivos?
Solución
Sea un el número de subconjuntos de {1,2,.n} sin números consecutivos. Cada subconjunto aceptable según la restricción, ya sea que contiene el 1 o bien no lo contiene.

Si contiene el 1 entonces no puede contener el 2 y se ve que el número de subconjuntos que contienen el 1 es un2 --pues es el número de subconjuntos de {3,4,,n}.

Por otro lado, si el subconjunto no contiene el 1, entonces el número de subconjuntos de esta clase son un1 --dado que es el número de subconjuntos de {2,3,,n}.

En resumen, un=un1+un2. (Claramente, u1=1,u2=2 --se deja como ejercicio su justificación.)

2. n-Cadenas binarias con dos ceros consecutivos

¿De cuántas formas se puede construir una n-cadena de ceros y unos con dos ceros consecutivos?
Solución
Sea un el número de cadenas binarias de longitud n con dos ceros
consecutivos. Claramente, una cadena de longitud 1 no puede tener dos ceros consecutivos, y solamente hay una de longitud dos con dos ceros consecutivos. Es decir, u1=0,u2=1.

Consideremos ahora el caso general. Cada cadena de longitud n con dos ceros consecutivos es de una de tres clases: empieza con 00 o con 01 o con 1.

Si empieza con 00, el resto de la cadena es una cadena de longitud n2 sin restricción.

Por otro lado, si empieza con 01, el resto de la cadena es una cadena de longitud n2 con dos ceros consecutivos.

Finalmente, si empieza con 1, el resto de la cadena es una cadena de longitud n1 con dos ceros consecutivos.

En resumen, el modelo recursivo para este problema es:

un=2n2+un2+un1

con u1=0,u2=1


3. Sus dígitos son 1 y/o 2 y suman n

¿Cuántos números con 1 y 2 como dígitos son tales que éstos suman n? Ejemplo: 111, 12, 21 son los tres números que cumplen para n=3.
Solución
Sea un el número de números que cumplen para n. Claramente, u1=1,u2=2. En el caso de n mayor que 2, se puede razonar recursivamente como sigue:
Los números que cumplen se pueden clasificar en dos clases excluyentes y exhaustivas. Los que empiezan con 1 y los que empiezan con 2.
Si empiezan con 1, son un1 --pues el problema se reduce a contar los números con 1 y 2 como dígitos y tales que éstos suman n1.
Si empiezan con 2, son Un2 --siguiendo un razonamiento similar. Por tanto un=un1+un2.
Otra forma: Considerando el último dígito, éste puede ser 1 o bien 2. Los números que terminan en 2 son un2 y los que terminan en 1 son un2

4. n-Cadenas binarias sin unos consecutivos

¿De cuantas formas se puede formar una cadena de ceros y unos de longitud n sin unos consecutivos?
Solución
Los números ya sea que inician con cero o bien con uno. Los que empiezan con cero son un1 y los que empiezan con uno son un2 --porque en realidad deben empezar con 10. Por tanto, un=un1+un2.

5. Tiempo de espera hasta dos águilas consecutivas

En una secuencia de n volados ¿cuántos resultados no tienen dos águilas consecutivas, excepto al final?
Solución
Sea un el número buscado. Los resultados, ya sea inician con águila (A) o bien con sello (S). Si inician con águila son un2; si con sello, son un1. Por tanto, un=un1+un2


Tomado de:

Mate Mat

No hay comentarios.:

Publicar un comentario