Cómo resolver este problema de algoritmo de juego

Si n es un número de Fibonacci, no hay estrategia ganadora. Si no, hay estrategia ganadora.

Lema 1: Teorema de Zickendorf Cualquier número se puede expresar como la suma de múltiples números discontinuos de Fibonacci. Para comprobarlo, consulte Wikipedia "Teorema de Zickendorf"

Lema 2: La secuencia de Fibonacci satisface f. (k 1)lt; 2×f(k)

El método de inducción matemática demuestra:

i=1 Si no se satisface el significado de la pregunta, no la considere.

Cuando i=2, n=2 obviamente el primero en moverse perderá

Cuando i=3, n=3 obviamente el primero en moverse perderá

i =k≥3

Suponiendo que es cierto cuando i=k,

cuando i=k 1, f(i)=f(k) f(k?1), es decir, si la segunda mano puede obtener la última de f(k?1), la proposición original está demostrada, ahora la prueba es la siguiente:

Si la primera mano toma x≥13f( k?1), el segundero puede tomar todo el resto y=f (k?1)?x?

And y=f(k?1)?xlt; ; 12f(k), es decir, el primer motor no puede tomar todos los f restantes a la vez (k)

Si se toma x≤13f(k?1) primero, debe haber f(k? 3)gt; 13f(k?1), y f(k-3)- se pueden tomar con el segundero x, luego el problema vuelve al paso anterior.

Entonces se prueba la proposición original.

Por el contrario, si n no es un número de Fibonacci, entonces toma x primero, de modo que n-x sea un número de Fibonacci, y ganarás.