[Prime]

This game is played at a bar sometimes. (By those patrons who lost all hope of picking up a date.)

Coins are arranged in 3 rows as following:

First row -- 3 coins;

Second row -- 5 coins;

Third row -- 7 coins.

Two players take turns to make their move. On your turn you must take any number of coins (more than zero) from one and only one row. Player who takes the last coin -- loses, and must buy the winner a drink.

I. Find the strategy forcing your win, if you move first.

II. For N rows (N >= 2), any number of coins in each row, find the formula for the winning strategy.

Or, to put it differently, find the formula for the winning (or losing) position on your move.

Computer programmers, jump in! I don't mean solving this problem by writing a program. Rather using relevant knowledge. Especially, for the part II.

[Guest]

I believe I am on to something for Part II thanks to the key positions provided by kgee and the hints provided by Little Miss Sally and Prime.

I converted all the digits in the key positions to binary and played around with them until I discovered that if you add them together, each column has an even number of 1's. For example, the key position {2,5,7} when converted to binary and added gives us 2 1's in each column:

2 ---> 0 1 0

5 ---> 1 0 1

7 ---> 1 1 1

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

1's -> 2 2 2

So, I wondered how a winning position such as {3,5,7} appears when converted to binary:

3 ---> 0 1 1

5 ---> 1 0 1

7 ---> 1 1 1

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

1's -> 2 2 3

It would appear that winning positions have at least 1 column with an odd # of 1's. Therefore, a player's move from this position would be to remove 1 coin from the row of 5, thus giving all the columns an even # of 1's:

3 ---> 0 1 1

4 ---> 1 0 0

7 ---> 1 1 1

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

1's -> 2 2 2

which is exactly what happened when I challenged Prime to a game (and lost of course).

[Prime]

I believe I am on to something for Part II thanks to the key positions provided by kgee and the hints provided by Little Miss Sally and Prime.

I converted all the digits in the key positions to binary and played around with them until I discovered that if you add them together, each column has an even number of 1's. For example, the key position {2,5,7} when converted to binary and added gives us 2 1's in each column:

2 ---> 0 1 0

5 ---> 1 0 1

7 ---> 1 1 1

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

1's -> 2 2 2

So, I wondered how a winning position such as {3,5,7} appears when converted to binary:

3 ---> 0 1 1

5 ---> 1 0 1

7 ---> 1 1 1

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

1's -> 2 2 3

It would appear that winning positions have at least 1 column with an odd # of 1's. Therefore, a player's move from this position would be to remove 1 coin from the row of 5, thus giving all the columns an even # of 1's:

3 ---> 0 1 1

4 ---> 1 0 0

7 ---> 1 1 1

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

1's -> 2 2 2

which is exactly what happened when I challenged Prime to a game (and lost of course).

That is the formula for a key position!

That simple operation has a name in Boolean Algebra and Computer Science.

The operation is called "Exclusive OR" (XOR). Sometimes, it is denoted as ⊕ (plus singn inside a circle). Typically, an assembly language would have an XOR instruction. Some high level languages, such as C, may also have a bit-wise XOR operation.

The truth table (definition) for XOR is

0 (+) 0 = 0

0 (+) 1 = 1

1 (+) 0 = 1

1 (+) 1 = 0

When you have more than two numbers to XOR, it comes down to odd number of 1s yielding 1 and even number of 1s yielding 0.

So back to our game.

Convert number of coins in each row to binary. Pad it with leading zeros to have the same number of digits in each number. Set the binary numbers one under another and perform XOR in each column. If the result is all zeros, then it is a key position. Whoever moves from it -- must lose (provided the opponent plays correctly.)

Example:

Suppose we had 4 rows with 3, 10, 11, and 13 coins respectively. Converting the numbers to binary and performing XOR, we get:

3: . . . 0 0 1 1

10: . . 1 0 1 0

11: . . 1 0 1 1

13: . . 1 1 0 1

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

