### Volume 30 solution – Oliver Chambers

We had three correct submissions this month: congratulations to Felix Zhu, Thomas Zhou, and Ean Chan. The recipient of this month’s book voucher is Felix Zhu.

PROBLEM

$$n > 10$$ coins lie in a line on a table. Initially all coins show heads. Two players, $$A$$ and $$B$$, take it in turns to find a block of $$10$$ consecutive coins with the leftmost coin showing heads and flipping those $$10$$ coins over (such that the heads show tails and vice versa). If a player is not able to make a move then they lose the game.

• Show that the game always terminates
• If Player $$A$$ may decide whether to play first or second. Is there a winning strategy? If so, what is it?

SOLUTION

• There is a natural bijection between the state of the coins and a binary number where heads maps to 1 and tails maps to 0. This number is strictly decreasing (but non-negative) after each move so the game must terminate.
• Number the coins from $$n$$ (left-most coin) to $$1$$ (right-most coin) and consider the coins at $$10k$$ for $$k = 1, …, \left\lfloor\frac{n}{10}\right\rfloor$$. Any legal move will flip exactly one of these coins, so after two moves the parity of the number of those coins is preserved. That means that if $$\left\lfloor\frac{n}{10}\right\rfloor$$ is odd then the first player will always have a legal move (i.e. the first player wins regardless of strategy). On the other hand, if $$\left\lfloor\frac{n}{10}\right\rfloor$$ is even then the first player will always lose. So Player $$A$$’s strategy is simply to check the parity of $$\left\lfloor\frac{n}{10}\right\rfloor$$ and chose to play first or second accordingly.

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.

Previous

Next