AUT_ABooklet_2023

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) ☐