Author |
Topic: Penny game (Read 7505 times) |
|
titan
Newbie
Posts: 33
|
 |
Re: Penny game
« Reply #25 on: Oct 13th, 2013, 5:44am » |
 Quote  Modify
|
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!!
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Penny game
« Reply #27 on: Oct 13th, 2013, 8:04am » |
Quote Modify
|
on Oct 13th, 2013, 5:27am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
titan
Newbie
Posts: 33
|
|
Re: Penny game
« Reply #28 on: Oct 13th, 2013, 9:28am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Penny game
« Reply #29 on: Oct 13th, 2013, 10:02am » |
Quote Modify
|
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print