1
$\begingroup$

First time asking a question here, so apologies if I ask something in the wrong way. I have two problems I got back from an exam and have been struggling to find a reasonable reason for their incorrectness.

The two problems are as follows:

Let's play a game of restricted Nim where a player can only take 2, 3, or 5 stones at a time. Let's start with 1000 stones, and you go first. Whats your move, why, and whats the expected outcome?

and then,

Let's play a different but similar game of restricted Nim where a player can only take 1, 4, or 5 stones at a time. Let's start with 1000 stones, and again, you go first. Whats your move, why, and whats the expected outcome?

For both answers I said that I would keep the total stones left at the end of my turn to be a multiple of 5, until my last move, where I take enough to put the stones to 6 or 7. This is so because form here the opponent cannot take all of them, and at a minimum lets me take the rest. I figured since the restrictions all have a sort of 'five-ness' to them that this was the right way to go. In either case I said that I will always win, ie the player that plays first.

Is there some gaping hole I'm missing here?

Thanks!

$\endgroup$
  • $\begingroup$ If your last move puts the stone at $6$ or $7$, what if the opponent takes $2$ or $3$ respectively? (For the first example) $\endgroup$ – Jihoon Kang Sep 26 '17 at 3:21
  • $\begingroup$ @JihoonKang, if your opponent puts the stones at $4$, you can take $3$, which leaves your opponent with no play. (That is, the object is not to take the final stone, it's to make the final move.) $\endgroup$ – Barry Cipra Sep 26 '17 at 3:23
  • $\begingroup$ @JihoonKang Is it possible to stalemate? $\endgroup$ – Marty Y Sep 26 '17 at 3:24
  • $\begingroup$ In light if these comments - what are the winning conditions? The objective of the standard game of Nim is to avoid making the last move (or rather avoid picking the last stone but these two are equivalent in this case) $\endgroup$ – Jihoon Kang Sep 26 '17 at 3:25
  • $\begingroup$ @JihoonKang the player that loses is the one that either has zero stones to remove or cannot make a move at the beginning of their move $\endgroup$ – Marty Y Sep 26 '17 at 3:34
1
$\begingroup$

The answer above that considers losing piles is a good way to think about the problem. Specifically, call a 'losing' pile a P-position (P for 'previous', meaning the previous player will win). If it is your turn, and the game is in a P-position, then you will lose.

The nice thing about P-positions is that they satisfy the two following facts:

  • If you are at a P-position, then you cannot move to another P-position
  • If you are not at a P-position, then there is a move to a P-position.

This allows you to work backward through the game recursively, finding all the P-positions. The winning strategy is always to move to a P-position, leaving your opponent with a losing position. I'll show the solution for the first set of numbers, where a player can take 2,3, or 5 stones. I'll assume that when there's one stone left, a player loses because they have no legal moves. That makes one a P-position, and 0 is a natural P-position as well since if it's your turn and there are no stones, your opponent just won. Make a grid and mark the P-positions:

enter image description here

Now you work backward through the grid, marking either 'x' or 'P'. For instance, 2 is not a P-position because there exists a move from 2 to 0, which means the position 2 can 'see' a P-position. That violates the first property, so 2 is not a P-position. By the same reasoning, neither are 3, 4, 5, or 6, since they can all 'see' a P-position.

enter image description here

Now we look at the position labeled 7. There are no moves from 7 to a P-position, which means that 7 itself must be one. Then work backward from 7 as before:

enter image description here

What about 8? It's also a P-position, since it can't see any other P-positions, and so 10, 11, and 13 get 'x'es too. The pattern becomes clear at this point; just as the answerer above me noted, the P-positions are the positions that are either a multiple of 7 or a multiple of 7 plus one.

enter image description here

Now the winning strategy is to always move to a P-position. If we start at 1000, that's equal to $7\cdot 142 + 6$, i.e. the remainder is 6 when you divide by 7. You want to leave a remainder of 0 or 1; you can leave a 1 by taking 5, again as noted in the answer by stewbasic. Based on his answer I suspect you'll find that 1000 is a P-position with the second ruleset.

$\endgroup$
  • $\begingroup$ This is a great visual representation and fantastic explanation. Thank you! I'm marking this as the answer, (I truly wish I could mark both!) solely because of the easy and nice visual accompanied. $\endgroup$ – Marty Y Sep 26 '17 at 20:48
4
$\begingroup$

By considering small piles and extrapolating, we can guess that the sets of losing pile sizes are $$ L_1=\{n\mid n\equiv 0\text{ or }1\pmod 7\} $$ for the first case and $$ L_2=\{n\mid n\equiv 0\text{ or }2\pmod 8\} $$ for the second. Indeed a valid move from $n\in L$ always ends outside $L$, and from any $n\notin L$ we can make a valid move to get into $L$.

In particular, starting from 1000 stones we should take 5 stones in the first case. In the second case we will lose to perfect play (there's not enough information to answer the question about what move to make; that depends whether we know the opponent uses some imperfect strategy).

$\endgroup$
  • $\begingroup$ Simple, beautiful answer! Thanks! $\endgroup$ – Marty Y Sep 26 '17 at 20:47

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.