$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?
-
- 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? $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.
- Alice and Bob play tic-tac-toe. Bob starts with an
-
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$.