The idea of solving this kind of problem consists of creating a brute force solution for small input instances (~N \le 1\,000~) and observing solution patterns for solving big cases.

Solution for small ~N~ uses a dynamic programming approach. Let ~dp[x][k]~ denote if a player can win regardless of its opponent's actions (winning position) if there are ~x~ pebbles remaining, and he can take at most ~2k~ rocks in the current turn. These are the possible transitions:

$$\displaystyle dp[x-1][1], dp[x-2][2], dp[x-3][3], \dots, dp[x-2k][2k]$$

under the assumption that there are enough rocks (~2k \le x~), otherwise it is allowed to take ~x~ rocks at most. If every neighbouring state is a losing position, we can conclude that our current state is a winning position. From these observations, we can quickly create an ~\mathcal O(N^3)~ algorithm.

Observing the outputs for small ~N~ we can notice that solutions we are looking at are in fact Fibonacci numbers. We can also observe that most of the solutions are not too big (except for the Fibonacci numbers and numbers which can be written as sums of Fibonacci numbers - their solutions are big). From these facts our intuition tells us that we might be able to find a solution if we try to disassemble the number ~N~ as a (unique) sum of non-consecutive Fibonacci numbers - the solution is then in fact the smallest number in the sum. That algorithm can be implemented in ~\mathcal O(\log N)~ complexity.

For those who want to learn more about this type of problem - try to look for the math game called "Fibonacci Nim".