. . . . . 1 1 1 1

In the above position each column has odd number of 1s. To make a winning move, we must ensure that the XOR operation on each column yields 0. (Leave even number of 1s in each column.) We must choose a row to work with and take a complement (reverse) of each digit in a non-zero column (in this case all four columns).

For example, we could work with the row of "10" (1010) converting it to 0101, or 5 in decimal. Or we could work with the row of "11" (1011) converting it to 0100, or 4 in decimal. Or we could convert the 13 (1101) into 0010, or 2 in decimal. But we couldn't touch the row of "3", because we'd have to make it into 1100, or 12 in decimal, which is greater than 3 and we cannot add coins.

Thus there is a choice of 3 winning moves in (3,10,11,13):

1). Taking 5 coins from the second row and leaving (3,5,11,13) to the opponent.

2). Or taking 7 from the third row, leaving (3,10,4,13).

3). Or taking 11 coins from the fourth row leaving (3,10,11,2).

We can verify that all of those 3 positions XOR to zero. Therefore, the opponent cannot obtain another "key position" on their move.

And so T-Roe has found the magic formula.

The derivation and proof are yet to be found. It could be a serious math/logic problem. I wouldn't spend all my free time on it. If someone finds it, I'll appreciate if they publish it here. If I stumble upon the proof again, I'll publish it then.

[EventHorizon]

...

And so T-Roe has found the magic formula.

The derivation and proof are yet to be found. It could be a serious math/logic problem. I wouldn't spend all my free time on it. If someone finds it, I'll appreciate if they publish it here. If I stumble upon the proof again, I'll publish it then.

I'm a bit late to the game, but here's a proof (for the modified game (take last stone to win))...

Let score(state) be the XORed binary representations a-la prime's formula.

Let score(state,row1) be score(state) if row "row1" was removed.

Let bin(row1) simply refer to the binary representation for the number of stones in row1.

I will start with two main lemmas (which are the bulk of the proof).

Lemma 1: If a player makes a valid move from state s1 for which score(s1)=0 to state s2, score(s2) != 0.

Proof: A move consists of modifying one row by removing stones. Therefore, only one row will be altered. Without loss of generality, let the row that the player will remove stones from be r1. By properties of xor, score(s1,r1) = score(s1) xor bin(r1). Since score(s1)=0, score(s1,r1)=bin(r1). The player removes at least one stone from r1 (call the modified row r2), which changes bin(r1) to bin(r2). Since at least one stone was removed, bin(r1) != bin(r2). Since bin(r1) != bin(r2), bin(r1) xor bin(r2) != 0.

score(s2) = score(s1,r1) xor bin(r2) = score(s1) xor bin(r1) xor bin(r2) = bin(r1) xor bin(r2) != 0.

Lemma 2: Let score(s1) != 0. There exists a valid move such that after performing it and reaching state s2, score(s2)=0.

Proof: First, find row r1 such that bin(r1) has a 1 in the most significant digit of the binary representation of score(s1). Such a row must exist since score(s1) has a 1 in that position and score(s1) is simply the xor of all the rows. Let r2 be the modified r1 after the player makes a move. As used above, we know score(s2) = score(s1,r1) xor bin(r2) = score(s1) xor bin(r1) xor bin(r2). If we find an r2 such that bin(r2)=score(s1) xor bin(r1), score(s2) = score(s1) xor bin(r1) xor bin(r2) = score(s1) xor bin(r1) xor score(s1) xor bin(r1) = (score(s1) xor score(s1)) xor (bin(r1) xor bin(r1)) = 0. So all that remains is to show that there is a valid move such that bin(r2)=score(s1) xor bin(r1).

