Learn / Library / Brainteasers

Uneven coin stacks

BrainteasersHard

There are $4$ stacks of coins of sizes $6$ , $10$ , $15$ and $21$ . $2$ players alternate; a move takes any positive number of coins from exactly one stack. The player who takes the last coin wins. You move first and both players play optimally. Exactly one first move guarantees you a win. How many coins does that move take?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Compute the XOR of the $4$ sizes and ask which stack can be cut down to make it $0$ .

Solution

A position in this game is lost for the player to move exactly when the XOR of the stack sizes is $0$ .
Step by step, $6$ XOR $10$ is $12$ , then $12$ XOR $15$ is $3$ , then $3$ XOR $21$ is $22$ .
A stack of size $s$ can be reduced to $s$ XOR $22$ only if that is smaller than $s$ ; this needs the leading bit of $22$ , which is $16$ , and only $21$ has it.
So the stack of $21$ goes down to $21$ XOR $22$ , which is $3$ , and the XOR of $6$ , $10$ , $15$ and $3$ is then $0$ .
The winning move takes $21 - 3 = 18$ coins, so the answer is $18$ .

Answer: $18$

Next question Back to the library