AUT ABooklet

Combinatorics Difficulty 6.9 National Olympiad Prove it Austria

Alice and Bob play a game on a strip of $n \ge 3$ squares with two game pieces. At the beginning, Alice's piece is on the first square while Bob's piece is on the last square. The figure shows the starting position for a strip of $n = 7$ squares.

The players alternate. In each move, they advance their own game piece by one or two squares in the direction of the opponent's piece. The piece has to land on an empty square without jumping over the opponent's piece. Alice makes the first move with her own piece. If a player cannot move, they lose.

For which $n$ can Bob ensure a win no matter how Alice plays?
For which $n$ can Alice ensure a win no matter how Bob plays?

Solution

Bob wins for $n = 3k + 2$ with $k \in \mathbb{Z}_{\ge 1}$ , Alice wins for all other $n \ge 3$ .

It is easily checked that Alice wins for 3, 4, 6 and 7 squares while Bob wins for 5 or 8 squares. We conjecture that Bob wins for all $n$ of the form $3k + 2$ and prove it by induction.

We include the case $k = 0$ which is obvious because Alice loses immediately.

Now, we assume that Bob can assure a win for $3k + 2$ squares for a certain natural number $k$ . Now, we want to prove that he can ensure a win for $3k + 5$ .

It is enough that Bob makes exactly the opposite move of Alice after her first move: If she moves by 1, he moves 2. If she moves by 2, he moves 1. This ensures that the distance between the two game pieces is reduced by 3 and the game continues as if it were a new game with $3k + 2$ squares where we already know that Bob can ensure a win.

Therefore, we have proved that Bob can win for all $n = 3k + 2$ .

Now, it remains to show that Alice can win for all $n$ of the form $3k$ and $3k + 1$ .

In the case of $3k$ squares, she starts the game by moving 1 such that the remaining game is played on $3k - 1 = 3(k - 1) + 2$ squares with Bob making the first move. So we already know that Alice as the second player can ensure a win.

In the case of $3k + 1$ , Alice starts with 2 which again reduces the game to a game with $3(k - 1) + 2$ squares with Bob making the first move.

We can conclude that Bob can ensure a win for all $n = 3k + 2$ , and Alice can ensure a win for all other $n$ .

(Theresia Eisenkölbl) ☐

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.