Obviously, we will not need to modify any of the digits more significant than the most significant digit with a 1 in score(s1). r1 was chosen because it had a 1 in the most significant digit of score(s1). First, subtract enough stones such that the binary representation of r2 is all 0's for each digit less significant than the most significant digit of score(s1). Now, subtract one more stone from r2. score(s2) will now have a 0 in the place where score(s1) had a 1 (this ensures a 0 in that digit of score(s2)), and 1's for all lesser significant digits. Now we can simply remove the corresponding power of 2 for any digit that needs to change for bin(r2) to equal score(s1) xor bin(r1).

Theorem 1: Let s1 be the starting state of the game, and let score(s1) != 0. The first player to move (player 1) cannot lose if playing optimally.

Proof: By Lemma 2, there exists a move that player 1 can perform to result in a state s2 such that score(s2)=0. By Lemma 1, there is no valid move that player 2 can make such that score(s3)=0, where s3 is the state after player 2 makes a move from s2. Therefore, score(s3) != 0. By this same logic, after every move player 2 makes which results in state sX, score(sX) != 0. Since the final state (all stones removed) is one such that score(s_final)=0, player 2 cannot win. Since there cannot be a tie and player 2 cannot win, player 1 will win if playing optimally.

See any flaws/holes?

[Prime]

I'm a bit late to the game, but here's a proof (for the modified game (take last stone to win))...

Let score(state) be the XORed binary representations a-la prime's formula.

Let score(state,row1) be score(state) if row "row1" was removed.

Let bin(row1) simply refer to the binary representation for the number of stones in row1.

I will start with two main lemmas (which are the bulk of the proof).

Lemma 1: If a player makes a valid move from state s1 for which score(s1)=0 to state s2, score(s2) != 0.

Proof: A move consists of modifying one row by removing stones. Therefore, only one row will be altered. Without loss of generality, let the row that the player will remove stones from be r1. By properties of xor, score(s1,r1) = score(s1) xor bin(r1). Since score(s1)=0, score(s1,r1)=bin(r1). The player removes at least one stone from r1 (call the modified row r2), which changes bin(r1) to bin(r2). Since at least one stone was removed, bin(r1) != bin(r2). Since bin(r1) != bin(r2), bin(r1) xor bin(r2) != 0.

score(s2) = score(s1,r1) xor bin(r2) = score(s1) xor bin(r1) xor bin(r2) = bin(r1) xor bin(r2) != 0.

Lemma 2: Let score(s1) != 0. There exists a valid move such that after performing it and reaching state s2, score(s2)=0.

Proof: First, find row r1 such that bin(r1) has a 1 in the most significant digit of the binary representation of score(s1). Such a row must exist since score(s1) has a 1 in that position and score(s1) is simply the xor of all the rows. Let r2 be the modified r1 after the player makes a move. As used above, we know score(s2) = score(s1,r1) xor bin(r2) = score(s1) xor bin(r1) xor bin(r2). If we find an r2 such that bin(r2)=score(s1) xor bin(r1), score(s2) = score(s1) xor bin(r1) xor bin(r2) = score(s1) xor bin(r1) xor score(s1) xor bin(r1) = (score(s1) xor score(s1)) xor (bin(r1) xor bin(r1)) = 0. So all that remains is to show that there is a valid move such that bin(r2)=score(s1) xor bin(r1).

Obviously, we will not need to modify any of the digits more significant than the most significant digit with a 1 in score(s1). r1 was chosen because it had a 1 in the most significant digit of score(s1). First, subtract enough stones such that the binary representation of r2 is all 0's for each digit less significant than the most significant digit of score(s1). Now, subtract one more stone from r2. score(s2) will now have a 0 in the place where score(s1) had a 1 (this ensures a 0 in that digit of score(s2)), and 1's for all lesser significant digits. Now we can simply remove the corresponding power of 2 for any digit that needs to change for bin(r2) to equal score(s1) xor bin(r1).

Theorem 1: Let s1 be the starting state of the game, and let score(s1) != 0. The first player to move (player 1) cannot lose if playing optimally.

