Nim - Page 2

Wacky · 2007-09-20, 00:14

Quote:

Originally Posted by davieddy

If you like. Does the first player win or lose?

That depends on their strategies.

I assume that you really wish to ask "Is there a strategy by which the first player can assure a win?"

davieddy · 2007-09-20, 01:09

To use another chess analogy, the winning strategy puts
the opponent in "Zugswang" (where any move loses).
This is always (and often uniquely) possible unless you are
in Zugswang yourself.
The question is "What constitutes Zugswang?".

David

Zeta-Flux · 2007-09-20, 01:45

3 5 7 wins for 1st player.

General note: If there is ever only one pile left, the player to play wins. If there are two piles, the player who can make both piles have the same number of items wins. (And he just matches the other player's move from there-on-out.) We will take these as givens.

The winning strategy goes something like this

3 5 7 -> Player 1 takes an item from the first pile resulting in 2 5 7

Option 1: Player 2 takes an entire pile or makes two piles have the same number of items. In either case, player 1 can force there to be only two piles, both with the same number of items, thus winning.

Option 2: Player 2 makes the first pile have 1 item. So we are at 1 5 7. In this case player 1 changes the 7 to a 4, resulting in 1 4 5. At this point player 2 is either forces to take an entire pile (and he loses, as in option 1), make two piles have the same number of items (and player one takes the other pile, winning again), or changing the 4 or 5 into a 2 or 3. In either of these last two cases, player 1 forces the piles to become 1 2 3 (possibly renumbering the piles). At this point player 2 is FORCED to take a pile or make two of the piles equal, and player 1 wins again.

Option 3: Player 2 makes the 5 pile or the 7 pile into a 3. In this case, player 1 makes the other untouched pile into a 1, resulting in 1 2 3 (which we saw wins for player 1).

Option 4: Player 2 makes the 7 pile into a 4. In this case, player 1 makes the 2 pile into a 1, resulting in 1 4 5 which we saw won under option 2.

Option 5 (the last untouched option!): Player 2 makes the 5 pile into a 4 or the 7 pile into a 6. In this case, player 1 does the opposite, resulting in 2 4 6.

Option 5a: Player 2 takes an entire pile or makes two piles equal (loses again!).

Option 5b: Player 2 changes it to 1 4 6. Player 1 changes it to 1 4 5 and wins as before.

Option 5c: Player 2 changes it to 1 3 6 or 1 3 4. In either case (after renumbering the piles) player 1 changes it to 1 2 3, winning as before.

Option 5d: Player 2 changes it to (after renumbering the piles) 1 2 6 or 1 2 4. In either case player 1 changes it to 1 2 3.

------------

I tried to analyze the 3 pile situation in generality, but got bogged down fairly quickly. If one fixed the three piles n_1 < n_2 < n_3 then if n_2 is big with respect to n_1 there is a general rule about what you want n_3 to do, but when n_2 is close to n_1 things get crazy and depend on smaller n_1's.

Zeta-Flux · 2007-09-20, 01:51

Note: I believe there is one other winning first move for player 1. Namely, make it 3 5 6.

Kevin · 2007-09-20, 08:04

Small hint:Why yes, 2,1+4,1+2+4 works, as well as 1+2,1+4,2+4

Zeta-Flux · 2007-09-20, 12:19

Kevin,

I'm not sure I follow your hint. At first I thought that you were decomposing the numbers so that every number is matched with another number once. But that won't work in general since 2 3 2+3 doesn't win (player 2 just makes it into 1 2 3). Then I thought maybe it had to do with having 3 matching pairs, or only powers of 2, but again 2 1+2 1+2+2 won't work. Every rule I can think up for why you would want such a decomposition fails to work for some other decomposition.

So, could you provide a little more of a hint? (Especially since I already proved that my two solutions work.)

davieddy · 2007-09-20, 15:15

5 is 1+4
Represent the numbers in binary. We want an even number of
1's in each binary place for Zugzwang.
Show that we can always accomplish this unless our opponent has.

Zeta-Flux · 2007-09-20, 16:04

That is clever! It's a double parity. It was the second parity I missed (looking at the 2-adic representation).

davieddy · 2007-09-21, 12:30

Quote:

Originally Posted by Zeta-Flux

That is clever! It's a double parity. It was the second parity I missed (looking at the 2-adic representation).

THX, Although I don't claim originality, I did deduce this myself about
20 years ago. A drinking partner presented me with 1,2,3,4,5 piles of matches.
Glad to find someone who tried it out instead of Googling

David

2007-09-20, 15:15	#18
davieddy "Lucan" Dec 2006 England 14512₈ Posts	5 is 1+4 Represent the numbers in binary. We want an even number of 1's in each binary place for Zugzwang. Show that we can always accomplish this unless our opponent has. Last fiddled with by davieddy on 2007-09-20 at 15:33

2007-09-20, 16:04	#19
Zeta-Flux May 2003 7·13·17 Posts	That is clever! It's a double parity. It was the second parity I missed (looking at the 2-adic representation). Last fiddled with by Zeta-Flux on 2007-09-20 at 16:07

2007-09-20, 01:09	#13
davieddy "Lucan" Dec 2006 England 2×3×13×83 Posts	To use another chess analogy, the winning strategy puts the opponent in "Zugswang" (where any move loses). This is always (and often uniquely) possible unless you are in Zugswang yourself. The question is "What constitutes Zugswang?". David

2007-09-20, 01:45	#14
Zeta-Flux May 2003 7×13×17 Posts	3 5 7 wins for 1st player. General note: If there is ever only one pile left, the player to play wins. If there are two piles, the player who can make both piles have the same number of items wins. (And he just matches the other player's move from there-on-out.) We will take these as givens. The winning strategy goes something like this 3 5 7 -> Player 1 takes an item from the first pile resulting in 2 5 7 Option 1: Player 2 takes an entire pile or makes two piles have the same number of items. In either case, player 1 can force there to be only two piles, both with the same number of items, thus winning. Option 2: Player 2 makes the first pile have 1 item. So we are at 1 5 7. In this case player 1 changes the 7 to a 4, resulting in 1 4 5. At this point player 2 is either forces to take an entire pile (and he loses, as in option 1), make two piles have the same number of items (and player one takes the other pile, winning again), or changing the 4 or 5 into a 2 or 3. In either of these last two cases, player 1 forces the piles to become 1 2 3 (possibly renumbering the piles). At this point player 2 is FORCED to take a pile or make two of the piles equal, and player 1 wins again. Option 3: Player 2 makes the 5 pile or the 7 pile into a 3. In this case, player 1 makes the other untouched pile into a 1, resulting in 1 2 3 (which we saw wins for player 1). Option 4: Player 2 makes the 7 pile into a 4. In this case, player 1 makes the 2 pile into a 1, resulting in 1 4 5 which we saw won under option 2. Option 5 (the last untouched option!): Player 2 makes the 5 pile into a 4 or the 7 pile into a 6. In this case, player 1 does the opposite, resulting in 2 4 6. Option 5a: Player 2 takes an entire pile or makes two piles equal (loses again!). Option 5b: Player 2 changes it to 1 4 6. Player 1 changes it to 1 4 5 and wins as before. Option 5c: Player 2 changes it to 1 3 6 or 1 3 4. In either case (after renumbering the piles) player 1 changes it to 1 2 3, winning as before. Option 5d: Player 2 changes it to (after renumbering the piles) 1 2 6 or 1 2 4. In either case player 1 changes it to 1 2 3. ------------ I tried to analyze the 3 pile situation in generality, but got bogged down fairly quickly. If one fixed the three piles n_1 < n_2 < n_3 then if n_2 is big with respect to n_1 there is a general rule about what you want n_3 to do, but when n_2 is close to n_1 things get crazy and depend on smaller n_1's.

2007-09-20, 01:51	#15
Zeta-Flux May 2003 7·13·17 Posts	Note: I believe there is one other winning first move for player 1. Namely, make it 3 5 6.

2007-09-20, 08:04	#16
Kevin Aug 2002 Ann Arbor, MI 433 Posts	Small hint:Why yes, 2,1+4,1+2+4 works, as well as 1+2,1+4,2+4

2007-09-20, 12:19	#17
Zeta-Flux May 2003 60B₁₆ Posts	Kevin, I'm not sure I follow your hint. At first I thought that you were decomposing the numbers so that every number is matched with another number once. But that won't work in general since 2 3 2+3 doesn't win (player 2 just makes it into 1 2 3). Then I thought maybe it had to do with having 3 matching pairs, or only powers of 2, but again 2 1+2 1+2+2 won't work. Every rule I can think up for why you would want such a decomposition fails to work for some other decomposition. So, could you provide a little more of a hint? (Especially since I already proved that my two solutions work.)