Restricted Nim : Similarities between problem sets

Question

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!

Answer 1

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:

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.

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:

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.

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.

Answer 2

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