Let $A$, $B$ and $C$ represent the number of tokens in three piles. A $\textit{game}$ between Alice and Bob starts with at most $n$ tokens in each pile (i.e. $0 < A, B, C \leq n$) and consists of them taking turns. A $\textit{turn}$ consists of a player removing $x$ tokens from one pile and $y$ tokens from a different pile, with the constraint that $x + y > 0.$ The player to remove the last set of tokens wins. Alice goes first in every game, and they play through all possible starting configurations of $A, B, C.$ If Alice and Bob play in such a way that ensures their own number of wins is maximized, how many games does Alice win?
  1. Alice and Bob play tic-tac-toe. Bob starts with an $X$ in the top left corner, and Alice replies with an $O$ in the opposite corner. How should Bob play to win?
  2. $31$ tokens lie on the table. In each move, a player can take one or two coins. The player to remove the last token wins. Alice decided to leave her opponent with a number of tokens which is divisible by $3$ after each move. Prove, using mathematical induction, that she will be able to do that, no matter what her opponent does, and finally win the game.

Who wins when $A=B=C=1$ and why?

Describe all configurations from which you can get to $A=B=C=1$ in one move.

Notice that in all of them you can ensure a win.

If $A, B, C$ are not all equal, can you make one move to make them all equal?

Who wins when $A=B=C=2$ and why?

Generalise your result to any case when $A=B=C$?

Use the principle of mathematical induction to prove that all positions when $A=B=C$ are losing and that all others are winning.

For $A=B=C=1$ case Alice loses as she can remove either 1 or 2 tokens, leaving Bob to remove the remaining ones. Notice that whoever has $A=B=C$ loses and otherwise can win. We may use the following observations to build an inductive proof of this fact.

  • $(1, 1, 1)$ is a losing position.
  • When $A, B, C$ are not all equal, one can choose the smallest and make the remaining ones equal to it.
  • When $A, B, C$ are all equal, it is impossible to keep them all equal, due to the constraint $x + y > 0.$

For all games starting with $A=B=C$, Bob wins, and for all other games, Alice wins. There are $n^3$ games in total, excluding 0 games, and Alice wins $n^3-n$ games, and Bob wins $n$.