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

Respuesta: 809

Conceptos:juego combinatorio aritmética modular casos pequeños

Nivel de dificultad: 2110

Pista pequeña:

Determina cuáles

n

pequeños son derrotas para el jugador a punto de mover:

n

es una derrota exactamente cuando tanto

n - 1

como

n - 4

son victorias

Work out which small

n

are losses for the player about to move:

n

is a loss exactly when both

n - 1

and

n - 4

are wins

Pista grande:

Las posiciones perdedoras se repiten con período

5:

son

n \equiv 0

o

2 \pmod 5.

Bob gana exactamente para esos

n.

The losing positions repeat with period

5:

they are

n \equiv 0

or

2 \pmod 5.

Bob wins exactly for those

n.

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

Respuesta: 809

Nivel de dificultad: 2110

Pista pequeña:

Pista grande:

Solución:

El Problema 3 en otros años