Re: Coins on chess-board puzzle
Willem
) On 2009-11-20, Eric Sosman <eso...@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
Nick
> Tim Little wrote:
>> On 2009-11-20, Risto Lankinen <rlan...@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
dgates
<nichol...@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...?
dgates
>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?
dgates
�gidius Mogensen) wrote:
>Nicholas Nash <nichol...@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
Ted Schuerzinger
> 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?
Assume that the squares are numbered in binary from 000000 to 111111.
Then for each of the six places (the units place to the 32s place) look
at the 32 squares that have 1s in that place. If an odd number of those
squares have 1s in their binary representation, then the parity of that
number is 1; if an even number of those squares have 1s, the parity is
0. When the jailer gives you the secret square, turn over the
appropriate coin to change all six parities to the binary representation
of the secret square.
--
Ted S.
fedya at hughes dot net
Now blogging at http://justacineast.blogspot.com
Tim Little
> 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
There are only 3 possible numbers you can make, since you must change
exactly one of the bits from the warden's number.
Unfortunately you can't do it in that case - with 3 outputs to code
from 8 possible bitstrings, one of the outputs must have at most 2
encodings. Without loss of generality, suppose one of them is 000.
If the warden gives you 000 to start with, you *must* flip a bit to
get to the other one - so they can only differ in one bit position.
However, what if the warden gave you 111? You can't get to either of
them by flipping one bit.
You can do it if you are allowed to leave the board unaltered, and you
can encode four outputs in that case.
- Tim
Tim Little
> then I suspect that some variation of it works for 4 prisoners and 2
> photos, so I'll put my mind to that first.
> they now have a 2-in-24 chance.
What if I said they can improve it to 10-in-24?
- Tim
dgates
wrote:
>On 2009-11-22, dgates <dga...@somedomain.com> wrote:
>> 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
>
>There are only 3 possible numbers you can make, since you must change
>exactly one of the bits from the warden's number.
Oh, actually by "8 possible numbers you can make," I meant "8 possible
numbers that can be made with 3-digit binary number."
I figured some codes would have to be served by more than one number,
hence my "modulo 4" thinking.
I was figuring that the encoding would end up *something* like this:
Magic Set binary
Square Code
Equals equal to
0 NA
1 1 or 5
2 2 or 6
3 3 or 7
>Unfortunately you can't do it in that case - with 3 outputs to code
>from 8 possible bitstrings, one of the outputs must have at most 2
>encodings. Without loss of generality, suppose one of them is 000.
>If the warden gives you 000 to start with, you *must* flip a bit to
>get to the other one - so they can only differ in one bit position...
Sure, so for magic square "1," you'd flip to 001, for "2," you'd flip
to "010," and for magic square "3," then my system falls apart (but I
figured I just needed to re-jigger the numbers.
>However, what if the warden gave you 111?
In my system then...
for magic square "1," you'd flip to 101, for "2," you'd flip to "110,"
and for magic square "3," you'd flip to 011.
>You can do it if you are allowed to leave the board unaltered, and you
>can encode four outputs in that case.
I definitely noticed that my system would work better if you're
allowed to leave the board unaltered. And, even under those
conditions, I also need to re-jigger the numbers.
For example, from a starting point of 110, I can indicate magic square
2 or 3, but have no way to indicate magic square 1.
This is probably the shell of an alternate puzzle -- maybe a variation
on this one where the number of squares isn't a power of 2 and the
players are allowed to leave a coin unflipped as a valid move.
dgates
Ahh, I see. Yes, each square on the board can be part of several
different of the 6 numbers. That kind of reminds me of a kids' magic
trick where someone picks a number, you show him special cards, asking
him which cards it's on, then you quickly calculate his number.
The cards look like this:
http://illuminations.nctm.org/lessons/6-8/binary/fig7.gif
To calcluate the number quickly, you just add the top left number on
all the cards the guy said yes to.
It would be handy to have a little chart something like that (showing
which positions represent the 8 and the 16 and so on) printed on a
cheat sheet before the prisoners have to do their math in the little
room. :-)
dgates
wrote:
>On 2009-11-22, dgates <dga...@somedomain.com> wrote:
Yep, I read it, and it was amazing.
I think I read a version of that puzzle on this newsgroup, but as a
puzzle about 10 guys outside a theater trying to sort out their movie
tickets or something, and it was amazing then as well.
Tim Little
> I definitely noticed that my system would work better if you're
> allowed to leave the board unaltered. And, even under those
> conditions, I also need to re-jigger the numbers.
Moving up to the next odd size, it is impossible with a board of 5
squares even if you're allowed to leave it unaltered. I suspect the
same is true for size 6, but haven't fully analysed it.
- Tim
alexy
>On Sun, 22 Nov 2009 09:16:51 -0800, dgates wrote:
>
>> 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?
>
>Assume that the squares are numbered in binary from 000000 to 111111.
Starting where? There is nothing in the statement of the puzzle that
says you can mark the squares. If you want to assume you can mark
them, then just mark the magic square!
>Then for each of the six places (the units place to the 32s place) look
>at the 32 squares that have 1s in that place. If an odd number of those
>squares have 1s in their binary representation, then the parity of that
>number is 1; if an even number of those squares have 1s, the parity is
>0. When the jailer gives you the secret square, turn over the
>appropriate coin to change all six parities to the binary representation
>of the secret square.
--
Alex -- Replace "nospam" with "mail" to reply by email. Checked infrequently.
Patricia Shanahan
> Ted Schuerzinger <fe...@hughes.spam> wrote:
>
>> On Sun, 22 Nov 2009 09:16:51 -0800, dgates wrote:
>>
>>> 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?
>> Assume that the squares are numbered in binary from 000000 to 111111.
>
> Starting where? There is nothing in the statement of the puzzle that
> says you can mark the squares. If you want to assume you can mark
> them, then just mark the magic square!
As a separate part of their planning, the prisoners need to agree on a
numbering system, presumably relative to the door through which they
enter the test room.
Patricia
Ray
> As a separate part of their planning, the prisoners need to agree on a
> numbering system, presumably relative to the door through which they
> enter the test room.
And then they are led into the room through different doors and
the whole elegant plan falls apart..... ;-)
Bear
Risto Lankinen
> And then they are led into the room through different doors and
> the whole elegant plan falls apart..... ;-)
Hmm... I think a numbering exists where this does not
matter (meaning that applying the same algorithm from
any corner does not make a difference as long as the
coins stay in place).
In fact, I think 64 squares can accommodate 8 different
states (all four corners plus, say, all mirror images).
ObPuzzle: How?
- Risto -
Risto Lankinen
> In fact, I think 64 squares can accommodate 8 different
> states (all four corners plus, say, all mirror images).
Mind lapse - forget the thing about mirror images.
Rotations should still be doable.
- Risto -
olivernash
question of whether there is a better strategy. I notice that this
hasn't been discussed here so maybe people might be interested to see
the proof that this is the optimal strategy. I recently wrote a short
account of this here:
http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/
On Nov 20, 3:08 am, Tim Little <t...@little-possums.net> wrote:
> On 2009-11-20, Risto Lankinen <rlank...@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
Remysun
away, either a little saliva or cigarette ash on the first one's
fingers, or hiding a lighter to heat the coin up with could work.
Gilles LAFORME
"Remysun" <remys...@yahoo.com> a �crit dans le message de news:
81a5daf7-e1cc-4b81...@21g2000yqj.googlegroups.com...
Nicholas Nash
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
swp
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
GJ Woeginger
#
# 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/
cplxphil
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
GJ Woeginger
# On Nov 17, 6:47??am, Nicholas Nash <nicholas.n...@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
cplxphil
wrote:
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
GJ Woeginger
# On Nov 17, 12:15??pm, gwo...@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
Mark Brader
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
m...@vex.net | (Michael Piller, Star Trek: Voyager, "Tattoo")
My text in this article is in the public domain.
alexy
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)).
Mark Brader
> 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
m...@vex.net that's just as good." -- D Gary Grady
Torben Ægidius Mogensen
> 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
Paul Hunter
> In comp.theory cplxphil <cplx...@gmail.com> wrote:
> # On Nov 17, 12:15??pm, gwo...@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)
Tim Little
> 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
Risto Lankinen
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 -
Tim Little
> 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
Torben Ægidius Mogensen
Torben Ægidius Mogensen
> On 18 marras, 14:48, torb...@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.
This is, indeed, the solution I was thinking of.
> 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 .
As Tim noted, it is somewhat smaller than that, but still much larger
than most expect.
Torben
Eric Sosman
> On 2009-11-20, Risto Lankinen <rlan...@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.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Andrew B.
> Tim Little wrote:
No, because by design they're each starting at the worst possible
point of the cycle.
Tim Little
> 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.
- Tim