Coins on chess-board puzzle
in [Theory]
|
From: cplxphil on 17 Nov 2009 12:29 On Nov 17, 12:15 pm, gwo...(a)figipc78.tu-graz.ac.at (GJ Woeginger) wrote: > In comp.theory cplxphil <cplxp...(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/ Oh, that's very clever. What would happen if there were some number of bits that wasn't a power of 2 though? Would it still work? E.g. if the jailer adds a 65th coin, you are dealing with a situation where there are bits that can't be flipped. (I haven't really thought it through completely though.) -Phil
From: GJ Woeginger on 17 Nov 2009 13:01 In comp.theory cplxphil <cplxphil(a)gmail.com> wrote: # On Nov 17, 12:15??pm, gwo...(a)figipc78.tu-graz.ac.at (GJ Woeginger) # wrote: # > # > 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. # > # # Oh, that's very clever. What would happen if there were some number # of bits that wasn't a power of 2 though? Would it still work? E.g. # if the jailer adds a 65th coin, you are dealing with a situation where # there are bits that can't be flipped. (I haven't really thought it # through completely though.) No, it only works for powers of 2. For 65 coins, there would be 2^65 possible coin configurations that the SECOND prisoner can see, and each of these 2^65 configurations must uniquely communicate one of the 65 squares as the magic square to him. Let x denote the largest integer below (2^65)/65. By pigeon-hole, there exists some magic square M that corresponds to at most x of the 2^65 possible good configurations. Each of these x good configurations can be reached in at most 65 ways (from starting configuartions) by the FIRST prisoner. Since 65*x < 2^65, there exists some starting configuration that the FIRST prisoner cannot turn into any of these x good configurations. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Mark Brader on 17 Nov 2009 13:03 Quoted text is spoiler protection. Nicholas Nash writes: > 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'm assuming that if the first prisoner tried the obvious thing of placing the coin badly off-center on the magic square as he turns it over, the warden would disallow it. The primary images or lettering on a coin are typically designed to be viewed from a particular orientation, defining the "down" direction for that coin. The first prisoner should review the orientation of the 63 coins on the non-magic squares, then turn over the coin on the magic square, carefully choosing a particular orientation. The second prisoner should look for those coins whose "down" direction is pointing exactly along the grid lines of the chessboard. If there is only one such coin pointing in a particular direction, then that one marks the magic square. If there are two or more in each of the four possible directions, then he should try the same thing with the four possible diagonal directions. If that doesn't work, try the eight possible directions 22.5 degrees off the grid lines. Of course, this solution depends on the prisoners' ability to tell how accurately a coin is aligned by direction. So it's not ideal, but it should give a decent probability of success, provided that the warden doesn't touch the coins between the two prisoners' sessions. -- Mark Brader, Toronto | "I don't have a life; I have a program." --the Doctor msb(a)vex.net | (Michael Piller, Star Trek: Voyager, "Tattoo") My text in this article is in the public domain.
From: alexy on 17 Nov 2009 15:59 cplxphil <cplxphil(a)gmail.com> wrote: >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. Very nice, but this solution presumes something that is not given in the puzzle--numbering of the squares, or known orientation of the board. Without it, how can you tell, e.g., square (3,2) from square (6,7) (assuming rows and columns numbered 1-8)? I suspect that this is something that needs to be specified in the statement of the puzzle. One could either state that the chessboard squares are numbered, or that the chessboard is on a table, with its sides parallel to the walls of the rectangular room, and only one door to the room, at on of the corners (in which case the prisoners could agree that the corner closest to the door was (1,1)). -- Alex -- Replace "nospam" with "mail" to reply by email. Checked infrequently.
From: Mark Brader on 17 Nov 2009 16:32
G.J. Woeginger: > 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. Ooooh, elegant! -- Mark Brader, Toronto "I'm not a lawyer, but I'm pedantic and msb(a)vex.net that's just as good." -- D Gary Grady |