Coins on chess-board puzzle
in [Theory]
|
From: Nicholas Nash on 17 Nov 2009 06:47 Hi, I recently heard about a very nice puzzle with a computer science / TCS flavor. The person who told me it had found a solution, but the person who told them didn't even know if there was a solution. Here is the puzzle: ---- A room contains a normal 8×8 chess board together with 64 identical coins, each with one heads side and one tails side. Two prisoners are at the mercy of a typically eccentric jailer who has decided to play a game with them for their freedom. The rules are the game are as follows. The jailer will take one of the prisoners (let us call him the first prisoner) with him into the aforementioned room, leaving the second prisoner outside. Inside the room the jailer will place exactly one coin on each square of the chess board, choosing to show heads or tails as he sees fit (e.g. randomly). Having done this he will then choose one square of the chess board and declare to the first prisoner that this is the magic square. The first prisoner must then turn over exactly one of the coins and exit the room. After the first prisoner has left the room, the second prisoner is admitted. The jailer will ask him to identify the magic square. If he is able to do this, both prisoners will be granted their freedom. These rules are explained to both prisoners before the game begins and they are allowed some time together to discuss their strategy. Of course the question is: what strategy should the prisoners adopt? --- I have looked around, and I can't find any discussions of the problem other than the one written by the person who told me, here: http://ocfnash.wordpress.com/2009/10/31/yet-another-prisoner-puzzle/ Incidentally the preceding link has a full solution (and generalizations) so you might want to think about the puzzle first before reading it. I'd be grateful if someone can tell me if they've heard this before, or have an idea of its source. Regards, Nick
From: swp on 17 Nov 2009 07:00 On Nov 17, 6:47 am, Nicholas Nash <nicholas.n...(a)gmail.com> wrote: > Hi, > > I recently heard about a very nice puzzle with a computer science / > TCS flavor. > The person who told me it had found a solution, but the person who > told them didn't even know > if there was a solution. Here is the puzzle: > > ---- > > A room contains a normal 8×8 chess board together with 64 identical > coins, each with one heads side and one tails side. Two prisoners > are at the mercy of a typically eccentric jailer who has decided to > play a game with them for their freedom. The rules are the game are as > follows. > > The jailer will take one of the prisoners (let us call him the first > prisoner) with him into the aforementioned room, leaving the second > prisoner outside. Inside the room the jailer will place exactly one > coin on each square of the chess board, choosing to show heads or > tails as he sees fit (e.g. randomly). Having done this he will then > choose one square of the chess board and declare to the first prisoner > that this is the magic square. The first prisoner must then turn > over exactly one of the coins and exit the room. After the first > prisoner has left the room, the second prisoner is admitted. The > jailer will ask him to identify the magic square. If he is able to do > this, both prisoners will be granted their freedom. > > These rules are explained to both prisoners before the game begins and > they are allowed some time together to discuss their strategy. Of > course the question is: what strategy should the prisoners adopt? > > --- > > I have looked around, and I can't find any discussions of the problem > other than the one written by the person who told me, here: > > http://ocfnash.wordpress.com/2009/10/31/yet-another-prisoner-puzzle/ > > Incidentally the preceding link has a full solution (and > generalizations) so you might want to think about the puzzle first > before reading it. > > I'd be grateful if someone can tell me if they've heard this before, > or have an idea of its source. > > Regards, > > Nick bleed on the magic square a little, since the warden didn't believe in good oral hygene you should have plenty available on your gums. do it in a subtle manner. say it was magic after you are free. and don't forget to think outside of the box, lest you be put back in one. never heard this one before. swp
From: GJ Woeginger on 17 Nov 2009 10:19 In comp.theory Nicholas Nash <nicholas.nash(a)gmail.com> wrote: # # The jailer will take one of the prisoners (let us call him the ???first??? # prisoner) with him into the aforementioned room, leaving the second # prisoner outside. Inside the room the jailer will place exactly one # coin on each square of the chess board, choosing to show heads or # tails as he sees fit (e.g. randomly). Having done this he will then # choose one square of the chess board and declare to the first prisoner # that this is the ???magic??? square. The first prisoner must then turn # over exactly one of the coins and exit the room. After the first # prisoner has left the room, the second prisoner is admitted. The # jailer will ask him to identify the magic square. If he is able to do # this, both prisoners will be granted their freedom. # # These rules are explained to both prisoners before the game begins and # they are allowed some time together to discuss their strategy. Of # course the question is: what strategy should the prisoners adopt? # --- # # # I'd be grateful if someone can tell me if they've heard this before, # or have an idea of its source. It's just a standard puzzle from coding theory. For instance, it is discussed by Andy Liu in his article "Two applications of a Hamming code" in the January 2009 issue of Mathematics Magazine. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: cplxphil on 17 Nov 2009 11:46 On Nov 17, 6:47 am, Nicholas Nash <nicholas.n...(a)gmail.com> wrote: > Hi, > > I recently heard about a very nice puzzle with a computer science / > TCS flavor. > The person who told me it had found a solution, but the person who > told them didn't even know > if there was a solution. Here is the puzzle: > > ---- > > A room contains a normal 8×8 chess board together with 64 identical > coins, each with one heads side and one tails side. Two prisoners > are at the mercy of a typically eccentric jailer who has decided to > play a game with them for their freedom. The rules are the game are as > follows. > > The jailer will take one of the prisoners (let us call him the first > prisoner) with him into the aforementioned room, leaving the second > prisoner outside. Inside the room the jailer will place exactly one > coin on each square of the chess board, choosing to show heads or > tails as he sees fit (e.g. randomly). Having done this he will then > choose one square of the chess board and declare to the first prisoner > that this is the magic square. The first prisoner must then turn > over exactly one of the coins and exit the room. After the first > prisoner has left the room, the second prisoner is admitted. The > jailer will ask him to identify the magic square. If he is able to do > this, both prisoners will be granted their freedom. > > These rules are explained to both prisoners before the game begins and > they are allowed some time together to discuss their strategy. Of > course the question is: what strategy should the prisoners adopt? > > --- > > I have looked around, and I can't find any discussions of the problem > other than the one written by the person who told me, here: > > http://ocfnash.wordpress.com/2009/10/31/yet-another-prisoner-puzzle/ > > Incidentally the preceding link has a full solution (and > generalizations) so you might want to think about the puzzle first > before reading it. > > I'd be grateful if someone can tell me if they've heard this before, > or have an idea of its source. > > Regards, > > Nick Interesting puzzle. I haven't looked at the solution yet, but I had a question: Is the jailer required to put the coins out randomly, or can he choose to put them however he wants? Also, does the jailer have a particular interest in keeping them in jail--i.e., is it a zero- sum game? I've only thought about the problem for about a minute, but I would suspect that there's no way for the prisoners to guarantee a win to the game--particularly if the warden is actually plotting against them and can choose the coin sides deliberately and non-randomly. However, I am sure there is a way to maximize the odds of winning; this sounds vaguely game-theoretic in nature. -Phil
From: GJ Woeginger on 17 Nov 2009 12:15
In comp.theory cplxphil <cplxphil(a)gmail.com> wrote: # On Nov 17, 6:47??am, Nicholas Nash <nicholas.n...(a)gmail.com> wrote: # # Interesting puzzle. I haven't looked at the solution yet, but I had a # question: Is the jailer required to put the coins out randomly, or # can he choose to put them however he wants? But this does not really matter... Associate with each of the 64 squares/coins a unique 6-bit string. For an arbitrary configuration C of 64 coins, we denote by EXOR(C) the bit-wise EXOR of all the 6-bit strings whose coins show tails. Now the idea is to make EXOR(C) equal to the number of the magic square. This can be done by flipping the right bits in the EXOR of the starting configuration, which is easily reached by flipping the coin whose 6-bit string consists of the wrongly set bits. --Gerhard # I've only thought about the problem for about a minute, but I would # suspect that there's no way for the prisoners to guarantee a win to # the game--particularly if the warden is actually plotting against them # and can choose the coin sides deliberately and non-randomly. However, # I am sure there is a way to maximize the odds of winning; this sounds # vaguely game-theoretic in nature. # # -Phil ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/ |