# Using your Head is Permitted

## January 2013 solution

#### Part 1:

The second player has a winning strategy if *N* is a multiple of 4.
The first player has one, otherwise.
Proof: from any number that is not a multiple of 4, taking 1, 2 or 3 can
make it into a multiple of 4. However, because all multiples of 4 are
composites, a player starting at a multiple of 4 can only take values that will
not retain this property.

#### Part 2:

The second player has a winning strategy if *N* is a power of 2.
The first player has one, otherwise.
Proof: if 2^{K}<*N*<2^{K+1}, then
we take away *N*-2^{K}< to make the result a power of
2. If *N*=2^{K}, the result after subtraction
cannot be a power of 2.

#### Part 3:

The second player has a winning strategy if *N* is a power of 2.
The first player has one, otherwise.
Strategy: take away *x*=gcd(*N*,2^{N}).
Doing so ensures that

- The number of 1s in the binary representation of the number of elements
left decreases.
- The next player cannot do the same, because it requires removal of
at least 2
*x* elements.

This is always a valid strategy (when not starting at a power of 2), because if
it is followed and the previous player removed *y* elements from a pile of
*N* elements, then the next
amount to be removed will be gcd(*N*-*y*,2^{N-y})
= gcd(*y*,2^{y}) ≤ *y*.
#### Part 4:

The second player has a winning strategy if *N* is a number from the
Fibonacci sequence (*F*(1)=1, *F*(2)=2, *F*(3)=3,
*F*(4)=5, *F*(5)=8, *F*(6)=13, etc.). The first player has one,
otherwise.
Strategy for first player: Let
*F*(*k*)<*N*<*F*(*k*+1) and
*x*=*N*-*F*(*k*). If *x*<*F*(*k*)/2,
take *x*. (This puts the other player on *F*(*k*) with no
ability to take all the elements, and hence wins the game by induction on
*N*.) Otherwise, play as you would for an initial pile of size *x*.
(Because *x*≥*F*(*k*)/2, we have
*F*(*k*-2)<*x*<*F*(*k*-1), so by induction the
strategy for *x* will reduce the pile to a size of *F*(*k*).
Furthermore, we know that the last amount to be taken by the player in the last
round before reducing to *F*(*k*) must have been less than
*F*(*k*)/2. If it was otherwise, this would indicate that in the
previous move the second player took more than *F*(*k*)/4,
for a total of 1.75 *F*(*k*)>*F*(*k*+1), contradicting
*N*<*F*(*k*+1). Thus, after reaching
*F*(*k*), the first player cannot immediately clear the pile, and
is therefore in a losing position.)

Strategy for second player: Let *N*=*F*(*k*). If the first
player took 1/3 or more of the pile, simply empty it and win. Otherwise, the
first player must have taken less than *F*(*k*-2). Employ the
second player strategy for *F*(*k*-2), followed by the second player
strategy for *F*(*k*-1). By induction, this leads to winning. Note
that on the first move after reaching *F*(*k*-1) the first player
cannot take the entire pile, because, once again, this would imply
*N*≥1.75 *F*(*k*)>*F*(*k*+1).

Back to riddle

Back to main page