Proof: By Lemma 2, there exists a move that player 1 can perform to result in a state s2 such that score(s2)=0. By Lemma 1, there is no valid move that player 2 can make such that score(s3)=0, where s3 is the state after player 2 makes a move from s2. Therefore, score(s3) != 0. By this same logic, after every move player 2 makes which results in state sX, score(sX) != 0. Since the final state (all stones removed) is one such that score(s_final)=0, player 2 cannot win. Since there cannot be a tie and player 2 cannot win, player 1 will win if playing optimally.

See any flaws/holes?

The lemmas are fine. But where is the proof that the losing positions must be those that XOR to zero?

Yes there is a set of losing (key) positions. And it is must be so that you cannot obtain one key position from another with a single move. And it must be so that you can always obtain a key position with a single move from any non-key position. Both points demonstrated formally in your lemmas.

But why those key positions XOR to zero? Is that the only possible formula that allows the above two conditions?

I recall, back when I found the winning strategy for a general case, I described it in terms of powers of 2 somehow. Then I took a second look and noticed, it was XOR.

[bonanova]

This game is played at a bar sometimes. (By those patrons who lost all hope of picking up a date.)

Coins are arranged in 3 rows as following:

First row -- 3 coins;

Second row -- 5 coins;

Third row -- 7 coins.

Two players take turns to make their move. On your turn you must take any number of coins (more than zero) from one and only one row. Player who takes the last coin -- loses, and must buy the winner a drink.

I. Find the strategy forcing your win, if you move first.

II. For N rows (N >= 2), any number of coins in each row, find the formula for the winning strategy.

Or, to put it differently, find the formula for the winning (or losing) position on your move.

Computer programmers, jump in! I don't mean solving this problem by writing a program. Rather using relevant knowledge. Especially, for the part II.

The last player can be said to win [normal game] or to lose [misere game].

The strategies are complementary and involve what is called the nim-sum, from the game's name.

Analysis and variations can be found here and elsewhere: google nim.

I didn't want to simply parrot from this link until discussion had run its course, so I only hinted in my first post.

I ran into nim in college and could not master it.

Hat's off to Prime for having done so.

[Prime]

The last player can be said to win [normal game] or to lose [misere game].

The strategies are complementary and involve what is called the nim-sum, from the game's name.

Analysis and variations can be found here and elsewhere: google nim.

I didn't want to simply parrot from this link until discussion had run its course, so I only hinted in my first post.

I ran into nim in college and could not master it.

Hat's off to Prime for having done so.

Thanks, Bonanova. I knew, there must have been a description/mathematical treatment of that game somewhere.

However, I don’t see a proof in the article in the Wikipedia you referred to, let alone the derivation of the formula. The article simply states, “The theorem follows by induction on the length of the game from these two lemmata.” Then it shows two lemmas, similar to those in EH’s proof. Basically, they boil down to:

1. You cannot obtain one losing position from another with a single move.

2. You can always create a losing position (for your opponent) with a single move from a non-losing position.

We have evidence that some losing positions conform to zero-XOR formula. But, where is that induction showing that all losing positions must?

It is like saying:

1. The winning strategy must have those two properties: A and B.

2. XOR formula conforms to those two A and B properties.

3. We know of some positions that conform to XOR formula.

4. Therefore, XOR must be it.

I disagree with the conclusion (4). The only conclusion that we can draw here is: XOR could be it. But that’s not a proof. Furthermore, the article (inadvertently) gives an example that the purported proof is not really a proof. That example is the misere variation of the game (the same one I gave in the OP, where whoever takes the last coin -- loses). In that variation, the winning strategy conforms to the XOR formula to a certain point in the game, then it stops conforming to that formula and switches to another formula altogether. That would break the induction, wouldn’t it?

I say, it is a commonplace occurrence with those types of proofs where you put the carriage before the horse. First, let’s introduce the winning formula out of nowhere, then let’s prove that it is. The derivation of the formula is not shown in the article, and, therefore, the understanding of it is missing.

