Question

Alice y Bob juegan al siguiente juego. Ante ellos hay una pila de $n$ fichas. Los jugadores se turnan y Alice va primero. En cada turno, el jugador retira $1$ ficha o $4$ fichas de la pila. El jugador que retira la última ficha gana. Halla la cantidad de enteros positivos $n$ menores o iguales que $2024$ tales que existe una estrategia que garantiza que Bob gane, sin importar las jugadas de Alice.

Alice and Bob play the following game. A stack of $n$ tokens lies before them. The players take turns with Alice going first. On each turn, the player removes $1$ token or $4$ tokens from the stack. The player who removes the last token wins. Find the number of positive integers $n$ less than or equal to $2024$ such that there is a strategy that guarantees that Bob wins, regardless of Alice's moves.

Respuesta

Solución:

Llama a $n$ una posición perdedora si el jugador a punto de mover pierde con el mejor juego. Afirmamos que las posiciones perdedoras son exactamente $n \equiv 0$ o $2 \pmod 5.$ Desde tal $n,$ retirar $1$ o $4$ fichas deja $n \equiv 4, 1, 3 \pmod 5$ , nunca de nuevo $0$ o $2$ , mientras que desde cualquier $n \equiv 1, 3, 4 \pmod 5$ una jugada alcanza una posición $\equiv 0$ o $2 \pmod 5$ (retirando $1,$ $1,$ $4$ fichas respectivamente). Como $n = 0$ es una derrota para el jugador que debe mover, la inducción confirma el patrón.

Bob gana exactamente cuando $n$ es una posición perdedora para Alice. Entre $1 \le n \le 2024$ hay $404$ múltiplos de $5$ y $405$ valores $n \equiv 2 \pmod 5$ (desde $2$ hasta $2022$ ), para un total de $404 + 405 = 809.$

Call $n$ a losing position if the player about to move loses with best play. We claim the losing positions are exactly $n \equiv 0$ or $2 \pmod 5.$ From such an $n,$ removing $1$ or $4$ tokens leaves $n \equiv 4, 1, 3 \pmod 5$ — never again $0$ or $2$ — while from any $n \equiv 1, 3, 4 \pmod 5$ one move reaches a position $\equiv 0$ or $2 \pmod 5$ (remove $1,$ $1,$ $4$ tokens respectively). Since $n = 0$ is a loss for the player to move, induction confirms the pattern.

Bob wins exactly when $n$ is a losing position for Alice. Among $1 \le n \le 2024$ there are $404$ multiples of $5$ and $405$ values $n \equiv 2 \pmod 5$ (from $2$ to $2022$ ), for a total of $404 + 405 = 809.$

2024 AIME I Problema 3

Solución:

El Problema 3 en otros años