wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Penny game
        
(Message started by: Garzahd on Nov 13^th, 2002, 4:15pm)

Title: Penny game
Post by Garzahd on Nov 13^th, 2002, 4:15pm

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.

Title: Re: New Puzzle: Penny game
Post by James Fingas on Nov 14^th, 2002, 7:28am

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? ;D

Title: Re: New Puzzle: Penny game
Post by TimMann on Nov 14^th, 2002, 1:13pm

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?

Title: Re: New Puzzle: Penny game
Post by Garzahd on Nov 14^th, 2002, 1:34pm

Your understanding is correct.

And yes, 8/7/5 is a different scenario but 10/7/5 is not.

Title: Re: New Puzzle: Penny game
Post by Chronos on Nov 15^th, 2002, 4:04pm

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.

Title: Re: New Puzzle: Penny game
Post by Icarus on Nov 15^th, 2002, 4:42pm

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.

Title: Re: New Puzzle: Penny game
Post by TimMann on Nov 15^th, 2002, 9:53pm

Yeah, I can name that classic in only three letters! ;)

Title: Re: New Puzzle: Penny game
Post by Pietro K.C. on Nov 16^th, 2002, 9:53am

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?

Title: Re: New Puzzle: Penny game
Post by TimMann on Nov 16^th, 2002, 12:10pm

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.

Title: Re: New Puzzle: Penny game
Post by Icarus on Nov 17^th, 2002, 7:04pm

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.

Title: NIM and the XOR function
Post by James Fingas on Nov 18^th, 2002, 8:45am

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.

Title: Re: New Puzzle: Penny game
Post by Icarus on Nov 18^th, 2002, 3:38pm

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.

Title: Re: New Puzzle: Penny game
Post by Garzahd on Nov 18^th, 2002, 3:48pm

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.

Title: Re: New Puzzle: Penny game
Post by TimMann on Nov 18^th, 2002, 10:55pm

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.

Title: Re: New Puzzle: Penny game
Post by HammerSandwich on Nov 20^th, 2002, 8:50am

Play online: http://www.cut-the-knot.com/recurrence/Northcott.shtml

Title: Re: New Puzzle: Penny game
Post by BNC on Dec 18^th, 2002, 12:00am

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.

Title: Re: New Puzzle: Penny game
Post by Icarus on Dec 18^th, 2002, 3:26pm

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!

Title: Re: New Puzzle: Penny game
Post by TimMann on Dec 31^st, 2002, 2:47am

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.

Title: Re: New Puzzle: Penny game
Post by Cyrus on Dec 31^st, 2002, 10:50am

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.

Title: Re: New Puzzle: Penny game
Post by James Fingas on Jan 2^nd, 2003, 9:12am

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.

Title: Re: New Puzzle: Penny game
Post by Cyrus on Jan 2^nd, 2003, 10:22am

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.

Title: Re: New Puzzle: Penny game
Post by James Fingas on Jan 2^nd, 2003, 2:15pm

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

Title: Re: New Puzzle: Penny game
Post by Icarus on Jan 5^th, 2003, 12:05pm

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. >:(

Title: Re: New Puzzle: Penny game
Post by TimMann on Jan 6^th, 2003, 2:12am

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.

Title: Re: Penny game
Post by yoyoy on Oct 13^th, 2013, 5:27am

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?

Title: Re: Penny game
Post by yoyoy on Oct 13^th, 2013, 5:44am

This point is not clear:
"From a position with nonzero XOR, you can always get to a position with zero XOR in one move."

say if 3 tracks were 3,5,3. Then using this:-

Row1 = 3= 1 x 2 + 1 x 1= 21
Row2 = 5 = 1 x 4 + 1 x 1= 41
Row3 = 3=1 x 2 + 1 x 1= 21
Total of UNPAIRED multiples= 101

Now, we can only remove pile from one track. But, here we need to remove piles from row1 and 3. So, we can't make a zero XOR by one move!!

Title: Re: Penny game
Post by towr on Oct 13^th, 2013, 7:55am

Sure you can, take everything from pile 2.

Title: Re: Penny game
Post by towr on Oct 13^th, 2013, 8:04am

on 10/13/13 at 05:27:03, yoyoy wrote:

Any invariant would work, where the invariant has one (set of) value(s) for losing positions and one (set of) value(s) for winning positions (i.e. it's a simplified characteristic of the game that tells you everything you need to know). XOR works because it is such an invariant.
In the end for the loser the XOR is 0, which is easy enough to see. If the XOR is zero at any point in the game, then any move you do changes it to something other than 0. Therefore if you can change the XOR to 0 from any non-zero value it means you will win, and as it happens that is the case.

Title: Re: Penny game
Post by yoyoy on Oct 13^th, 2013, 9:28am

Why are we using these 2 classifications of XOR, 0 or non-zero as win/loss?
Why not use say, XOR=5 meaning win and XOR!=5 is a loss?

Title: Re: Penny game
Post by towr on Oct 13^th, 2013, 10:02am

Because that doesn't correspond with what happens in the game. You lose when its your turn and all piles are 0, and the XOR of 0s is 0, not 5. So the end-state is pretty clear.
It is not immediately obvious that the same is true for intermediary game-states (that XOR of 0 is always a losing state and everything else winning), but you can prove that it fits this problem. You can always go from non-zero to zero, and never from zero to zero, so you can force your opponent to the losing end-state (which is 0).