Square coins?

Probability Level 3

A pile of coins is on the table.

Two players alternate picking $n$ coins from the table, where $n$ must be a square number. For example, if there are 10 coins on the table, you could take 1, 4 or 9 coins.

The player to take the last coin (or a group containing the last coin) wins!

Martha realizes that if it's her turn, and there are 22 coins in the pile, she can't guarantee a win.

What is the next number greater than 22 for which if it is your turn you will lose assuming both players play optimally?

If you think there are no such numbers, i.e. every number greater than 22 will guarantee you a win, then please provide 0 as the answer.

Image credit: http://www.fotosearch.com/

The answer is 34.

1 solution

Geoff Pilling
Dec 2, 2016

Let $1$ represent a win and $0$ represent a loss.

Then in general, whether you win, given $n$ coins, and its your turn to move, is calculated by the following recursion relation:

$W(n) = 1$ if $n$ is a square number
$W(n) = 1 - MAX(n-i)$ , where $i$ are all the squared numbers less than $n$

The second equation is because if you can pick a square number $i$ such that $W(n-i) = 0$ , you will, and will leave the other player with a losing number of coins to play from.

This gives

$W(n) = 1$ for $22<n<34$
$W(34) = 0$ .

Therefore $\boxed{34}$ is the first number greater than $22$ for which you will lose the game if its your turn and that many coins are in the pile.

Terrific question! Thanks for posting it. The next two numbers are $39$ and $44$ . Using $22, 34, 39, 44$ I got a hit on OEIS. Golomb's paper makes for some good light reading. :p

Brian Charlesworth - 4 years, 6 months ago

Square coins?

Image credit: http://www.fotosearch.com/

The answer is 34.

1 solution

0 pending reports