I, suppose, if I check the references further (now that I know the proper name of that game), I may find a real proof/derivation I am looking for. From my own derivation of the formula twenty some years ago, I vaguely recall tables filled with numbers, some kind of rotational symmetry in those tables, and interrelations between numbers of rows and numbers of coins in them.

Edited February 26, 2009 by Prime

[EventHorizon]

I have a personal history with this game.

Long time ago, in a land far, far away...

It was sometime in 1984-85. I worked as a computer programmer at a large company in the suburbs of Chicago. A coworker showed the game to me. We played a few rounds and he won every time. Satisfied with putting me into my place, he said: "It will take you a few days to figure out." Being so prodded, I went to lunch and upon return demonstrated to my challenger that I could win every game if I moved first. The man was duly impressed. Still, not satisfied, I spent the remainder of the work day and the entire evening looking for a general formula for the game.

Next morning at work, I wrote a program using CLIST (command language on IBM Mainframe), which played the game with up to 5 rows, up to 25 letters "I" in each. I called the game "Eyes". So simple the equation was, the program came out only a few lines long. I had to obscure the formula with mounds of junk code calculating the labels to which to branch. Then I added a random number generator which picked annoying messages written in poor English (such as I had) from a file and displayed them to tease the opponent. Such comments as: "Computer mind is superior to human because it is binary and human is singular!"

I think I managed to alienate a significant number of coworkers, including some of my superiors up to the Director of Data Processing Department. Several times I was accused of writing an unfair game, with no winning possibility. But the game was fair. After setting up a random position, the “Eyes” offered the opponent to choose who moves first. I demonstrated to my colleagues that I could win against the computer every time.

I lasted another year or so at that place. And no one had solved the game in all that time. On the day of my departure, I stopped by the Data Processing Director's office to say good bye. The Director barely turned to wish me good luck. He then hunched his shoulders over his computer terminal shielding the screen from my sight. But I managed to spot a loosing position of "Eyes" on it, anyway.

Finally read post #2. That's awesome.

As for the proof. I suppose I will let wikipedia handle it. Though if I come up with a surprisingly simple/intuitive reason for xor, I'll post it.

[EventHorizon]

Finally read post #2. That's awesome.

As for the proof. I suppose I will let wikipedia handle it. Though if I come up with a surprisingly simple/intuitive reason for xor, I'll post it.

Oops, didn't see Primes last post before posting my last post. Guess that's the problem with opening tabs and ignoring web pages for a while.

So wikipedia also only proved that it works, and didn't show why xor works. I guess it's good to know that wikipedia didn't have a significantly better proof (at least one with a derivation of the magic formula).

Edited February 26, 2009 by EventHorizon

[Prime]

Having googled the “Nim game theory”, I came across a paper that proves the XOR formula. For our version of the game, you need to read just the first 12 pages. The actual proof is presented on pages 10 - 11, which one cannot understand, unless they paid due attention to the preceding definitions and lemmas. (It is especially important to understand the concept of equivalency.) So it takes a bit of effort to get through. But the proof by induction looks solid. Still it kind of pulls the powers of 2 out of the sleeve.

There are some things in that paper that I can translate into non-mathematical terms, and which may be helpful for deriving the XOR strategy for this game without going into all that formal math.

Here are some of those peculiarities of the game:

1. Combining two losing positions gives another losing position. The losing position is the one where the player whose move it is -- loses, if the opponent plays correctly. For example, you can combine two losing positions like (2,2) and (1,2,3) into (2,2,1,2,3) which is also losing. The player who moves first will be taking coins from a row which belonged to either the first, or the second position; so the player who moves second can always play within that same position keeping it losing until the last coin of it is taken.

2. Combining a losing position with a winning position always yields a winning position. That is because the player who moves first can always make a move inside the winning position thus leaving to his opponent a combination of two losing positions, which is also losing as shown in the previous point.

3. Combining two identical positions will always produce a losing position. That is because the player who moves second can always copy the first player’s moves in the other position.