Coins on chess-board puzzle
in [Theory]
|
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen on 18 Nov 2009 07:48 Nicholas Nash <nicholas.nash(a)gmail.com> writes: > 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? Gerhard already gave the solution to this, so I will instead give a similar (but harder) puzzle: There are 50 prisoners and one jailer. You can assume that the prisoners have been jailed together for a while, so they know each other by name and face. The jailer has photos of all 50 prisoners, which he will lay out randomly face down in a row on a table. Now, each prisoner will in turn be called in and be allowed to turn over 25 photos. When he has done so, he is led to another room and the jailer will turn over the face-up photos again (without altering their order) so all are face-down again. He then calls in the next prisoner and repeats the procedure untill all prisoners are moved into the other room. If _all_ 50 prisoners saw their own photo as one of the 25 they flipped over, they are all set free, but if just a single prisoner doesn't see his own photo, thet are all executed. The prisoners will be told about the procedure beforehand and can agree on a strategy, but once the procedure starts, they can not communicate. What strategy can the prisoners use to maximize their survival chance, and how big can they make this chance? Torben
From: Paul Hunter on 18 Nov 2009 10:58 GJ Woeginger wrote: > 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. You can do it for one less than powers of 2 if the first prisoner is able to choose to not flip a coin (the choice of not flipping corresponding to flipping the coin with bit string 0)
From: Tim Little on 19 Nov 2009 23:05 On 2009-11-18, Torben Ægidius Mogensen <torbenm(a)pc-003.diku.dk> wrote: > The prisoners will be told about the procedure beforehand and can agree > on a strategy, but once the procedure starts, they can not communicate. > > What strategy can the prisoners use to maximize their survival chance, > and how big can they make this chance? When you say that prisoners can turn over 25 cards, can they re-order the cards they turn over or must the cards be turned over in place? - Tim
From: Risto Lankinen on 20 Nov 2009 02:22 On 18 marras, 14:48, torb...(a)pc-003.diku.dk (Torben Ægidius Mogensen) wrote: > > There are 50 prisoners and one jailer. You can assume that the > prisoners have been jailed together for a while, so they know each other > by name and face. Assuming all names are unique they are easily indexed with a running number. > The jailer has photos of all 50 prisoners, which he will lay out > randomly face down in a row on a table. Again, row positions are easily indexed with a number. > Now, each prisoner will in turn be called in and be allowed to turn over > 25 photos. When he has done so, he is led to another room and the > jailer will turn over the face-up photos again (without altering their > order) so all are face-down again. He then calls in the next prisoner > and repeats the procedure untill all prisoners are moved into the other > room. Each row position R has the picture of prisoner P. Each prisoner starts by revealing the picture having their own index i.e. R = P. If he finds his own picture, OK; else he next opens the picture having the index of the prisoner portrayed by the previously opened one. This he repeates until he finds his own picture or hits the limit of 25 attempts. > If _all_ 50 prisoners saw their own photo as one of the 25 they flipped > over, they are all set free, but if just a single prisoner doesn't see > his own photo, thet are all executed. The probability of success is equal to the probability of the picture arrangement having a displacement loop at most 25 nodes. Intuitively this is about 1/2 . N.B. if the prisoners are worried about jailer deliberately arranging the pictures against their success, they should simply randomize their indexes before "playing". - Risto -
From: Tim Little on 20 Nov 2009 03:08
On 2009-11-20, Risto Lankinen <rlankine(a)gmail.com> wrote: > If he finds his own picture, OK; else he next opens the picture > having the index of the prisoner portrayed by the previously opened > one. Nicely done. His number will always be part of some cycle. If the cycle length is 25 or less, he succeeds. Every prisoner has an individual 50% chance of success, but their chances are very much correlated. > The probability of success is equal to the probability of the > picture arrangement having a displacement loop at most 25 nodes. > Intuitively this is about 1/2 . The probability of a permutation of size n having a cycle of length exactly k is 1/k (for k > n/2). So the probability of an overall success is about 31.7%. If the permutation has a cycle of length k > 25, then exactly k prisoners fail to find their own photo. > N.B. if the prisoners are worried about jailer deliberately > arranging the pictures against their success, they should simply > randomize their indexes before "playing". Yes, making sure to agree on the same shuffling beforehand. - Tim |