Fibonacci nim estrategias ganadoras en diferentes situaciones

Reglas de fibonacci nim:

Fibonacci nim es jugado por dos jugadores, que se alternan quitando monedas u otras fichas de una pila. En el primer movimiento, un jugador no puede tomar todas las monedas, y en cada movimiento posterior, la cantidad de monedas eliminadas puede ser cualquier número que sea como máximo el doble del movimiento anterior. De acuerdo con la convención de juego normal, el jugador que toma la última moneda gana.

Y tengo que mostrar estas 4 cosas:

1) probar que si al comienzo del juego sobre la mesa hay 2 F norte monedas, entonces el movimiento ganador es tomar F norte − 2 monedas

2) designar jugada ganadora si al comienzo del juego en la mesa es F norte − 1 monedas

3) probar que si al comienzo del juego sobre la mesa hay F norte 2 monedas, luego tomar 1 moneda es un movimiento ganador

4) designar jugada ganadora si al comienzo del juego en la mesa es 4 F norte monedas

y tenemos eso F 0 = 1 , F 1 = 2 y luego F norte = F norte − 2 + F norte − 1

Sé cuál es la estrategia ganadora en el juego Fibonacci Nim, pero no sé cómo encontrar la representación Zeckendorf de los números en el punto. 1 − 4 :(

¿Estás familiarizado con la representación de Zeckendorf de los números enteros positivos y su relación con el nim de Fibonacci?
Sé cuál es la estrategia ganadora, pero cómo encontrar la distribución de Zeckendorf, por ejemplo, el número 2 F norte
Bueno. Todavía no he tenido la oportunidad de pensar seriamente en ello, pero quería saber con cuántos antecedentes teníamos para trabajar.
Si conoce la estrategia ganadora y solo quiere encontrar la representación Zeckendorf de los números en sus preguntas, ¿por qué no pidió eso? Podrías haber puesto información adicional sobre por qué quieres encontrar la representación Z. agregando este juego como fondo. O si no está seguro de que encontrar la representación Z. lo llevará a la respuesta a su pregunta original, al menos agregue en el cuerpo de la pregunta lo que sabe al respecto y por qué cree que podría ser útil para esta pregunta.
Lo siento, edité la pregunta.

Respuestas (1)

Para ( 1 ) tenga en cuenta que 2 F norte = F norte + ( F norte − 1 + F norte − 2 ) = ( F norte + 1 − F norte − 1 ) + ( F norte − 1 + F norte − 2 ) .

Para ( 2 ) probar por inducción que

F norte − 1 = F norte − 1 + F norte − 3 + F norte − 5 + … + F metro = ∑ k = 0 ⌊ norte / 2 ⌋ − 1 F norte − ( 2 k + 1 ) ,

dónde

metro = { 1 , si  norte  incluso 2 , si  norte  es impar .

Para ( 3 ) Observo las siguientes representaciones de Zeckendorf:

norte F norte 2 Zeckendorf 1 1 1 2 1 1 3 4 101 4 9 10001 5 25 1000101 6 64 100010001 7 169 10001000101 8 441 1000100010001 9 1156 100010001000101

Esto muestra un patrón que sugiere que F norte + 2 2 = F norte 2 + F 2 norte + 2 , y esto, de ser cierto, permitiría una prueba inductiva fácil de la afirmación. De hecho, esta es una identidad antigua debido a Lucas; hay una prueba combinatoria fácil en este PDF (Teorema 4 ).

Para ( 4 ) , experimentación similar con las representaciones de Zeckendorf de los números 4 F norte sugerirá una identidad para 4 F norte que produce una estrategia para norte ≥ 3 .

Gracias mañana comprobaré si entiendo todo y si tengo algún problema escribo :)
@TuptuśTupta: De nada.
para ser honesto, no entiendo cómo encontrar un patrón de esta tabla. Sé cómo se creó la tabla, pero si no escribieras cuál es la relación entre los números, no lo habría descubierto por mí mismo. ¿Podrías explicar cómo, paso a paso, se te ocurrió un ejemplo?
@TuptuśTupta: Para ( 3 ) , o por ( 4 ) ?
@TuptuśTupta: Para ( 3 ) Noté que la representación de Zeckendorf de F norte + 2 2 solo agrega un prefijo 1000 a la representación de Zeckendorf de F norte 2 . Esto significa que F norte + 2 2 = F norte 2 + F metro para algunos metro . Mirando la mesa, veo que metro aumenta en 2 cuando norte aumenta en 1 , de modo que metro = 2 norte + k para algunos k , y después de eso solo era cuestión de encontrar k inspeccionando la mesa.
bueno entiendo pero F norte + 2 2 = F norte 2 + F 2 norte + 2 ¿No es la distribución de Zeckendorf del número F norte 2
@TuptuśTupta: Mire la tabla: esa identidad permite probar por inducción que si el Zeck. reps. de F norte 2 termina en 1 , también lo hace el Zeck. reps. de F norte + 2 2 , y eso le permite concluir a partir de la estrategia ganadora conocida que debe tomar una moneda.
yo apunto 4 usando la propiedad F norte = F norte + 1 − F norte − 1 y obtengo 4 F norte = F norte − 2 + F norte + F norte + 2 . ¿Hay una manera más fácil de resolver la tarea 3? ¿Uno que nos daría una distribución de Zeckendorf con la palabra más pequeña F_1 o F_2? O podrías probar que F norte + 2 2 = F norte 2 + F 2 norte + 2
@TuptuśTupta: Sí, esa es la misma solución que obtuve para ( 4 ) . En ( 3 ) no necesita la distribución real: solo necesita probar que Zeck. reps. de cada F norte 2 termina en 1 . Puede haber mejores formas, pero la más fácil que encontré fue usar la identidad F norte + 2 2 = F norte 2 + F 2 norte + 2 demostrarlo por inducción. Una prueba de esa identidad está en el PDF al que vinculé en mi respuesta.
entonces si tengo F norte + 2 2 = F norte 2 + F 2 norte + 2 cómo mostrar ahora que cada F norte 2 tener número 1 en la distribución zeckendorf?
@Piszczu: El Zeck. repeticiones de F 1 2 y F 2 2 terminar en 1 . Muestra esa F 2 norte + 2 es sustancialmente mayor que F norte 2 — la tabla sugiere que si F k es el mayor número de Fibonacci en el Zeck. reps. de F norte 2 , entonces 2 norte + 2 = k + 4 — y será inmediato que el Zeck. reps. de F norte + 2 2 simplemente agrega un 1 y algo 0 s a la izquierda del Zeck. reps. de F norte 2 . Por lo tanto, si el Zeck. reps. de F norte 2 termina en 1 , también el de F norte + 1 2 .
ok pero como mostrar eso 2 norte + 2 = k + 4 ? Lo veo desde la tabla, pero ¿cómo probarlo?
@Piszczu: Todo lo que realmente necesitas es eso F 2 norte + 2 < F norte + 2 2 < F 2 norte + 3 ; un enfoque podría ser utilizar el hecho de que F norte es el entero más cercano φ norte 5 .
Fibonacci nim estrategias ganadoras en diferentes situaciones
RespuestasAquíPolítica de privacidad1y, 0v