Author |
Topic: Penny game (Read 7498 times) |
|
Garzahd
Junior Member
Gender: 
Posts: 130
|
There are three one-dimensional tracks, of length 12, 7, and 5 spaces respectively. You start with pennies in the first space of each track; your opponent starts with pennies in the last space of each track. On your turn, you may move any one of your pennies any number of spaces in either direction along a track (as a chess rook), however you are not permitted to bypass the other player's penny or occupy its space. If a player has no legal move, he loses.
What should your first move be?
Hardcore puzzlers will probably solve this immediately, but newer people might take quite some time. For the newer people, the solution to this is a useful trick to have in your random-puzzle-solving arsenal. As a sub-problem, you may want to try solving it without the 5-length track.
|
| « Last Edit: Oct 23rd, 2003, 8:13pm by Icarus » |
 IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
 |
Re: New Puzzle: Penny game
« Reply #1 on: Nov 14th, 2002, 7:28am » |
 Quote  Modify
|
This is a very interesting puzzle. I highly recommend it to anyone!
Here's an interesting one: what is the winning strategy if the track lengths are 10,7, and 5? 
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New Puzzle: Penny game
« Reply #2 on: Nov 14th, 2002, 1:13pm » |
Quote Modify
|
I don't see what's particularly interesting about 10, 7, and 5 as lengths. But what if the lengths are 8, 7, and 5?
By the way, to check my understanding, if the track is length 10, that means that there are initially 8 empty spaces between the pennies. Right?
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: New Puzzle: Penny game
« Reply #3 on: Nov 14th, 2002, 1:34pm » |
Quote Modify
|
Your understanding is correct.
And yes, 8/7/5 is a different scenario but 10/7/5 is not.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: New Puzzle: Penny game
« Reply #4 on: Nov 15th, 2002, 4:04pm » |
Quote Modify
|
Maybe I'm not hardcore enough, but the solution wasn't obvious to me. For two tracks, though, it is: Player 2 can force a win if the tracks are the same length, and Player 1 can force a win if they're not. I'm not sure how this relates to the three-track version, though, aside from indicating some moves not to make.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Penny game
« Reply #5 on: Nov 15th, 2002, 4:42pm » |
Quote Modify
|
The reason a lot of hard-core puzzlers will get this is because it is a classic in disguise. Penetrate the disguise, and the solution is well-known.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New Puzzle: Penny game
« Reply #6 on: Nov 15th, 2002, 9:53pm » |
Quote Modify
|
Yeah, I can name that classic in only three letters! 
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: New Puzzle: Penny game
« Reply #7 on: Nov 16th, 2002, 9:53am » |
Quote Modify
|
Whoa! This is one seriously cool puzzle! I as well took some time in figuring it out, but to me it was much easier to solve 8/7/5 from 12/7/5 than solving 12/7/5 in the first place!
And I have NO idea what the three-letter classic is. I mean, not a clue. I can't even Google this hint.  Is it "Go!" ? Is "!" a letter? Does the oriental game of Go really end in an exclamation mark? Is it at all like this? I've never played it.
Anyways, my approaches were (you can highlight the first few lines without much fear of spoilage, as I will just talk about some of my first unsuccessful attempts):
The first idea was to block one of the pieces outright. You know, just pick one track and move your piece the farthest it can go. So, in trying to prove that this was a winning strategy, my thoughts naturally turned to the 2-track scenario, and I started trying to figure out a way for the 2nd player to insure victory.
It turns out there is such a way. I came across it in trying to apply one of the Great Principles of Game-Oriented-Riddle-Solving: imitate what the other guy does. This works in the Faustian Round Table Coin Game, and in many other examples, though I can't remember them now.
At first, I thought of imitating the other guy's movement in the same track where the movement was performed. This though lasted for about a second, because it is clearly not realizable all the time. Darn, if only there was some other place to imitate... wait! The other track! A-ha!
So it was that the imitating idea came into fruition: If there are two tracks, of lengths a,b, of which a is the larger, then player 1 can force a win. He just needs to move his penny in track a so as to leave the same number of empty spaces between the coins in that track as there are in track b (namely, b-2). In the following moves, he lets track a simulate b, and vice-versa, in the obvious way: what player 2 does in track b, player 1 does in a with his own penny, and also the other way around. So, when player 2 makes movement in one track impossible for player 1, in the following round, player 1 will do the same for player 2, and therefore win.
So the "nullify a track outright" strategy sucks. It would work only if there were two tracks of the same size. The next challenge, then, was to adapt the foregoing result to the three-track case. I admit I was stumped for a good ten minutes, trying out different variations in my head. It had stricken me as odd that the sum of the size of the two smaller tracks was the size of the larger, but I was reluctant to use that. Finally, I caved and gave it some serious thought.
It was pretty natural, by now, to use the larger track to simulate both the smaller tracks by the larger one. The idea was to keep the number of spaces between the pennies in track 12 as the sum of the spaces between the pennies in tracks 7 and 5. So the strategy is: every time player two moves his penny in tracks 7 or 5, make the corresponding move in track 12. If player 2 moves his penny in track 12, pick one of tracks 7 or 5 and move your penny in the same way. This idea needs a setup, which should be your first move: place your track 12 coin in square 3, so that there are 10 free squares between you and your opponent.
This works because, when some penny in tracks 7 or 5 is no longer able to move, the number of free spaces between them is zero; therefore, in the next round, you, player 1, in making the corresponding move in track 12, reduce the problem to the previously treated case, namely, of two tracks with the same number of free spaces between the pennies. However, if player 2's move reduces the number of free spaces between pennies in track 12 to zero, you, in your following move, do the same to some penny in another track, and, by construction, the two pennies in the third track are already in this situation.
I have been a bit sloppy in the above argument, regarding backward movements and different track sizes, but there are no holes that can't be fixed with a little thought on the reader's part. I think. All you have to do is notice that, when player X, by some move in track Y, reduces the number of free spaces between pennies to zero, he has guaranteed victory in that track, and without affecting his performance on other tracks. How might he do that?
So I propose the following extension: for what positive integers a,b,c can player 1 force a win if the track lengths are a/b/c?
|
| « Last Edit: Nov 16th, 2002, 11:35am by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New Puzzle: Penny game
« Reply #8 on: Nov 16th, 2002, 12:10pm » |
Quote Modify
|
About the name: "go" has two letters and bears no resemblance to this game. The three-letter game name I was referring to is nim.
About the strategy: Pietro is right about the 2-track case, but goes badly wrong after that. I don't just mean the minor slipup that 5 + 3 = 8, not 10; the whole strategy of keeping the number of spaces left in the longest track equal to the sum of the spaces in the other two will not work.
This is a hard problem if you haven't seen the solution to nim before. Don't expect to get it in 10 minutes. Once you do get it, the generalization to longer tracks and more tracks should be included in your solution.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Penny game
« Reply #9 on: Nov 17th, 2002, 7:04pm » |
Quote Modify
|
I agree with Tim. If you don't know the trick for the classic game, then this is definitely a hard problem to figure out. Here is one place that Pietro's solution fails: On Player 2's first turn he moves his track 12 penny forward 7 positions. This does not finish off that track, and it cannot be matched on either of the other tracks. One thing that Pietro is correct on: The winning strategy is more easily expressed in terms of the number of empty spaces rather than the overall track length.
Note that in the general game, with track lengths of x, y, z, some starting positions are Player 1 wins and some are Player 2 wins. Player 1's strategy is always to move to a "Player 2 win" position, since at the start of Player 2's turn, he is effectively the new "Player 2". So to solve this, what you really need to figure out which positions are Player 2 wins, and which are Player 1 wins.
Here is a discription of the classic game and how this is the same game in disguise:
Nim is played with 3 piles of counters. Each turn, the player can take as many counters as he wants from one pile. The player who takes the last counter is the winner. In this case the counters are the empty spaces between the pennies. The players remove counters by moving their pennies forward. By the way Nim is not just "a" classic game, it is "the" classic game of Game Theory. The game that is always the prime example discussed when one studies the field. It can be played with more than 3 piles, but the solution for 3 piles easily generalizes.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
NIM and the XOR function
« Reply #10 on: Nov 18th, 2002, 8:45am » |
Quote Modify
|
See, I never played NIM, and when I posted that 10,7,5 thing, I obviously hadn't worked out the correct solution. I had worked out the following instead:
<WRONG>: If you can express one track's spaces-left as the sum of the spaces-left on the other two tracks, then you are in a winning position.
This of course isn't quite right, but for small values it works. I eventually did a breadth-first search of the 3d position space to find the winning combinations and came up with the very interesting relation between the three track lengths for winning combinations that I won't bother to share with you now because I don't really know how to prove it. It's really very interesting--not at all what I was expecting!
Of course it's the same as NIM--the only difference is that here you have the option to sometimes add spaces instead of always taking them away. However, if you're in a losing position, then adding spaces never helps, because the winner can take away any number of spaces you can add. And if you're in a winning position, you never need to add spaces to remain in a winning position. Hence a solution for NIM will work here too.
|
| « Last Edit: Nov 18th, 2002, 8:45am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Penny game
« Reply #11 on: Nov 18th, 2002, 3:38pm » |
Quote Modify
|
Yeah, I had missed that you are allowed to back the pennies up. So this game is not an exact equivalent to NIM, but as James points out, the only thing backing the pennies up does is delay the inevitable outcome. If you were allowed to back the penny up beyond its start position, then Player 2 can delay his loss indefinitely, effectively creating a draw, but he still cannot win.
The condition for a winning position is a bit suprising, but it is not that hard to prove once you know it.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: New Puzzle: Penny game
« Reply #12 on: Nov 18th, 2002, 3:48pm » |
Quote Modify
|
Been away for a couple days, so just updated myself on the thread now....
Yes, the game is Nim in disguise. The solution to Nim is as follows (proof left as an exercise to the googler):
Express each "pile" in binary. As stated before, tracks of 12/7/5 correspond to empty spaces of 10/5/3. In binary, these are 1010, 0101, 0011. A winning move in Nim is one such that after your turn, the XOR of all piles is zero; that is, each power of two occurs an even number of times across all piles. In this particular instance, the correct answer is to reduce the 10 to 6 (110 in binary), leaving the result 110/101/011. Any move your opponent does must upset the XOR balance somehow, since he's forced to remove or add at least one space to one track.
From here, it's pretty clear that the answer to the two-track problem is to make the two tracks the same length.
|
| « Last Edit: Nov 18th, 2002, 3:48pm by Garzahd » |
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New Puzzle: Penny game
« Reply #13 on: Nov 18th, 2002, 10:55pm » |
Quote Modify
|
Garzahd already has most of the proof there. Here's something to fill in the remaining gap:
(1) The position after you've just made the final move and won has an XOR of 0. Obvious.
(2) From a position with nonzero XOR, you can always get to a position with zero XOR in one move. This is pretty easy to see. Let the XOR of all piles be T, and consider the leftmost 1 bit of T. At least one pile must be of a size S that has 1 in that position; if none did, T would have a 0 there. Therefore if you take S XOR T, this will clear that bit of S and not change any bits to the left, so S XOR T < S. Thus reducing this pile from size S to size S XOR T is a legal move. Doing so changes the XOR of all piles to T XOR T = 0.
So to sum up, once player A makes a move that leaves the XOR of all piles at 0, player B cannot make a move that preserves that condition, but A can always restore the condition after player B's move. As Icarus points out, the piles inevitably grow smaller (despite the losing player's ability to back up to a limited extent in the penny game variant), so eventually the game terminates and A wins. If the initial position already has an XOR of 0, the first player is put in B's position and loses.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
BNC
Guest
|
|
Re: New Puzzle: Penny game
« Reply #15 on: Dec 18th, 2002, 12:00am » |
Quote Modify
 Remove
