Game Theory: Nim - Winning Strategy for 5 & 1000 Stones

[Ikastun]

Homework Statement

• Two players: A and B.
• Players can take 1 or 2 stones per turn.
• The player who takes the last stone wins.

The question is: is there any winning strategy with 5 stones?, does it change with 1000 stones?.

Homework Equations

None.

The Attempt at a Solution

If there are 5 stones player A has a winning strategy if he takes 2 stones in his first turn. 3 stones left, so B can take 1 or 2 but in any case there are available stones and A wins.

If there are 1000 stones I don't know.

 

[LCKurtz]

Homework Statement

• Two players: A and B.
• Players can take 1 or 2 stones per turn.
• The player who takes the last stone wins.

The question is: is there any winning strategy with 5 stones?, does it change with 1000 stones?.

Homework Equations

None.

The Attempt at a Solution

If there are 5 stones player A has a winning strategy if he takes 2 stones in his first turn. 3 stones left, so B can take 1 or 2 but in any case there are available stones and A wins.

If there are 1000 stones I don't know.

Try a few cases like 4,6,7,8,9 stones etc and see if you notice anything.

 

[HallsofIvy]

"Five stones" is pretty close to trivial. The first person takes 2 stones, leaving three. If the second person takes one stone, the first person takes the two remaining stones, winning. If the second person takes two stones, the first person takes the one remaining stone, winning.

 

[LCKurtz]

The attempt at a solution

If there are 5 stones player A has a winning strategy if he takes 2 stones in his first turn. 3 stones left, so B can take 1 or 2 but in any case there are available stones and A wins.

"Five stones" is pretty close to trivial. The first person takes 2 stones, leaving three. If the second person takes one stone, the first person takes the two remaining stones, winning. If the second person takes two stones, the first person takes the one remaining stone, winning.

Didn't the OP already observe that?

 

[phinds]

If there are 1000 stones I don't know.

The number of stones is irrelevant. There is a winning strategy. Period.

It's been about 50 years since I knew the math on it but it's something like writing out the # of remaining stones in binary and then taking away a number of stones that does something (I forget what) the the form of the binary number.

 

[STEMucator]

Presuming there are 1000 stones and player A gets to go first...

It seems to me that player A can ensure a victory every time as long as he doesn't take 2 stones at a time on the first turn ( I tried several cases myself ).

If player A only takes 1 stone on the first turn, he/she can force player B into the 5 stone scenario which you know is a guaranteed win. Just some stuff I was fiddling with.

 

[LCKurtz]

The number of stones is irrelevant. There is a winning strategy. Period.

Not always. It depends on the starting state.

It's been about 50 years since I knew the math on it but it's something like writing out the # of remaining stones in binary and then taking away a number of stones that does something (I forget what) the the form of the binary number.

But the OP's problem is a simple sub-version of the game of Nim. You don't need anything but a little reasoning to figure it out. Hopefully everyone will let the OP do that.

 

[phinds]

Not always. It depends on the starting state.

You are right of course. If the starting state has the binary number in the requisite form and they both know the strategy, then the starter cannot win. Good point.

EDIT: there IS still a winning strategy of course, just not for the starter in this case

 

[phinds]

OH, I just realize that the OP is talking about a LIMITED form of NIM (yeah, LCKurtz, I see that you pointed that out --- I'm dense sometimes). That may not have a winning strategy for any number of starting stones. I think I remember now what the strategy that I was talking about is and it requires that you be able to remove up to half of the stones.

 

[STEMucator]

I would also like to add to my previous post.

If it gets down to it, player A can win if they can force player B ( Of course presuming a perfect game is played ) to allow them to take stones when there are only 4, 5, 7, or 8 stones left.

 

[LCKurtz]

Hey everybody, enough with the hints and partial solutions. Let's wait for the OP to make some progress.

 

[haruspex]

The number of stones is irrelevant. There is a winning strategy. Period.

Not always. It depends on the starting state.

Well, there is always a winning strategy in such games, but whether it's the first or second player that has it available depends on the starting state. The set of positions can be partitioned into two sets. In one set, every legal move leads to a position in the other set; the player having to play from such a position should lose. In the other set, there exists at least one move which leads to a position in the first set; that move is the winning line.
Viewed this way, it becomes a problem of control. You can often invert the criterion for a win (e.g. in Nim, whether the player to take the last stone wins or loses) without changing the essential strategy. Only a few positions in the endgame switch set.

 

[HallsofIvy]

Didn't the OP already observe that?

Yes, he did. I just didn't read all of the post! It looks to me like the first player can win if he moves so as to always leave an odd number of stones. Until the last move: if there are 1 or 2 stones left take them all, of course.

 

[D H]

Yes, he did. I just didn't read all of the post! It looks to me like the first player can win if he moves so as to always leave an odd number of stones.

That is not a winning strategy. Consider N=7. You have just given your opponent a winning state if you take away two stones. This is not too much of a hint because we already know that N=5 is a state that has winning strategy.

Hey everybody, enough with the hints and partial solutions. Let's wait for the OP to make some progress.

Hear, hear. There is a generic solution to the problem. Everyone, please give the OP time to find it.

 

[Ikastun]

Thank you all for your help. I think I got the solution after trying with n= 4, 6, 7, 8, 9 and 10.

When n=4 A takes 1, they remain 3 so B loses. A's winning strategy is 1 stone in his first turn.

When n=6 then A doesn't have any WS whether he takes 1 or 2 stones. If he takes 1 there are 5 left, so B wins. If he takes 2 there are 4, so B takes 1 and wins the game, since A only can take up to 2, but in any case B is the winner.

When n=7 then A does have a WS if he starts taking 1, so B must deal with n=6 which is the previous case.

When n=8 then A has a WS. He takes 2 and n=6. Same case.

When n=9 A doesn't have any WS. Regardless how many he takes in the first turn he cannot win (n=8 or n=7).

When n=10 A has a WN taking 1.

I think that the key is that A has a WS if the number of stones left that he has to confront isn't multiple of 3. If n=1000 A has to take 1 in his first movement, and then he has to follow the idea of multiple. Is it correct?.

Thanks in advance.

 

[D H]

I think that the key is that A has a WS if the number of stones left that he has to confront isn't multiple of 3. If n=1000 A has to take 1 in his first movement, and then he has to follow the idea of multiple. Is it correct?.

Correct. This is a trinary (base 3) rather than binary (base 2) problem.

 

[haruspex]

Correct. This is a trinary (base 3) rather than binary (base 2) problem.

Well, it's not a ternary solution in the sense of standard Nim's binary solution. It is, as Ikastun says, just a modulo 3 criterion, which is simpler.
To relate this to my earlier post, since each player has to take 1 or 2 stones, the second player in a pair of turns can always arrange that the total of the two turns is 3 (provided there were at least 3 left). Thus the value mod 3 becomes a relevant property. If the objective is to take the last stone then leaving a multiple of 3 wins; if the objective is to leave the last stone then leaving 1 mod 3 wins.
We can make it a bit more like standard Nim by introducing multiple piles. You can take 1 or 2 stones, but only from one pile. I would guess a ternary solution analogous to that of standard Nim might apply.