Juego Con 21 Plazas, Cómo Muchas Respuestas Posibles? La Función De La Construcción De

Question

Hemos jugado a este juego en nuestra clase de matemáticas, está bien, voy a explicar cómo se juega. Hay 21 plazas en una línea recta a través de, la primera persona de tonos de 2 plazas adyacentes. El siguiente jugador en 2 tonos más plazas adyacentes. Siguen tomando turnos hasta que no hay más plazas adyacentes a la sombra. El último jugador para jugar gana. Que la forma de jugar, pero la pregunta que nos dieron después de la era de cuántas posibles combinaciones de sombra y sin sombra plazas hay? Luego introduce lo que él llama "la función de la construcción", que es básicamente una forma más simple de problema y seguir sumando en él hasta que usted puede encontrar una función para ello. Yo realmente apreciaría cualquier ayuda, y espero que pueda aprender de esto!

Edit: supongo que se me olvidó incluir que para que una solución sea considerada una solución, tiene que ser un juego terminado, así que no hay dos adyacentes plazas se quedan sin sombrear.

Answer 1

Edit: a Continuación es la respuesta a la pregunta original, que desde entonces ha sido modificado.

Deje $a_n$ el número total de patrones de sombra y sin sombra plazas, donde el número total de plazas es de $n$.

Expresamos $a_{n+1}$ en términos de la anterior $a_k$.

Un patrón de longitud $n+1$ (i) termina con un sin sombrear de la plaza o (ii) termina con $2$ casillas sombreadas. Hay $a_n$ patrones de tipo (i), y $a_{n-1}$ patrones de tipo (ii). De ello se sigue que $$a_{n+1}=a_n+a_{n-1}.$$ Este es un muy famoso de la recurrencia, la de Fibonacci de la recurrencia.

Tenga en cuenta que$a_1=1$$a_2=2$. Así $a_3=3$, $a_4=5$, $a_5=8$, y así sucesivamente: obtenemos los números de Fibonacci. Para más detalles, consulte el [artículo de la Wikipedia.] (http://en.wikipedia.org/wiki/Fibonacci_number) incluso Hay una fórmula explícita para el número de patrones como una función de $n$.

Answer 2

Con el requisito de "el juego tiene que ser terminado sólo en caso de que no tenía sentido, así que no hay dos plazas adyacentes sin sombra" luego de un largo permita la secuencia termina

• con un permitida la secuencia seguida por un par de sombra o
• con un permitida la secuencia seguida por un par de sombra y sin sombra de la plaza

dando la recurrencia $$a_n=a_{n-2}+a_{n-3}$$

Ya que se comienza $1,1,2,\ldots$, este es el Padovan secuencia, offset

Answer 3

Desea que las posibilidades de tener adjunto plazas a la sombra, pero no adjunto no casillas sombreadas (posiciones finales del juego). Llame al número de posiciones finales, cuando hay $n$ plazas $e_n$. Claramente $e_1 = e_2 = 1$$e_3 = 2$.

Piensa cómo puedes hacer que una posición final $n$ de las plazas de los más pequeños. Si la última plaza está en la sombra, significa $n$ $n - 1$ están sombreadas, y antes de que llegue legal de la posición final para $n - 2$. Si el último no está a la sombra, a continuación, $n - 1$ $n - 2$ están sombreadas, y antes de que llegue legal de la posición final para $n - 3$. El ajuste de los índices por orden: $$ e_{n + 3} = e_{n + 1} + e_n \qquad e_1 = e_2 = 1, e_3 = 2 $$ Por lo tanto: $$ 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ... $$ En particular, $e_{21} = 256$.