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 2K<N<2K+1, then we take away N-2K< to make the result a power of 2. If N=2K, 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,2N). Doing so ensures that

  1. The number of 1s in the binary representation of the number of elements left decreases.
  2. The next player cannot do the same, because it requires removal of at least 2x 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,2N-y) = gcd(y,2y) ≤ 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 xF(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