Emilia and Julieta have a pile of 2024 cards and play the following game: they take turns, and each player removes a number of cards that must be a power of two, i.e., \(1, 2, 4, 8, \dots\). The player who removes the last card wins. Julieta starts the game. Prove that there exists a strategy for Julieta that guarantees her victory, no matter how Emilia plays.
Problem
Source:
Tags: combinatorics, Chile
onyqz
23.10.2024 21:36
funny problem
We will prove this by induction on the number of cards $n$.
For $n=1,2$ then Julieta we immediately win. For $n=3$ Emilia would win. Now suppose that for $k\equiv 1,2 \mod 3, k\leq n$ the person to start would win (call it winning position) and for $k\equiv 0 \mod 3, k\leq n$ the person to start would lose (a losing position.
Let $n \longrightarrow n+1$.
If $n+1\equiv 1,2 \mod 3$, then it can be written as $(n) + 1 = 3k + 1$ or $(n-1) + 2 = 3k + 2, k\in \mathbb{N}$, in which case the player who starts can take the one or two cards respectively, after which the second player is in a losing position. Therefore $n+1 \equiv 1,2 \mod 3$ is a winning position.
If $n+1\equiv 0 \mod 3$ however, then the player who starts cannot take $2^m, m\in\mathbb{N}$ cards s.t. the second player is in a losing position, i.e. $3k-2^m \equiv 0 \mod 3 $ is a contradiction. Therefore, $n+1\equiv 0 \mod 3$ is a losing position.
Note that $2024\equiv 2 \mod 3$, which is by induction a winning position, so Julieta can guarantee her victory. $\square$