|
Hi,
A total newbi here.
I was wandering: is there a way to solve a “reversed” NIM game? That is, you want a other guy to take the last bit.
I can’t seem to come with a solution.
Any ideas are welcomed.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Penny game
« Reply #16 on: Dec 18th, 2002, 3:26pm » |
Quote Modify
|
The last I heard, which has been ~15 years ago, Reverse Nim was an unsolved problem (in general - for small starting positions solutions are known), so you are hardly alone in not being able to come up with a solution!
|
| « Last Edit: Dec 18th, 2002, 3:26pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New Puzzle: Penny game
« Reply #17 on: Dec 31st, 2002, 2:47am » |
Quote Modify
|
The misere form of Nim (where you lose by taking the last counter) has almost the same solution as the forward form. The winning strategy is to leave a position where either (1) at least one pile has more than 1 counter left, and the XOR of all the pile sizes is 0, or (2) an odd number of piles have 1 counter left, and the rest have 0. The only tricky bit is transitioning from (1) to (2). If normal Nim strategy would call for you to move for the first time to a position where all nonempty piles have only 1 counter left, it would have you leave an even number of such piles, which is a losing move in misere Nim. But you can instead leave an odd number of piles of 1 counter by taking either one more or one less counter from the pile (of size > 1 by hypothesis) than forward Nim would call for.
The misere form of the Penny Game maps to the misere form of Nim in the same way the forward forms map. I.e., if the losing player makes a legal Nim move, the winner makes the Nim response; if the losing player "adds N counters to a pile" by moving his penny backward, the winning player moves his penny N spaces forward on the same track. The latter type of move/response pair leaves the position unchanged when viewed as a Nim position, but it can't result in the game failing to terminate, because the winning player always moves forward.
|
| « Last Edit: Dec 31st, 2002, 3:19am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Cyrus
Newbie
Gender:
Posts: 27
|
|
Re: New Puzzle: Penny game
« Reply #18 on: Dec 31st, 2002, 10:50am » |
Quote Modify
|
Yikes. This one is tough. I thought the same way at Pietro. And maybe I don't understand how it doesn't work. Assuming I move my track 12 coin forward 2 spaces leaving 8 open spaces in track 12 and a combined 8 spaces in tracks 7 and 5. Then what would player 2 do to mess me up?
I don't really understand how binary and this XOR work. So maybe I need to learn that before I'll be able to understand this.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New Puzzle: Penny game
« Reply #19 on: Jan 2nd, 2003, 9:12am » |
Quote Modify
|
Cyrus,
When we say the XOR of three number is zero, then we mean:
1) let the numbers be X, Y and Z. Now express the numbers in binary form. Example:
X = 0000 1011
Y = 0100 0010
Z = 0100 1001
2) The XOR we're talking about is the bit-wise XOR function, where we compute the XOR of each bit separately. In this example, the bitwise XOR of the three numbers is indeed zero.
3) Note that a three-way XOR function is the same as XORing the first two numbers, and then XORing the result with the third number.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Cyrus
Newbie
Gender:
Posts: 27
|
|
Re: New Puzzle: Penny game
« Reply #20 on: Jan 2nd, 2003, 10:22am » |
Quote Modify
|
I see. Makes perfect sense. Thanks James. And I see how this works.
But could someone post an example where Pietro's solution does not work.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New Puzzle: Penny game
« Reply #21 on: Jan 2nd, 2003, 2:15pm » |
Quote Modify
|
The original move I gave, 10-7-5, which I believe follows Pietro's solution (which I think is the same as my original solution now that I look at it again). After you do this, the spaces between the pennies are 8, 5, and 3. This satisfies Pietro's condition because 8 = 5 + 3, but it doesn't satisfy the XOR condition:
1000 xor
0101 xor
0011
=
1100
If you played this way, your opponent could just move the 12-row penny forward by 2 to get the situation 8-7-5 (which is a winning position).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Penny game
« Reply #22 on: Jan 5th, 2003, 12:05pm » |
Quote Modify
|
Thanks for the info on misere NIM, Tim. Now my personal puzzle is to figure out if my memory is bad, my information 15 years ago was bad, or was this only discovered in the last 15 years?
Since I couldn't even remember that "misere" is the correct word for the reverse game, I'm betting it's the first. 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: New Puzzle: Penny game
« Reply #23 on: Jan 6th, 2003, 2:12am » |
Quote Modify
|
I'm sure the solution to the misere form of Nim has been known for ages. I had a plastic 3/5/7 Nim game when I was in grade school over 30 years ago and knew the solution to both forms -- I probably read it in a Martin Gardner book. Hmm, or maybe my older brother explained it to me.
Hmm (looks in closet)...My gosh, I still have that game in the box of math puzzles in my closet, along with my Soma cube, Rubik's cube, etc.
Anyway, I'm guessing that you were thinking of some other game where the misere form is much harder than the normal form. I recall reading that there are some games like that, but I don't remember any examples.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
titan
Newbie
Posts: 33
|
|
Re: Penny game
« Reply #24 on: Oct 13th, 2013, 5:27am » |
Quote Modify
|
I have understood what Nim is and hence this problem. Nim:- http://www.archimedes-lab.org/How_to_Solve/Win_at_Nim.html
But, why are we using xor and why not anything else to solve the actual Nim problem? Why should this strategy give us a right solution? Why does it work?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print