Pearls and Swine?

[Happy Extinction]

http://www.ebaumsworld.com/pearl.shtml

I think this is unbeatable - If you can get the other guy into a situation where the are n,n-1,n-2,n-3 pearls (or n,n-1,n-2,0) then you can win.

The game starts with you in that situation.

Either I am wrong or there is an elegant proof out there somewhere...

[Gandalf]

Originally Posted by Scoot!

http://www.ebaumsworld.com/pearl.shtml

I think this is unbeatable - If you can get the other guy into a situation where the are n,n-1,n-2,n-3 pearls (or n,n-1,n-2,0) then you can win.

The game starts with you in that situation.

Either I am wrong or there is an elegant proof out there somewhere...

I suspect the game is unbeatable, but your conditions are wrong.

Game starts (6,5,4,3) corresponding to (n,n-1,n-2,n-3) with n=6.

You could legally take all 6, leaving (5,4,3,0), corresponding to (n,n-1,n-2,0) with n=5. Or take all three, leaving (6,5,4,0) corresponding to (n,n-1,n-2,0) with n=6. If those are winning positions, you can always win from the initial position.

Leaving (3,2,1,0) is a win, I think. Which means leaving (4,3,2,1), corresponding to (n,n-1,n-2,n-3) with n=4, is a loss.

[BC]

This is NIM, basically. IIRC, the way to solve NIM is to break each down into BINARY:

3 = 011
4 = 100
5 = 101
6 = 110

Then add these up, WITHOUT CARRYING

Total = 322

The winning strategy is to make sure, at all points in time, that when your opponent does this he only has even numbers.

So it seems that winning first moves are to remove 4 pearls from any row from which this is possible.

[BC]

Actually, I guess you're supposed to make the OTHER guy take the last one. Which is why it took several tries to win...

I started taking the pile of 4. He took 2 from the 6-pile. I took 2 from the 3-pile (leaving (4,5,0,1)). He took 1 from the 4-pile. I took 3 from the 5-pile (leaving (3,2,0,1)). He took 1 from the 2-pile. I took 2 from the 3-pile. Mate in 2.

Not sure about general strategy here. I'll need to think awhile...

[BC]

It turns out that the only winning first moves are to take 4 from a pile. Any of the 4-pile, 5-pile, or 6-pile will work.

General Strategy: Make sure to either give him

1 stone in 1 pile
2 equal piles of size >= 2
4 piles in two equal pairs (with one pair of size >= 2)
3 piles of 1 stone each
0/1/2/3 Configuration
0/1/4/5 Configuration
0/2/4/6 Configuration
0/3/5/6 Configuration (Can do on first move)
1/2/5/6 Configuration
1/3/4/6 Configuration (Can do on first move)
2/3/4/5 Configuration (Can do on first move)

The proof is not simple, and I may have made a mistake, but I believe that

(a) He can not get from any of the above configurations to another in a single move, and

(b) From any configuration OTHER than those listed above, you can get to one of the above configurations.

Once you've given him one stone in one pile, the game is over.

[BC]

I thought about this a little more. Basically, simple NIM strategy works UNTIL there's only one pile with more than 1 stone in it. Using basic NIM strategy insures that YOU are the person to pick once that point is reached. At that point, you reduce that single pile to either 1 or 0 stones, depending on whether you want to TAKE the last stone or force your opponent to take the last stone.