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

[Prime]

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.

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

Take one stone from any pile.

Whatever move opponent makes, you can create another winning position. etc.

How, and the strategy for II, I'll leave for another poster.

[Prime]

Take one stone from any pile.

Whatever move opponent makes, you can create another winning position. etc.

How, and the strategy for II, I'll leave for another poster.

That is the correct first move. I'm assuming you are leaving it for other posters because you already know the solution.

[bonanova]

That is the correct first move. I'm assuming you are leaving it for other posters because you already know the solution.

It's a rather disjointed process.

[peace*out]

take a whole row

[Prime]

It's a rather disjointed process.

There is a short and simple formula that allows to determine correct move even with many rows and lots of coins in them. Deriving that formula is not easy.

take a whole row

Which one of the 3 rows?

[Guest]

Hello you guys , I also try to give a shot .

I. I take 2 coins from the first row, 4 coins from the second row , and 6 on the third row. On each move , the opponent is forced take the last coin on each row. Then I win.

II. we have N rows with A1, A2, ... , An.( in which Ai within 1 <= i <= n is the number of coins on the row i).

I have to count how many rows having only one coin. Assume that there are X rows having only one coin. If X is divisible by 2 , then the one who makes the first move always wins. Otherwise, he always loses.

Explanation : trying to leave one coin for those rows having more then one rows. Then you can figure out who will be the winner. That's my brief explanation.

[Prime]

Hello you guys , I also try to give a shot .

I. I take 2 coins from the first row, 4 coins from the second row , and 6 on the third row. On each move , the opponent is forced take the last coin on each row. Then I win.

II. we have N rows with A1, A2, ... , An.( in which Ai within 1 <= i <= n is the number of coins on the row i).

I have to count how many rows having only one coin. Assume that there are X rows having only one coin. If X is divisible by 2 , then the one who makes the first move always wins. Otherwise, he always loses.

Explanation : trying to leave one coin for those rows having more then one rows. Then you can figure out who will be the winner. That's my brief explanation.

Hello, Ntdo. Wellcome to the Den!

Your opponent on his/her move does not have to take coins from the same row as you.

I. The initial position was (3, 5, 7).

So when you take 2 coins from the first row leaving me (1, 5, 7),

I could take 3 coins from the third row, leaving you (1, 5, 4), for example.

II. Not that easy. Suppose, there were 2 rows with two coins in each. I'd say the player who moves from that position -- loses.

[Prime]

It’s been more than a week and no one could even solve Part I?! It is simply a matter of enumerating all lesser than (3,5,7) positions from which you lose, if it is your move.

It is perfectly understandable if no one solves Part II. Here I have a confession to make. I’ve tried to reconstruct the solution I found 20 some years ago, and I couldn’t. So, for now, I have the answer to Part II, but not a proof/derivation.

I could publish the answer to Part II, if there is an interest to this problem.

[Guest]

That is the correct first move. I'm assuming you are leaving it for other posters because you already know the solution.

If you go first and you take any number of coins from the row of 5 on your first move, you will lose against me everytime. . . Care to play?

[Prime]

If you go first and you take any number of coins from the row of 5 on your first move, you will lose against me everytime. . . Care to play?

I am game. My first move is taking 1 coin from the row of 5, leaving you with 3, 4, and 7. Your move.

[Guest]

I am game. My first move is taking 1 coin from the row of 5, leaving you with 3, 4, and 7. Your move.

For my first move, I will take 6 from the row of 7, leaving you with 3, 4 and 1. Your move.

[Guest]

For my first move, I will take 6 from the row of 7, leaving you with 3, 4 and 1. Your move.

Your second move will be to take 2 from the row of 4 and you will be able to force a win from then on. I guess I had to see it on screen before being able to see and accept the obvious.

Edited February 15, 2009 by T-Roe

[Guest]

i think i got the winning strategy, though i hav only tried it out in my mind so far

1) in ur mind see every row as, one for the opponent and rest for urself, this is equivalent to having every row with two coins

2) if u move first take all but last one from every row

3) if there are n rows there will be 2* n moves, and you being the first will force ur opponent being the last since there will be even number of moves.

i guess the formula is if u play first, leave behind an odd number of coins in the row u touch, if u are the second person to play, leave behing and even number of coins in the row u touch

can someone confirm this?

Edited February 15, 2009 by tarunark

[grey cells]

i think i got the winning strategy, though i hav only tried it out in my mind so far

1) in ur mind see every row as, one for the opponent and rest for urself, this is equivalent to having every row with two coins

2) if u move first take all but last one from every row

3) if there are n rows there will be 2* n moves, and you being the first will force ur opponent being the last since there will be even number of moves.

i guess the formula is if u play first, leave behind an odd number of coins in the row u touch, if u are the second person to play, leave behing and even number of coins in the row u touch

can someone confirm this?

If I am not misunderstanding the rules of the game, we are allowed to take any number of coins greater than zero from only one row at a single go, right?

EDIT: Added

[Prime]

i think i got the winning strategy, though i hav only tried it out in my mind so far

1) in ur mind see every row as, one for the opponent and rest for urself, this is equivalent to having every row with two coins

