The Computer Laboratory

Practice Paper 3 Question 18

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?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  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.

Hints

  • Hint 1
    Who wins when \(A=B=C=1\) and why?
  • Hint 2
    Describe all configurations from which you can get to \(A=B=C=1\) in one move.
  • Hint 3
    Notice that in all of them you can ensure a win.
  • Hint 4
    If \(A, B, C\) are not all equal, can you make one move to make them all equal?
  • Hint 5
    Who wins when \(A=B=C=2\) and why?
  • Hint 6
    Generalise your result to any case when \(A=B=C\)?
  • Hint 7
    Use the principle of mathematical induction to prove that all positions when \(A=B=C\) are losing and that all others are winning.

Solution

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\).

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.