Sea [math]p>2 un número primo fijo. Dos jugadores [math]A y [math]B escriben, por turnos, una sucesión de números enteros de acuerdo con las siguientes reglas: [math]A elige un número [math]a_1 y lo escribe, luego [math]B elige un número [math]a_2 y lo escribe; a continuación, [math]A escribe el número [math]a_3=a_1+a_2; luego [math]B escribe el número [math]a_4=a_2+a_3, y así siguiendo, cada jugador en su turno escribe el número igual a la suma de los últimos dos números escritos, es decir, [math]a_{n+1}=a_{n-1}+a_n.
El juego termina en el paso [math]j, luego de que un jugador escribió [math]a_j, si existe un índice [math]i, con [math]2<i<j, tal que [math]a_i-a_j, es múltiplo de [math]p y además [math]a_{i-1}-a_{j-1} es también múltiplo de [math]p. Gana el jugador que escribió el último número.
Determinar cuál de los dos jugadores tiene estrategia ganadora.
Bueno, me di cuenta que la solución se puede simplificar por $100$ y de paso evitar algunos errores que tiene. Tomamos $a≡b \pmod p$, luego a todos los términos de la sucesión le podemos sacar factor común $a$ para obtener la sucesión de Fibonacci.
Además la condición de divisibilidad que nos da el problema equivale a que haya dos pares de números iguales $\pmod p$.
Como la sucesión es cíclica (con período par) $\pmod p$ siendo $p$ un primo impar, entonces siempre gana Beto. El único caso que analizamos aparte es cuando $p=2$ y si $a≡b≡0$ también gana Beto porque la sucesión sería $0,0,0$.
Gana $B$, así que en toda la solución vamos a suponer cosas sobre $b_1$ en base a que queremos que gane. Notemos que los primeros términos de la sucesión son
$$a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b, \dots$$
De donde esta claro que $a_n = f(n-1)b+f(n-2)a$ siendo $f(n)$ la sucesión de Fibonacci definida por $f(0) = 0, f(1) = 1, f(n) = f(n-1)+f(n-2) \Rightarrow 0, 1, 1, 2, 3, 5, 8, 13, \dots$. Luego, las congruencias $\pmod p$ quedan:
$$a_i-a_j = f(i-1)b+f(i-2)a-f(j-1)b-f(j-2)a \equiv 0 \pmod p (1)$$
$$a_{i-1}-a_{j-1} = f(i-2)b+f(i-3)a-f(j-2)b-f(j-3)a \equiv 0 \pmod p (2)$$
Notemos que si $a \equiv 0 \pmod p$ entonces $B$ elije $b \equiv 0\pmod p$ y la sucesión $\pmod p$ nos quedaría $0, 0, 0, \dots$. Dado que $2<i<j$ entonces el primer $j$ que podemos tomar es $j = 4$ lo cual implica que gana B, pues B siempre tiene las jugadas pares y Ana las impares. A partir de ahora, $a, b \not\equiv 0 \pmod p$.
Supongamos que $f(j-1)-f(i-1) \equiv 0 \pmod p$, luego las ecuaciones nos quedarían.
De donde no importa que valor tome $a$ o $b$, el resultado depende pura y exclusivamente de la sucesión de Fibonacci. Luego, si $f(j-1)-f(i-1) \not\equiv 0 \pmod p$ entonces tiene un inverso modular $\pmod p$. Para achicar cuentas, digamos $f(j-1)-f(i-1) = x, f(i-2)-f(j-2) = y$. Luego, las ecuaciones quedarian:
$$ay \equiv bx \pmod p \iff a \equiv bxy^{-1} \pmod p$$
$$(b-a)y \equiv ax \pmod p$$
Un dato curioso que me di cuenta, nada que ver con olimpíadas, pero si ponemos los valores del sistema en una matriz
$$A = \left(
\begin{matrix}
a & b \\
b-a & a \\
\end{matrix}
\right)$$
E igualamos su determinante a cero:
$$\det{A} = a^2-b(b-a) = 0 \iff a^2+ab-b^2 = 0$$
Entonces las soluciones a esa cuadrática en $a$ son $a = b(\frac{-1\pm\sqrt{5}}{2})$, casualidad que aparezca $\phi$ tan mágicamente.
$$\Rightarrow (b-bxy^{-1})y \equiv bxy^{-1}x \pmod p \iff b(1-xy^{-1})y \equiv bx^2y^{-1} \pmod p \iff (1-xy^{-1})y \equiv x^2y^{-1} \pmod p$$
De donde, otra vez, no importa que valores de $a$ o $b$ se elijan (siendo los mismos no nulos), entonces el resultado depende solo de la sucesión de Fibonacci.
A checkear esto de arriba porque no me cierra del todo. Pero de igual manera, si tomas $a \equiv b \pmod p$ entonces podemos sacar factor común $a$ de toda la sucesión y queda lo mismo que se sigue abajo. Debería de verlo más a detalle.
Entonces, podemos asumir sin perdida de generalidad que la sucesión empieza con $a = 1, b = 1 \Rightarrow 1, 1, 2, 3, 5, 8, 13, \dots$, es decir la misma sucesión de Fibonacci (pero ignoramos el cero inicial). Es sabido que la sucesión de Fibonacci es cíclica $\pmod p$ y su periodo nos lo da la función $\pi(p)$, siendo esta la función de Pisano, además es conocido que para todo primo impar, $\pi(p)$ es par (si, lo googlee). Ahora notemos que si analizamos la sucesión $\pmod p$, entonces lo que nos interesa es que haya dos pares de números consecutivos iguales, pues eso es lo que nos dice la condición $a_i-a_j \equiv 0 \pmod p$ y $a_{i-1} - a_{j-1} \equiv 0 \pmod p$. Pero en caso de que haya dos pares de números consecutivos iguales, entonces es porque la sucesión se empezó a repetir (pues $f(n) = f(n-1)+f(n-2)$ es decir depende de los dos términos anteriores), de donde sabemos que nuestra sucesión quedaría:
Además, sabemos que el primero en repetirse es $1, 1$, pues en caso contrario $1, 1$ no volvería a aparecer, contradiciendo que la sucesión es periódica. Por consiguiente, sabemos que el primer $j$ que cumple seria el $1$ (el que tiene abajo el $2k+2)$ y su correspondiente $i$ seria el segundo termino de la sucesión. Dado que $j$ esta en una posición par, entonces sabemos que gana B, y entonces concluimos que B es el que tiene la estrategia ganadora.
Resumiendo, si $A$ elije un múltiplo de $p$, $B$ elije otro múltiplo de $p$ y gana. En caso de que $A$ no elija un múltiplo de $p$, $B$ tampoco elije un múltiplo de $p$ y también gana.
