1
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ – Brian Tung Oct 21 '15 at 19:17
  • $\begingroup$ @Brian: Yes: you can confirm it by the fact that Player 1 is given as the winner for $n=3$. $\endgroup$ – Brian M. Scott Oct 21 '15 at 19:19
  • $\begingroup$ Can you give more of the sequence? (It would suffice to list the N's for which player 2 is the winner.) $\endgroup$ – Barry Cipra Oct 21 '15 at 19:26
  • $\begingroup$ 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 $\endgroup$ – perlik Oct 21 '15 at 19:28
  • $\begingroup$ @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. $\endgroup$ – Barry Cipra Oct 21 '15 at 19:33
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is essentially the same diagram that I produced (albeit upside-down). There are even some obvious regularities in the upper left half of the grid. Unfortunately, things get a little chaotic as we descend toward the lower right... $\endgroup$ – Brian Tung Oct 21 '15 at 20:20
  • $\begingroup$ @Brian: It is indeed; I was typing and didn’t see any of those comments. $\endgroup$ – Brian M. Scott Oct 21 '15 at 20:22
  • 1
    $\begingroup$ No worries; I'm just glad someone else went through the trouble of typing it up. :-) $\endgroup$ – Brian Tung Oct 21 '15 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.