I have to find the winning strategy for the following game. There is a heap with $N$ objects. Two players take objects in turn, but there is a limitation: if there were taken $K$ objects on previous turn, then player can take only $K$ or $K + 1$ objects on current turn. On the first turn a player can take 1 or 2 objects. The one to make the last turn is the winner.
I've written a simple program using dynamic programming that calculates a winner for different values of $N$. There are some of them:
N winner
1 1
2 1
3 1
4 2
5 1
6 2
7 1
8 1
9 1
10 2
11 1
12 1
13 2
14 1
15 2
16 1
17 1
18 2
19 1
20 1
Actually I couldn't find any pattern in this sequence (for $N \le 100$). Also the distance between adjacent second players' winning positions doesn't exceed $4$, but I can't explain that.
Maybe this problem can be reduced to nim somehow...
This is not a solution; it’s a way of looking at the game that may provide some insight, together with some possibly useful data.
This can be viewed as a game played on a grid. You start at $\langle n,1\rangle$; if you’re at $\langle k,\ell\rangle$, the possible moves are to $\langle k-\ell,\ell\rangle$ and to $\langle k-\ell-1,\ell+1\rangle$. If $k<\ell$, no move is possible, and you lose. Clearly you want to avoid moving to a point $\langle k,\ell\rangle$ with $\ell\le k\le 2\ell+1$: if $k=\ell$, your opponent will move to $\langle 0,\ell\rangle$, and in all other cases your opponent will move to $\langle k-\ell-1,\ell+1\rangle$, and you’ll have no legal move. Using $1$ for a position in which the player whose turn it is has a winning move (i.e., an N-position in the usual terminology), and $2$ for a position in which the other player wins (a P-position), some of the grid looks like this:
$$\begin{array}{c|cc} 7&2&2&2&2&2&2&2&1&1&1&1&1&1&1&1&1&2\\ 6&2&2&2&2&2&2&1&1&1&1&1&1&1&1&2&2&2\\ 5&2&2&2&2&2&1&1&1&1&1&1&1&2&2&2&2&2\\ 4&2&2&2&2&1&1&1&1&1&1&2&2&2&2&1&1&1\\ 3&2&2&2&1&1&1&1&1&2&2&2&1&1&1&1&1&1\\ 2&2&2&1&1&1&1&2&2&1&1&2&1&1&1&2&2&1\\ 1&2&1&1&1&2&1&2&1&1&1&2&1&1&2&1&2&1\\ \hline \ell\backslash k&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \end{array}$$
It’s clear that $\langle k,\ell\rangle$ is a P-position if $0\le k<\ell$, and it’s not hard to verify that $\langle k,\ell\rangle$ is an N-position if $\ell\le k\le 2\ell+1$ and a P-position if $2\ell+2\le k\le 3\ell+1$. Moreover, if $k<\binom{n+1}2$, then $k\le\sum_{i=2}^ni$, and from the position $\langle k,1\rangle$ we can go no higher than $\ell=n$ (and that only at $\langle 0,n\rangle$). In fact we’ll cross the line $k=3\ell+1$ sooner than that, there’s a pretty efficient algorithm for determining whether $\langle k,1\rangle$ is an N- or a P-position.