Calculando el número de secuencias de azulejos

Question

Mi hija (de 12 años) vino a mí con el problema de abajo. Pude ayudarla hasta cierto punto pero no pude ver una solución apropiada para su edad. Es decir, podía imaginar soluciones que involucraran factores/combinaciones o escribir un programa de computadora. Sin embargo, ella está en séptimo curso en la escuela y no pude ver cómo resolverlo con ese nivel de conocimiento. Nos pusimos de acuerdo en una solución de fuerza bruta, pero no la completamos porque nos llevaría demasiado tiempo. Así que, ¿puede alguien resolver esto con un algoritmo simple y lógico usando conocimientos / técnicas con las que un estudiante que acaba de empezar el instituto estaría familiarizado?

Digamos que tienes un conjunto de azulejos negros (B) y blancos (W) - idénticos aparte del color. Dispones los azulejos en varias secuencias, por ejemplo, B, BW, WWBW, etc. Una secuencia se considera significativa si todas sus sub-secuencias de fichas blancas tienen la misma longitud. Por lo tanto, lo siguiente es significativo: WW, BBB, WWWWBB; mientras que las siguientes no lo son: W, BWWW, BWWBBBW. Nota: una secuencia de longitud cero parecería ser considerada pareja.

Había algunas preguntas simples que podíamos resolver, por ejemplo, cuántas secuencias significativas de longitud 1, 2, 3 y 4 hay. Enuméralas.

Pero la pregunta que nos dejó perplejos fue: ¿cuántas secuencias significativas de longitud 20 hay? No podíamos extrapolar fácilmente las preguntas anteriores.

PD: No estaba seguro de qué etiquetas usar. Por favor, actualice como considere oportuno.

Answer 1

Estoy seguro de que hay una respuesta mejor que la mía, pero la publicaré de todos modos.

Agrupa las fichas blancas en parejas de 2 - esto se hace porque sólo queremos secuencias pares de las fichas blancas. Ahora, para organizar 20 fichas, tenemos las siguientes maneras de elegir las fichas:

• 0 fichas blancas y 20 negras
• 1 par de baldosas blancas y 18 negras
• 2 pares de baldosas blancas y 16 negras ........ así sucesivamente hasta
• 10 pares de baldosas blancas y 0 negras

Consideremos el primer caso, cuando no hay baldosas blancas. Sólo hay una combinación posible. En el segundo caso, cuando hay 1 par de fichas blancas, tenemos 19 combinaciones posibles. Cuando tenemos 2 pares de fichas blancas, tenemos 153 combinaciones posibles... y así sucesivamente.

Sumando todos ellos obtendremos nuestra respuesta.

EDITAR:

Si tenemos $x$ artículos, de los cuales $m$ son de un mismo tipo y $n$ son de otro tipo, entonces el número total de formas de ordenarlos es: $$\frac{x!}{m!n!}$$ En nuestro caso, tenemos dos tipos de objetos, pares de baldosas blancas (que se consideran 1 objeto) y baldosas negras.

Así, en el tercer caso (dos pares de fichas blancas), tenemos un total de 18 objetos: 16 fichas negras y 2 pares de fichas blancas. Por lo tanto, la forma total o disponerlos es: $$\frac{18!}{16!2!}$$

Answer 2

Sea $a_n$ sea el número de secuencias significativas de longitud $n$ . Si cuentas con cuidado, verás que $a_1=1$ , $a_2=2$ , $a_3=3$ , $a_4=5$ , $a_5=8$ y $a_6=13$ . Es posible que usted (o ella) los reconozca como los Números de Fibonacci e incluso si no lo haces, puedes darte cuenta de que cada uno es la suma de los dos anteriores. Si extrapolas sobre esta base, puedes adivinar (tras un poco de aritmética) que $a_{20}=10946$ .

Por supuesto, cabe preguntarse si la extrapolación es legítima. Para comprobarlo, supongamos que $\sigma$ es una secuencia significativa de longitud $n$ donde $n\ge 3$ . Si $\sigma$ termina en B, la primera $n-1$ cartas de $\sigma$ son una secuencia significativa de longitud $n-1$ . Por el contrario, si se empieza con cualquier secuencia significativa de longitud $n-1$ añadiendo una B al final se obtiene una secuencia significativa de longitud $n$ . Así, hay $a_{n-1}$ secuencias significativas de longitud $n$ que terminan en B.

Si, por el contrario, $\sigma$ termina en W, entonces en realidad debe terminar en WW, y la primera $n-2$ cartas de $\sigma$ debe ser una secuencia significativa de longitud $n-2$ . Por el contrario, si se empieza con una secuencia significativa de longitud $n-2$ y añadir WW al final, se obtiene una secuencia significativa de longitud $n$ . Así, hay $a_{n-2}$ secuencias significativas de longitud $n$ que terminan en W.

Juntando las dos cosas, vemos que $a_n=a_{n-1}+a_{n-2}$ .