Coins on chess-board puzzle
in [Theory]
|
From: Willem on 21 Nov 2009 03:52 Tim Little wrote: ) On 2009-11-20, Eric Sosman <esosman(a)ieee-dot-org.invalid> wrote: )> Even if all the cards are in one cycle of length k = 50, each )> prisoner finds his own photo if he starts with any photo not more )> than 24 places before his own. ) ) An easy way to see that this cannot be true is to consider which photo ) they would turn immediately after their own. <pedantic> Well, technically what he said *is* true (trivially): *IF* he starts with any photo not more than 24 places before his own. The problem being, of course, that that 'if' is never satisfied, as you showed. </pedantic> SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT
From: Nick on 21 Nov 2009 06:29 Eric Sosman <esosman(a)ieee-dot-org.invalid> writes: > Tim Little wrote: >> 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. > > I think you mean "exactly k prisoners are less than certain > to find their own photos." Even if all the cards are in one > cycle of length k = 50, each prisoner finds his own photo if > he starts with any photo not more than 24 places before his > own. So even in this extreme case each prisoner has a 25/50 > chance of finding his own photo. I was lying awake last night and thinking about this one. What's happening is really quite neat (the following developed as the results of hints from people who clearly got this quickly - this is for the benefit of those who didn't!): What you are doing is creating a set of closed cycles amongst the photos. The minimum length is 1 (photo n is in position n) and the longest is 50. This means that the photo in any position is immediately preceded in a cycle by the photo of the person with that number. Therefore, if you start with your photo you are guaranteed to be in the same cycle as your picture. BUT you are as far away from it as possible. This means that the chances of you finding your photo are dominated by the distribution of cycles - if there are no cycles of length greater than 25 you are guaranteed to find it. So as you add people to it, instead of the odds starting at .5 and going down for each new person, they fairly rapidly converge on "what are the odds that there are no cycles of length > 25". I don't know enough maths to work that out, but it's pretty obviously a lot better than ..5^50. -- Online waterways route planner: http://canalplan.org.uk development version: http://canalplan.eu
From: dgates on 22 Nov 2009 12:11 On Tue, 17 Nov 2009 03:47:29 -0800 (PST), Nicholas Nash <nicholas.nash(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. I haven't looked at the answer yet, but I suspect that the answer will be something like this (involving hugely complicated math): Each prisoner will think of the entire chessboard as 64-digit binary number. The first prisoner will switch one digit of the binary number to create a new binary number that represents the magic square's number in the form [something] modulo [something]. I'm trying to work out how you would even do it if there were only 3 squares, rather than 64 squares. As I see it, with 3 squares, there are 8 possible numbers you can make, and 3 possibilities for the "magic square" (or 4, if the warden were allowed to say "There is no magic square). It seems like, in the case with a 3-square chessboard, you need some kind of "modulo 4" answer, so maybe with the 64-square chessboard, you need a "modulo (2^64)-1" answer...?
From: dgates on 22 Nov 2009 12:16 On Tue, 17 Nov 2009 15:32:24 -0600, msb(a)vex.net (Mark Brader) wrote: >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! I read in another post that this is considered the correct answer, and it seems to go along with my idea that somehow you encode the information using all 64 coins, but I don't understand exactly how you would communicate this strategy to your fellow prisoner. Let's say you were the first prisoner, and I were the second (and, while I know that 2^6 is 64, I don't know what "EXOR" means). What would you tell me to look for in order to decode your message to me?
From: dgates on 22 Nov 2009 12:25
On Wed, 18 Nov 2009 13:48:46 +0100, torbenm(a)pc-003.diku.dk (Torben �gidius Mogensen) wrote: >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? Hmm, if there's a solution that works for 50 prisoners and 25 photos, then I suspect that some variation of it works for 4 prisoners and 2 photos, so I'll put my mind to that first. Obviously with the 4&2 problem, the *worst* strategy would be for them all to flip photos 1 and 2, since two will be guaranteed to be wrong. Conversely, I guess they could improve their odds by each flipping as follows: P1: 1 & 2 P2: 2 & 3 P3: 3 & 4 P4: 4 & 1 That seems to up their odds slightly. Instead of them only having a 1-in-256 chance, as they would have by pure chance, they now have a 2-in-24 chance. I'm guessing that, in the 50-prisoner version, P1 should flip 1 thru 25, P2 should flip 2 thru 26, and so on. But I still don't love their odds! :-o |