2) if u move first take all but last one from every row

3) if there are n rows there will be 2* n moves, and you being the first will force ur opponent being the last since there will be even number of moves.

i guess the formula is if u play first, leave behind an odd number of coins in the row u touch, if u are the second person to play, leave behing and even number of coins in the row u touch

can someone confirm this?

The first part of the puzzle is to figure out the {3,5,7} position (the winning path of moves). Then we can move on to figuring out the formula.

Your second point seems to imply that you can take coins from more than one row on a single move. That would be against the rules.

If I am not misunderstanding the rules of the game, we are allowed to take any number of coins greater than zero from only one row at a single go, right?

EDIT: Added

Exactly! A valid move is taking any greater than zero number of coins from one and only one row. To take coins from another row, a player must wait for the next turn.

[Prime]

Your second move will be to take 2 from the row of 4 and you will be able to force a win from then on. I guess I had to see it on screen before being able to see and accept the obvious.

So I see, you have figured out some of the key positions.

Namely...

{1,2,3}.

Whoever moves from that position -- loses.

I suppose, you can see all positions below that one. So, if you figure out all key positions above that one -- the Part 1 of the puzzle is solved.

Edited February 15, 2009 by Prime

[Guest]

So I see, you have figured out some of the key positions.

Namely...

{1,2,3}.

Whoever moves from that position -- loses.

I suppose, you can see all positions below that one. So, if you figure out all key positions above that one -- the Part 1 of the puzzle is solved.

All I can come up with for the {3,5,7} game at this point is to force my opponent to move from {1,2,3} or {0,n,n} where n > 1, or for me to move from {n,1,1} where n<>1.

I am really enjoying this puzzle - Thank you for posting it.

[Guest]

For part I, I think I've got all the "losing" positions:

(1,0,0)

(n,n,0) for n>1

(1,1,1)

(1,2,3)

(1,4,5)

(2,4,6)

(2,5,7)

(3,4,7)

(3,5,6)

Did I miss any?

For part II I am stumped, I can't find something simple that works all the time. Hmm.

For N rows, sum of rows 1 .. N-1 equals row N.

Works except for (1,1,1) and (3,5,6).

Is this even remotely in the right direction?

[Prime]

For part I, I think I've got all the "losing" positions:

(1,0,0)

(n,n,0) for n>1

(1,1,1)

(1,2,3)

(1,4,5)

(2,4,6)

(2,5,7)

(3,4,7)

(3,5,6)

Did I miss any?

That's all of them! Part 1 is now officially solved!

Also, partial credit to T-Roe and to bonanova.

For part II I am stumped, I can't find something simple that works all the time. Hmm.

For N rows, sum of rows 1 .. N-1 equals row N.

Works except for (1,1,1) and (3,5,6).

Is this even remotely in the right direction?

Part 2 is the most fun. And it is difficult.

[Guest]

That's all of them! Part 1 is now officially solved!

Also, partial credit to T-Roe and to bonanova.

Part 2 is the most fun. And it is difficult.

I love this game. Played it all the time in math class in high school.

Just wish I would've seen this post earlier before ya'll finished part I.

As for part II, I know it has something to do with

binary numbers

Is that right Prime?

[Guest]

For my 'guess' earlier, I have represented the number of remaining coins for each row in binary notation.

So far the only connection between all the "loser points" is keeping an even number of 1's on the board when in binary notation.

Am I on the right track here or way off base?

[Guest]

Am I on the right track here or way off base?

For my 'guess' earlier, I have represented the number of remaining coins for each row in binary notation.

So far the only connection between all the "loser points" is keeping an even number of 1's on the board when in binary notation.

Nevermind, that doesn't work because then {1,1,3} would have to be a loser situation.

Why do I get the feeling that this is going to bug me for weeks to come?

[Prime]

I love this game. Played it all the time in math class in high school.

Just wish I would've seen this post earlier before ya'll finished part I.

As for part II, I know it has something to do with

binary numbers

Is that right Prime?

That's a very strong hint. Indeed, the formula has to do with exactly that.

Let me change the rules of the game a little.

Instead of leaving the last coin for your opponent, you must take the last coin to win.

Interestingly, the key positions do not change. E.g., for the new rules {1,2,3} position is still lost for the player who has to move from it. Only those key positions are reversed, where there is not more than one row with more than one coin remaining. For example, {1,1,1} becomes a position from which you can force a win if it is your turn to move.

The reason for the rule change is to keep the formula consistent. With the old rules (win if your opponent takes the last coin), the formula for the key position works only while there are more than one row with more than one coin left. After that you just have to leave odd number of rows with one coin each to your opponent. With the new rules (one who takes the last coin -- wins), the formula for the key position works all the way to the end.

I suppose, this could be a hint too.

As I said earlier, I remember the formula, but forgot the derivation. So don't count on my help too much. I grew too lazy (perhaps, incapable) to duplicate the derivation/proof I did twenty some years ago. I would like someone else to do it and publish the proof here.

[Prime]

Nevermind, that doesn't work because then {1,1,3} would have to be a loser situation.

Why do I get the feeling that this is going to bug me for weeks to come?

See my previous post.