Prisoner puzzle
David Goldfarb
some people here.
Imagine that alien space bats have taken 100 smart people prisoner.
The people get to confer beforehand, but after conferring they're
going to be held in solitary confinement and have no contact with
each other.
There is one channel of communication, and it's only one bit wide:
once per day, a randomly-selected prisoner is taken to a room with
a light bulb and a switch. That prisoner then has three choices:
1) Flip the switch, toggling the bulb's state. (The bulb is known
to start in the "off" state, by the by.)
2) Do nothing.
3) Make the assertion, "Each of us has been in this room at least once."
In this last case, if the assertion is correct then there is a reward,
and if not there is a penalty. The details don't matter. The point
is that there's a strong incentive for the prisoners to make sure
that when the assertion is eventually made, it is correct.
So then: how can they guarantee this?
--
David Goldfarb |"'Shut up, shut up, shut up,' says the stranger
gold...@ocf.berkeley.edu | from the stars!"
gold...@csua.berkeley.edu | -- _Norstrilia_
Keith F. Lynch
> Imagine that alien space bats have taken 100 smart people prisoner.
> The people get to confer beforehand, but after conferring they're
> going to be held in solitary confinement and have no contact with
> each other.
> There is one channel of communication, and it's only one bit wide:
> once per day, a randomly-selected prisoner is taken to a room with
> a light bulb and a switch. That prisoner then has three choices:
> 1) Flip the switch, toggling the bulb's state. (The bulb is known
> to start in the "off" state, by the by.)
> 2) Do nothing.
> 3) Make the assertion, "Each of us has been in this room at least once."
> In this last case, if the assertion is correct then there is a
> reward, and if not there is a penalty. The details don't matter.
> The point is that there's a strong incentive for the prisoners to
> make sure that when the assertion is eventually made, it is correct.
> So then: how can they guarantee this?
Can all the prisoners see whether the bulb is on or off from their
cells? Or can they only see it when they're in the room with it?
Thanks.
--
Keith F. Lynch - http://keithlynch.net/
Please see http://keithlynch.net/email.html before emailing me.
Harry Mary Andruschak
> There is one channel of communication, and it's only one bit wide:
> once per day, a randomly-selected prisoner is taken to a room with
> a light bulb and a switch. �That prisoner then has three choices:
>
> 1) Flip the switch, toggling the bulb's state. �(The bulb is known
> to start in the "off" state, by the by.)
> 2) Do nothing.
> 3) Make the assertion, "Each of us has been in this room at least once."
>
> In this last case, if the assertion is correct then there is a reward,
> and if not there is a penalty. �The details don't matter. �The point
> is that there's a strong incentive for the prisoners to make sure
> that when the assertion is eventually made, it is correct.
>
But what are the consequences of choosing 1 or 2?
As for choice 3, wrong could mean death, and correct could mean
release. The others would be informed if a death occured, thus giving
them the information that not all had yet been in the room.
Much more information needed.
David Goldfarb
Keith F. Lynch <k...@KeithLynch.net> wrote:
>Can all the prisoners see whether the bulb is on or off from their
>cells? Or can they only see it when they're in the room with it?
They can only see it when they're in the room.
--
David Goldfarb | "And it came to pass by the way in the inn,
gold...@ocf.berkeley.edu | that the LORD met him, and sought to kill him."
gold...@csua.berkeley.edu | -- Exodus 4:24
David Goldfarb
Harry Mary Andruschak <adopts...@aol.com> wrote:
>On Jun 26, 9:42�am, goldf...@ocf.berkeley.edu (David Goldfarb) wrote:
>> 1) Flip the switch, toggling the bulb's state. (The bulb is known
>> to start in the "off" state, by the by.)
>> 2) Do nothing.
>> 3) Make the assertion, "Each of us has been in this room at least once."
>>
>> In this last case, if the assertion is correct then there is a reward,
>> and if not there is a penalty.
>
I had thought that I said that: if 1 is chosen, the state of the
light bulb gets toggled -- it turns off if it was on, it turns on if
it was off. If 2 is chosen, nothing happens. In either case,
the prisoner then returns to their cell.
>As for choice 3, wrong could mean death, and correct could mean
>release. The others would be informed if a death occured, thus giving
>them the information that not all had yet been in the room.
No. The *first* time someone chooses 3, *everybody* either gets killed
or released. That's the kind of thing I meant when I said that there
was a big incentive for the prisoners to get it right.
--
David Goldfarb |"'The truth will set you free.'
gold...@ocf.berkeley.edu | If you love the truth, you'll inevitably
gold...@csua.berkeley.edu | come back!" -- Hitherby Dragons
Morris Keesan
<gold...@ocf.berkeley.edu> wrote:
> Imagine that alien space bats have taken 100 smart people prisoner.
> The people get to confer beforehand, but after conferring they're
> going to be held in solitary confinement and have no contact with
> each other.
>
> There is one channel of communication, and it's only one bit wide:
> once per day, a randomly-selected prisoner is taken to a room with
> a light bulb and a switch.
But we don't know anything about the selection process other than that it's
random, correct? In particular, the random process could select the same
prisoner multiple times, with some others having never been selected?
David Friedman
gold...@ocf.berkeley.edu (David Goldfarb) wrote:
> In article <h240i8$9i$1...@panix2.panix.com>,
> Keith F. Lynch <k...@KeithLynch.net> wrote:
> >Can all the prisoners see whether the bulb is on or off from their
> >cells? Or can they only see it when they're in the room with it?
>
> They can only see it when they're in the room.
Start with the light bulb off.
Every prisoner is told to turn the light bulb on the first time he is in
the cell and it is off, thereafter to leave it alone. Except that ...
Prisoner 1 is told to turn the light bulb off every time he finds it on,
and keep count; if it's off he leaves it off. When he has turned it off
N-1 times, he knows that N-1 other prisoners have been in the cell. So
he announces that all prisoners have visited the cell.
--
http://www.daviddfriedman.com/ http://daviddfriedman.blogspot.com/
Author of
_Future Imperfect: Technology and Freedom in an Uncertain World_,
Cambridge University Press.
David Friedman
"Morris Keesan" <kee...@alum.bu.edu> wrote:
If it's really random, they will eventually all be selected. With my
solution, which I just posted, the process takes longer than that--but
eventually terminates.
Michael Benveniste
>Start with the light bulb off.
>
>Every prisoner is told to turn the light bulb on the first time he is in
>the cell and it is off, thereafter to leave it alone. Except that ...
>
>Prisoner 1 is told to turn the light bulb off every time he finds it on,
>and keep count; if it's off he leaves it off. When he has turned it off
>N-1 times, he knows that N-1 other prisoners have been in the cell. So
>he announces that all prisoners have visited the cell.
This is a correct solution.
But since we are dealing with people, there are a couple of caveats.
The first is that none of the prisoners screw up. If prisoner 1 loses
count, or another prisoner forgets that he or she has already turned
the light on, certainty is lost. The second is that all of the
prisoners survive and stay sane long enough to complete their tasks.
Neither of these are trivial caveats, since the solution will take an
average of about 10400 days (28.4+ years) to play out.
If the aliens allow the prisoners to count days, you get 99.99% odds
that everyone has entered the room after about 1360 days, and 99.999%
odds after 1600 days.
--
Mike Benveniste -- m...@murkyether.com (Clarification Required)
Don't succumb to the false authority of a tool or model. There
is no substitute for thinking.
Arthur T.
Message-ID:<ddfr-013308.1...@newsfarm.ams.highwinds-media.com>,
David Friedman <dd...@daviddfriedman.nopsam.com> wrote:
>In article <KM0ID...@kithrup.com>,
> gold...@ocf.berkeley.edu (David Goldfarb) wrote:
>
>> In article <h240i8$9i$1...@panix2.panix.com>,
>> Keith F. Lynch <k...@KeithLynch.net> wrote:
>> >Can all the prisoners see whether the bulb is on or off from their
>> >cells? Or can they only see it when they're in the room with it?
>>
>> They can only see it when they're in the room.
>
>Start with the light bulb off.
>
>Every prisoner is told to turn the light bulb on the first time he is in
>the cell and it is off, thereafter to leave it alone. Except that ...
>
>Prisoner 1 is told to turn the light bulb off every time he finds it on,
>and keep count; if it's off he leaves it off. When he has turned it off
>N-1 times, he knows that N-1 other prisoners have been in the cell. So
>he announces that all prisoners have visited the cell.
This is why it's a bad idea to phrase mathematical puzzles as if
they were in the real world. What is the likelihood that all 100
prisoners will still be alive after the 27 or more years that this
procedure will take? Remember, if even one prisoner dies, the
algorithm never halts.
--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
Harry Mary Andruschak
> once per day, a randomly-selected prisoner is taken to a room with
> a light bulb and a switch. �That prisoner then has three choices:
Perhaps the puzzle could be improved by stating that while the
prisoners are chosen randomly, all must be chosen ONCE before the
process starts for a second round of random choices.
Evelyn Leeper
Well, no, because then one can say after 100 days that all have been in
the room once.
--
Evelyn C. Leeper
Never let your sense of morals prevent you from doing
what is right. -Salvor Hardin, "Foundation"
Keith F. Lynch
> Keith F. Lynch <k...@KeithLynch.net> wrote:
>> Can all the prisoners see whether the bulb is on or off from their
>> cells? Or can they only see it when they're in the room with it?
> They can only see it when they're in the room.
As others have pointed out, the solution would then take so long that
it's vanishingly unlikely that all hundred prisoners would still be
living -- and it would fail if they weren't.
My thought was that if they *can* see the light from their cells, that
each of them changes the state of the bulb only once, the first time
they're in the room with it. Then after it has changed state 100
times, everyone immediately knows that everyone has been in that room
at least once.
Harry Mary Andruschak
> some people here.
>
> Imagine that alien space bats have taken 100 smart people prisoner.
PS on 29 June, late evening. 100 people is way too much for a
practical test. Now maybe a small group of fans at a convention might
be worth testing out.
David Goldfarb
David Friedman <dd...@daviddfriedman.nopsam.com> wrote:
>Start with the light bulb off.
>
>Every prisoner is told to turn the light bulb on the first time he is in
>the cell and it is off, thereafter to leave it alone. Except that ...
>
>Prisoner 1 is told to turn the light bulb off every time he finds it on,
>and keep count; if it's off he leaves it off. When he has turned it off
>N-1 times, he knows that N-1 other prisoners have been in the cell. So
>he announces that all prisoners have visited the cell.
Very good. Katie and I didn't manage to figure that out on our own;
Katie peeked at the result in a paper. (The paper goes on to do some
calculations about the expected time taken.)
Assuming you solved that yourself, I'm impressed.
--
David Goldfarb | "Oh no, foolish Jed, you have let out
gold...@ocf.berkeley.edu | the verbal gerbils!"
gold...@csua.berkeley.edu | -- _Sandman_ #11
David Goldfarb
><gold...@ocf.berkeley.edu> wrote:
>> There is one channel of communication, and it's only one bit wide:
>> once per day, a randomly-selected prisoner is taken to a room with
>> a light bulb and a switch.
>
>But we don't know anything about the selection process other than that it's
>random, correct? In particular, the random process could select the same
>prisoner multiple times, with some others having never been selected?
Yes, that is correct. It could conceivably happen that the prisoners
will *never* get to correctly assert that everyone has been in the room,
although as time passes this will become decreasingly likely. If you
like, assume that the ASB's extend the prisoners' lifespans so that
none of them die before the experiment is over.
--
David Goldfarb |"The only thing better than messing with somebody's
gold...@ocf.berkeley.edu | sense of reality is messing with a whole LOTTA
gold...@csua.berkeley.edu | people's sense of reality...."
| -- J. Michael Straczynski
David Friedman
gold...@ocf.berkeley.edu (David Goldfarb) wrote:
> In article <ddfr-013308.1...@newsfarm.ams.highwinds-media.com>,
> David Friedman <dd...@daviddfriedman.nopsam.com> wrote:
> >Start with the light bulb off.
> >
> >Every prisoner is told to turn the light bulb on the first time he is in
> >the cell and it is off, thereafter to leave it alone. Except that ...
> >
> >Prisoner 1 is told to turn the light bulb off every time he finds it on,
> >and keep count; if it's off he leaves it off. When he has turned it off
> >N-1 times, he knows that N-1 other prisoners have been in the cell. So
> >he announces that all prisoners have visited the cell.
>
> Very good. Katie and I didn't manage to figure that out on our own;
> Katie peeked at the result in a paper. (The paper goes on to do some
> calculations about the expected time taken.)
>
> Assuming you solved that yourself, I'm impressed.
I did. Fun puzzle.
The critical point was to realize that although the state of the light
was only a one bit signal, the history of the state of the light as
observed by a prisoner had lots of bits.
David Goldfarb
David Friedman <dd...@daviddfriedman.nopsam.com> wrote:
>
>Every prisoner is told to turn the light bulb on the first time he is in
>the cell and it is off, thereafter to leave it alone. Except that ...
[snip]
Actually, thinking about it, it's not necessary that the initial state
of the bulb be known. On the first day, whoever goes to the room *sets*
the bulb to off; after that, you proceed with the given solution, as though
what is now the second day were the first day with known state.
--
David Goldfarb | "Boom. Sooner or later. Boom!"
gold...@ocf.berkeley.edu |
gold...@csua.berkeley.edu | -- Babylon 5, "Grail"
Paul Treadaway
> As others have pointed out, the solution would then take so long that
> it's vanishingly unlikely that all hundred prisoners would still be
> living -- and it would fail if they weren't.
If the aliens are actually interested in the result (i.e. they want to
know whether humans can manage this), perhaps they've used
their superior technology to stop the humans aging, getting ill etc.
William December Starr
Paul Treadaway <paul.tr...@dial.pipex.com> said:
> "Keith F. Lynch" <k...@KeithLynch.net> wrote
>
>> As others have pointed out, the solution would then take so long
>> that it's vanishingly unlikely that all hundred prisoners would
>> still be living -- and it would fail if they weren't.
>
> If the aliens are actually interested in the result (i.e. they
> want to know whether humans can manage this), perhaps they've used
> their superior technology to stop the humans aging, getting ill
> etc.
Or, despite what they said, they're really only going to run the
experiment long enough to determine by observation whether the
humans are implementing the solution.
That would only require however long it takes for each human to be
randomly selected at least once, right?
(Of course, if the aliens had taken the time to learn the common
language of the set of humans they'd selected for the experiment, or
had a magical universal translator device, they could simply listen
in on the humans while they were together planning (or not) their
strategy. After all, if the point is to determine "Are the humans
smart enough to solve this puzzle?", once you know whether they
_have_ figured out the solution there's no real need to make them go
through all the motions, or for you to sit there watching them.)
-- wds
David Friedman
wds...@panix.com (William December Starr) wrote:
> In article <Xns9C409019763B5pa...@69.16.176.253>,
> Paul Treadaway <paul.tr...@dial.pipex.com> said:
>
> > "Keith F. Lynch" <k...@KeithLynch.net> wrote
> >
> >> As others have pointed out, the solution would then take so long
> >> that it's vanishingly unlikely that all hundred prisoners would
> >> still be living -- and it would fail if they weren't.
> >
> > If the aliens are actually interested in the result (i.e. they
> > want to know whether humans can manage this), perhaps they've used
> > their superior technology to stop the humans aging, getting ill
> > etc.
>
> Or, despite what they said, they're really only going to run the
> experiment long enough to determine by observation whether the
> humans are implementing the solution.
>
> That would only require however long it takes for each human to be
> randomly selected at least once, right?
I don't follow that. How do you know if the humans' behavior follows the
pattern of the (or a) solution?
William December Starr
David Friedman <dd...@daviddfriedman.nopsam.com> said:
> wds...@panix.com (William December Starr) wrote:
>
>> Or, despite what they said, they're really only going to run the
>> experiment long enough to determine by observation whether the
>> humans are implementing the solution.
>>
>> That would only require however long it takes for each human to be
>> randomly selected at least once, right?
>
> I don't follow that. How do you know if the humans' behavior
> follows the pattern of the (or a) solution?
Hmm. Having thought about it some more, I have to withdraw that
suggestion -- no matter how much it may _look_ like the humans were
executing following the simple solution-algorithm, it would still
_possible_ that they were running a different program that just
happened to, in its initial steps, _resemble_ the simple solution.
The only way to be sure would be to let it run to either (a) the
conclusion of the simple solution or (b) a point where it diverged
from the simple solution, at which point the experiment-runner would
have to decide whether to declare a failure or let it keep running
(for how long?) to see whether a less-efficient but still eventually
successful algorithm was being executed.
-- wds
David Friedman
Or a more efficient algorithm. I gather they exist, at least for large
numbers.
Keith F. Lynch
> Having thought about it some more, I have to withdraw that
> suggestion -- no matter how much it may _look_ like the humans were
> executing following the simple solution-algorithm, it would still
> _possible_ that they were running a different program that just
> happened to, in its initial steps, _resemble_ the simple solution.
I remember when I was a child, cycling through a three-way lamp many
times. When my father asked me what I was doing, I explained that I
was trying to figure out the pattern. It appeared to repeat every
fourth click (off, dim filament, bright filament, both filaments), but
how could I be sure it wouldn't eventually do something different?
(I now know that at the time it would have been very difficult to
build such a lamp. Today, of course, it would be trivial to have it
spell out the first billion digits of pi in base 4 or whatever.)
There are also games such as Eleusis and Zendo where the goal is to
figure out the rule. No matter how many observations you make, you
can never be sure you've got it right. Similarly with a scientist
observing nature.
Steve Coltrin
"Keith F. Lynch" <k...@KeithLynch.net> writes:
> I remember when I was a child, cycling through a three-way lamp many
> times. When my father asked me what I was doing, I explained that I
> was trying to figure out the pattern. It appeared to repeat every
> fourth click (off, dim filament, bright filament, both filaments), but
> how could I be sure it wouldn't eventually do something different?
Eventually it would have, of course - one of the filaments would have
burned out.
--
Steve Coltrin spco...@omcl.org Google Groups killfiled here
"A group known as the League of Human Dignity helped arrange for Deuel
to be driven to a local livestock scale, where he could be weighed."
- Associated Press
Michael Stemper
>In article <op.uwaxhmldakl9p6@toshiba-laptop>, "Morris Keesan" <kee...@alum.bu.edu> wrote:
>> On Fri, 26 Jun 2009 12:42:14 -0400, David Goldfarb <gold...@ocf.berkeley.edu> wrote:
>> > Imagine that alien space bats have taken 100 smart people prisoner.
>> > The people get to confer beforehand, but after conferring they're
>> > going to be held in solitary confinement and have no contact with
>> > each other.
>> But we don't know anything about the selection process other than that it's
>> random, correct? In particular, the random process could select the same
>> prisoner multiple times, with some others having never been selected?
>If it's really random, they will eventually all be selected.
I don't believe that is correct. I believe that there is always a
non-zero (but continuously decreasing) probability that somebody
will not have been selected at any point in time.
--
Michael F. Stemper
#include <Standard_Disclaimer>
I feel more like I do now than I did when I came in.
Seth
There is no single point in time that corresponds to "eventually".
With probability 1, everybody will be selected in finite time.
Seth
Michael Stemper
I'm afraid not.
If you have "p" people, the probability that a particular person will
not have been chosen after "n" selections (with replacement) is
(1 - 1/p)^n. No matter how large "n" gets, this will always be greater
than zero.
Since this is the probability that one specific person hasn't been
chosen, the probability that there exists a person who hasn't been
chosen is higher, although I don't know off-hand how to calculate it.
--
Michael F. Stemper
#include <Standard_Disclaimer>
Twenty-four hours in a day; twenty-four beers in a case. Coincidence?
Keith F. Lynch
> se...@panix.com (Seth) writes:
>> There is no single point in time that corresponds to "eventually".
>> With probability 1, everybody will be selected in finite time.
> I'm afraid not.
> If you have "p" people, the probability that a particular person
> will not have been chosen after "n" selections (with replacement)
> is (1 - 1/p)^n. No matter how large "n" gets, this will always be
> greater than zero.
You're both correct.