Thought Process

This problem seemed related to Problem 301, and indeed it was, some further research into Nim landed me to the Sprague-Grundy Theorem, which is a theorem which can solve games like the one illustrated in the question. Essentially it details a dynamic programming solution approach.

Let Pi denote a position with i blocks, if Pi = 0, then this position is won for the player that is not in this position, Let mex() denote a function which outputs the least non-negative integer of a set of numbers, for example mex(0, 1, 2) = 3, mex(1, 2) = 0.

Then P0 = 0, P1 = 0,P2 = 1, Pi = mex(Pk ⊕ Pi-k-2) where 0 ≤ k ≤ floor(i/2), where ⊕ represents bit XOR.

For example:

1. P3 = mex(P0 ⊕ P1) = mex(0) = 1

2. P4 = mex(P0 ⊕ P2, P1 ⊕ P1) = mex(1, 0) = 2

3. P5 = mex(P0 ⊕ P3, P1 ⊕ P2) = mex(1, 1) = 0

From this we can see that Player 1 has a winning position if there are 2, 3, 4 blocks, as illustrated in the question.

Using dynamic programming I was able to find the answer for 1 ≤ n ≤ 10,000, and then it was getting too slow. I decided to try putting the numbers where player 1 wins and player 2 wins into OEIS, and the player 2 wins gave me https://oeis.org/A215721, and crucially the following formula was listed which makes the problem become instantaneously solvable "For n > 14, a(n) = a(n-5) + 34".