# Perfect information game with heap of objects

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...

• I assume that if a player is unable to take exactly $K$ or $K+1$ objects (because there are fewer than $K$ objects remaining), that player loses, yes? – Brian Tung Oct 21 '15 at 19:17
• @Brian: Yes: you can confirm it by the fact that Player 1 is given as the winner for $n=3$. – Brian M. Scott Oct 21 '15 at 19:19
• Can you give more of the sequence? (It would suffice to list the N's for which player 2 is the winner.) – Barry Cipra Oct 21 '15 at 19:26
• 4,6,10,13,15,18,22,24,28,30,33,35,37,40,42,46,49,51,54,56,58,61,65,67,70,73,75,78,82,84,88,92,94,97 – perlik Oct 21 '15 at 19:28
• @perlik, thank you. The first few numbers, 4,6,10,13,15,18 (from the OP) had a couple of hits at the OEIS, but they go away with the next couple of terms. – Barry Cipra Oct 21 '15 at 19:33

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.