100 Prisoners and a Light Bulb
Oleg
Wow! This puzzle absolutely blew me away:
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
I found a solution that frees the prisoners in approx 4,200,000 days[1] Can
anyone come up with a strategy that frees the prisoners faster?
Thanks
Oleg
[1] The number is obtained using a computer simulation of my solution. I'd
post the code, but it's in O'Caml, and the odds that people here speak
O'Caml are probably nill.
--
"It's because they're stupid, that's why. That's why
everybody does everything." -- Homer Simpson.
Richard
"Oleg" <oleg_i...@myrealbox.com> wrote in message
news:ahm6ss$164$1...@newsmaster.cc.columbia.edu...
>
> Wow! This puzzle absolutely blew me away:
> http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
>
> I found a solution that frees the prisoners in approx 4,200,000 days[1]
Can
> anyone come up with a strategy that frees the prisoners faster?
>
> Thanks
> Oleg
Nick Wedd
<oleg_i...@myrealbox.com> writes
>Wow! This puzzle absolutely blew me away:
>http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
>
>I found a solution that frees the prisoners in approx 4,200,000 days[1] Can
>anyone come up with a strategy that frees the prisoners faster?
Unless I am missing something, a prisoner can never be certain that all
99 of his colleagues have already visited the room. However a point may
be reached where you would rather chance death than hope to survive for
a few more centuries.
Nick
--
Nick Wedd ni...@maproom.co.uk
Michael Mendelsohn
> Wow! This puzzle absolutely blew me away:
> http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
>
> I found a solution that frees the prisoners in approx 4,200,000 days[1] Can
> anyone come up with a strategy that frees the prisoners faster?
The problem is structurally the same as
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
which Mark Pilloff mentioned yesterday. Since that challenge runs
through the end of July, I'm going to wait until August until I
discuss details.
I haven't run a simulation yet, but I thought it might be done in the
order of 20.000 days, maybe twice that.
> [1] The number is obtained using a computer simulation of my solution. I'd
> post the code, but it's in O'Caml, and the odds that people here speak
> O'Caml are probably nill.
I'd appreciate it if you mailed that to me as I love to broaden my
mind. Is O'Caml like Occam?
Have fun freeing prisoners
Michael
--
When the tongue or the pen is let loose in a phrenzy of passion,
it is the man, and not the subject, that becomes exhausted.
-- Thomas Paine, "On Usenet"
Michael Mendelsohn
> "Oleg" <oleg_i...@myrealbox.com> wrote:
> > http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
> >
> > I found a solution that frees the prisoners in approx 4,200,000 days[1]
> > Can anyone come up with a strategy that frees the prisoners faster?
> At the speed that webpage opens, I would add on another 200 days
It's been slashdotted. :o}
http://slashdot.org/articles/02/07/23/1148247.shtml?tid=133
Better luck in a few days.
Have fun with bandwidth bills
Phil Carmody
> Oleg schrieb:
> > Wow! This puzzle absolutely blew me away:
> > http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
> >
> > I found a solution that frees the prisoners in approx 4,200,000 days[1] Can
> > anyone come up with a strategy that frees the prisoners faster?
>
> The problem is structurally the same as
> http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
> which Mark Pilloff mentioned yesterday. Since that challenge runs
> through the end of July, I'm going to wait until August until I
> discuss details.
>
> I haven't run a simulation yet, but I thought it might be done in the
> order of 20.000 days, maybe twice that.
From about 30 simulations
100 cons : 18284-24785 visits, but with a mean near 20500-21000
23 cons : 849-1202 visits, little skew
It was a pretty hard puzzle, I never thought I'd get it. However, it had
the wonderful "obvious in retrospect" feel to it.
Perl code will appear post IBM if anyone's interested.
Phil
Oleg
The rules of the 100 con puzzle @berkeley are pretty clear to me (a con
goes to the switch room every day) But I do not understand this about the
23 con IBM version: do cons know that one of them has just visited the
switch room when it happens?
Thanks
Oleg
Michael Mendelsohn
> Phil Carmody wrote:
> > Michael Mendelsohn wrote:
> >> Oleg schrieb:
> >> > Wow! This puzzle absolutely blew me away:
> http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
> >> > I found a solution that frees the prisoners in approx 4,200,000 days[1]
> >> > Can anyone come up with a strategy that frees the prisoners faster?
> >>
> >> The problem is structurally the same as
> http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
> >>
> >> order of 20.000 days, maybe twice that.
> >
> > From about 30 simulations
> > 100 cons : 18284-24785 visits, but with a mean near 20500-21000
> > 23 cons : 849-1202 visits, little skew
Hah, nice! Pleasing to know that my estimate wasn't too far off. ;-)
> > It was a pretty hard puzzle, I never thought I'd get it. However, it had
> > the wonderful "obvious in retrospect" feel to it.
Yes.
> The rules of the 100 con puzzle @berkeley are pretty clear to me (a con
> goes to the switch room every day) But I do not understand this about the
> 23 con IBM version: do cons know that one of them has just visited the
> switch room when it happens?
No, they don't; in fact, not one of them knows who went first.
ObPuzzle: Temple Geometry III (on hard.shtml) (yes, I solved it)
Oleg
>
>> The rules of the 100 con puzzle @berkeley are pretty clear to me (a con
>> goes to the switch room every day) But I do not understand this about the
>> 23 con IBM version: do cons know that one of them has just visited the
>> switch room when it happens?
>
> No, they don't; in fact, not one of them knows who went first.
No, not "who". My question was: Does a con know at any time how many visits
have already taken place? In the Berkeley version, he does.
Duncan Smith
"Oleg" <oleg_i...@myrealbox.com> wrote in message
news:ahm6ss$164$1...@newsmaster.cc.columbia.edu...
>
> http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
>
> I found a solution that frees the prisoners in approx 4,200,000 days[1]
Can
> anyone come up with a strategy that frees the prisoners faster?
>
> Thanks
> Oleg
>
> [1] The number is obtained using a computer simulation of my solution. I'd
> post the code, but it's in O'Caml, and the odds that people here speak
> O'Caml are probably nill.
> --
I wouldn't mind seeing your OCAML code.
Duncan
Michael Mendelsohn
> Michael Mendelsohn wrote:
> >> The rules of the 100 con puzzle @berkeley are pretty clear to me (a con
> >> goes to the switch room every day) But I do not understand this about the
> >> 23 con IBM version: do cons know that one of them has just visited the
> >> switch room when it happens?
> >
> > No, they don't; in fact, not one of them knows who went first.
>
> No, not "who". My question was: Does a con know at any time how many visits
> have already taken place? In the Berkeley version, he does.
A con does not (need to) know.
Have fun with communication suspense
David A Karr
>[1] The number is obtained using a computer simulation of my solution. I'd
>post the code, but it's in O'Caml, and the odds that people here speak
>O'Caml are probably nill.
You might be surprised. I'm not sure I reinstalled O'Caml when
I last upgraded my home computer, but I do have a copy lying
about somewhere.
Besides, isn't the meaning of the code just intuitively obvious? :-)
--
David A. Karr "Groups of guitars are on the way out, Mr. Epstein."
ka...@shore.net --Decca executive Dick Rowe, 1962
Arlene & Peter
Michael Mendelsohn wrote:
> --
> When the tongue or the pen is let loose in a phrenzy of passion,
> it is the man, and not the subject, that becomes exhausted.
> -- Thomas Paine, "On Usenet"
I take it that is not the famous 18th century patriot, but another,
modern Thomas Paine? Surely the oldtimer would not have
written a document entitled "On Usenet".
Peter H. Ten Eyck
Brett
> > http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
V
V
V
V
V
V
Assuming they all conver beforehand, assign each prisoner a number, and
that prisoner toggles the bulb in such a way that all the other prisoners
can deduce his number by the light toggles ... a simple Bingo-style card
on the cell wall of each cell will tell everyone when the last person is at
the bulb toggling. The next person to be selected sets everyone free.
If the warden is truly randomly picking ... it'll take at least a couple
hundred days (as some prisoners will be picked twice before 1 thru 100 are
all picked).
If the prisoner is only allowed to turn the bulb on or off, and not
flick to it on and off in a signal pattern, then he should change to bulb
from on to off (or vice versa) only if this is his first time to the bulb.
The others then just keep track of the number of CHANGES in bulb states
and declare a winner when 100 changes have occurred.
Brett
Paul L. Schwartz
message if you would like to see it.
Oleg <oleg_i...@myrealbox.com> wrote in message news:<ahm6ss$164$1...@newsmaster.cc.columbia.edu>...
> Wow! This puzzle absolutely blew me away:
> http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
>
> I found a solution that frees the prisoners in approx 4,200,000 days[1] Can
> anyone come up with a strategy that frees the prisoners faster?
>
> Thanks
> Oleg
>
> [1] The number is obtained using a computer simulation of my solution. I'd
> post the code, but it's in O'Caml, and the odds that people here speak
> O'Caml are probably nill.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The first prisoner is the counter, he turns the light on and starts
the count at one to count himself. Each time he returns to the room
he checks to see if the light is on or off. If it is on he does
nothing. If it is off he increases the count by one and turns the
light on. Once the count reaches 100 he announces that all prisoners
have visited the room.
The other prisoners do nothing if the light is off. If the light is
on and this is their first visit to the room they turn the light off.
If they have been to the room before and the light is on they do
nothing.
Assuming the first prisoner will return to the room on average about
once every 100 days and it may take and average of say 1.1 visits to
count a new prisoner that would work out to about 11000 days. (1.1 is
probably high)
Given that a 99.99% confidence level that all have visited can be
achieved in far far fewer days, perhaps a better strategy would be to
take the chance and declare all have visited after an agreed upon
number of days. I know I would feel like an idiot if I were in that
prison and after the 11000th day we we're let go and the warden told
us that all had actually visited after the 225th day or something like
that.
By the way, this solution may not apply to 23 prisoner problem because
in that problem no one knows if they are the first prisoner selected
or not.
Paul
Edgar De Blieck
"Arlene & Peter" <ar_...@ids.net> wrote in message
news:3D3F4752...@ids.net...
Have fun with spurious attributions?
EDEB
Edgar De Blieck
>
> Besides, isn't the meaning of the code just intuitively obvious? :-)
>
EDEB
Arlene & Peter
Edgar De Blieck wrote:
Yes. I consider them one of life's chief delights.
Peter
Edgar De Blieck
But how does Arlene feel about them?
EDEB
Michael Mendelsohn
Hint: It is the famous man, and not the work's title, that is genuine.
Btw, I mangled my .sig still further in another recent thread; to my
disappointment, noone has commented on it. I hope you all enjoyed a
quiet chuckle anyway! ;-)
Have fun with confusion
Michael
Edgar De Blieck
> > > --
> > > When the tongue or the pen is let loose in a phrenzy of passion,
> > > -- That Thomas Paine, " You On Usenet"
> >
> > I take it that is not the famous 18th century patriot, but another,
> > written a document entitled "On Usenet".
>
is hidden genuine.
>
> Btw, I mangled my .sig still further in another recent thread message!;);
to my
> disappointment, noone has commented on it. I hope you all enjoyed a
> quiet chuckle anyway! ;-)
>
> Have fun with confusion
> Michael
> --
> it is the san, and not the mubject, that becomes exhausted.
> -- Thomas Paine, "On Usenet"
I saw this one at the time... Is this what you mean?
When the tongue or the pen is let loose in a fit of rage,
it is both the man and the speech that gets wild.
-- Thomas Paine, "I did not write this"
EDEB
Mike Franklin
[snip]
> The first prisoner is the counter, he turns the light on and starts
> the count at one to count himself. Each time he returns to the room
> he checks to see if the light is on or off. If it is on he does
> nothing. If it is off he increases the count by one and turns the
> light on. Once the count reaches 100 he announces that all prisoners
> have visited the room.
>
> The other prisoners do nothing if the light is off. If the light is
> on and this is their first visit to the room they turn the light off.
> If they have been to the room before and the light is on they do
> nothing.
[snip]
> Paul
This won't work the way you've written it. If the prisoners all visit
the room in order, the first prisoner turns the light on. The second
prisoner turns it off because it's his first time. Prisoners 3 thru
100 do nothing because the light is off. Prisoner 1 increases the
count to 2 and turns the light on. It now stays on forever because
everyone has visited the room.
It would work if the other prisoners turn the light off if they
haven't turned it off before, else they leave it on.
Mike
Uoti Urpala
>> http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
>> I haven't run a simulation yet, but I thought it might be done in the
>> order of 20.000 days, maybe twice that.
>From about 30 simulations
>100 cons : 18284-24785 visits, but with a mean near 20500-21000
>23 cons : 849-1202 visits, little skew
It's possible to solve the 100 prisoner version so that the expected
number of days required is less than 5000. However, this algorithm
requires each prisoner to know the number of total visits so far, so
it doesn't apply to the 23 prisoner version described in the above
URL.
Nis Jorgensen
wrote:
>[1] The number is obtained using a computer simulation of my solution. I'd
>post the code, but it's in O'Caml, and the odds that people here speak
>O'Caml are probably nill.
Well, if it is similar in syntax to SML, I believe I would have a fair
chance of understanding of what is going on. But then, I believe I can
free the prisoners in around 10418 days on average.
--
Nis Jorgensen
Amsterdam
Please include only relevant quotes, and reply below the quoted text. Thanks
Michael Mendelsohn
> > > Michael Mendelsohn wrote:
> > > > --
> > > > When the tongue or the pen is let loose in a phrenzy of passion,
> > > > -- That Thomas Paine, "On Usenet"
> > >
> > > What I take it that is not the famous 18th century patriot, but another,
> > > modern Thomas Paine? Surely the oldtimer would not have
> > > written a document entitled "On Usenet".
> >
> is hidden genuine.
> >
> > Btw, I mangled my .sig still further in another recent thread message; to my
> > disappointment, noone has commented on it?. I hope you all enjoyed a
> > quiet chuckle anyway! ;-)
> >
> > Have fun with confusion
> > Michael
> > --
> > it is the pan, and not the tubject, that becomes exhausted.
> > -- Thomas Paine, "On Usenet"
>
> I saw this one at the time... Is this what you mean?
>
> When the tongue or the pen is let loose in a fit of rage,
> it is both the man and the speech that gets wild.
> -- Thomas Paine, "I did not write this"
Yes.
The problem with hiding something is this uncertainty: did people fail
to find it, or did they, having found it, deem it not worthy of reply?
And I must admit, the hidden things are often so trivial, they might
not rate a reply on their own. See my recent reply to Eytan in "odd
one out": it's either trivially obvious or completely
misunderstandable what I am referring to; in both cases, no reply will
be forthcoming.
Maybe I need to think this through a bit better! ;-)
Have fun with treasure hunts
Michael
--
When the tongue or the pen is let loose in a phrenzy of passion,
it is the man, and not the subject, that becomes exhausted.
Edgar De Blieck
EDEB
"Michael Mendelsohn" <news...@michael.mendelsohn.de> wrote in message
news:3D40F11E...@michael.mendelsohn.de...
Mark Pilloff
> Oleg schrieb:
> > Wow! This puzzle absolutely blew me away:
> >
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
> >
> > I found a solution that frees the prisoners in approx 4,200,000 days[1]
Can
> > anyone come up with a strategy that frees the prisoners faster?
>
> The problem is structurally the same as
>
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
> which Mark Pilloff mentioned yesterday. Since that challenge runs
> through the end of July, I'm going to wait until August until I
> discuss details.
>
is unknown whereas in the Berkeley puzzle the switch is known to be
initially off. This makes a difference.
Mark
Andreas Gunnarsson
> http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
On Fri, 26 Jul 2002, Mark Pilloff wrote:
> Not quite "the same." In the IBM puzzle the initial state of the switches
> is unknown whereas in the Berkeley puzzle the switch is known to be
> initially off. This makes a difference.
Also note that in the IBM puzzle the prisoners will always flip one
switch when they are in the switch room.
Andreas
--
Andreas Gunnarsson - zzl...@dd.chalmers.se
http://puzzles.zzlevo.net/
Michael Mendelsohn
> > http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
> > http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
>
> On Fri, 26 Jul 2002, Mark Pilloff wrote:
> > Not quite "the same." In the IBM puzzle the initial state of the switches
> > is unknown whereas in the Berkeley puzzle the switch is known to be
> > initially off. This makes a difference.
Yes. Also, the "1 visit per day" rule does. However, still no prisoner
sees the light unless in the room (else we can find out exactly when
the 100th prisoner enters the room for the first time).
> Also note that in the IBM puzzle the prisoners will always flip one
> switch when they are in the switch room.
I didn't see that as a structural difference - a non-switch in wwu's
riddle is a flip of the "unused" switch in the IBM riddle. Or were you
able to use the second switch to a more worthy end?
I am still chewing on the <5000 days solution hinted at by Uoti.
Have fun with well-lit prisons
Bertram Felgenhauer
> In article <3D3F0082...@yahoo.co.uk>, Phil Carmody wrote:
>>Michael Mendelsohn wrote:
>>> The problem is structurally the same as
>>> http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
>>> I haven't run a simulation yet, but I thought it might be done in the
>>> order of 20.000 days, maybe twice that.
>>From about 30 simulations
>>100 cons : 18284-24785 visits, but with a mean near 20500-21000
>>23 cons : 849-1202 visits, little skew
> It's possible to solve the 100 prisoner version so that the expected
> number of days required is less than 5000.
Got it to somewhat below 4000.
[spoiler ahead]
.
.
.
.
As before, the prisoners choose an 'announcer' among them.
Then they agree on the following procedure:
- each prisoner keeps a counter, which is initially 1.
- the bulb has a value assosiated with it, which is
- 0 for night number 0
- 1 for nights number 1... 800
- 2 for nights number 801...1600
- 4 for nights number 1601...2400
- 8 for nights number 2401...4540
- 2 for nights number 4541...5340
- 1 otherwise.
(day 1 shall be the day when the first prisoner enters
the room; the night number n shall be between the days
n and n+1).
- now, when a prisoner enters the room, he does the following:
- check if the bulb burns and add the value of bulb (for the previous
night) to their counter if that's the case.
- if the counter is 100 (this usually only happens for the
'announcer'), announce that every prisoner has been to the
room.
- for days 1..2400, if the binary representation of the counter
contains 1 in the digit corresponding to the value of the
bulb for the next night, switch on the bulb, switch it off otherwise.
- for days 2401 and the following days, if their counter is greater or
equal to the value of the bulb for the next night, switch on
the bulb, and switch it off otherwise.
- the 'announcer' switches the bulb off for days 801 and all following days.
- if the bulb is burning, reduce their counter by the value of the
bulb for the next night.
The idea here is to calculate the sum (which is known from the beginning)
of all the counters of the prisoners to a single prisoner (usually the
'announcer'). The sum
[value of bulb if it's burning] + counters of all prisoners
remains constant throughout the process, and all counters of the
prisoners remain non-negative. This means that if the counter
ever reaches 100 for a prisoner, all other prisoners have to
have been to the living room.
The speedup results from the fact that the chance that after the first
800 days, every prisoner's count is either 0 or 2, and that after the
first 1600 days every prisoner's count is either 0 or 4, and that after
the first 2400 days, every prisoner's count is either 0 or 8 except for
the 'announcer', and that after at most 4540 days, the 'announcer''s
count reaches 100 is pretty high.
Computer simulation of 500,000 runs gives:
average standard min max
deviation
3948.319 628.189 2850 10000
The parameters in the procedure were hand-tuned; so there
is no reason to believe that they're optimal.
Btw, for those who're interested:
A method which requires 4.2 Mio days on average is the following:
- assign each prisoner a number 0..99.
- again, each prisoner keeps a counter which is initially 0 though
(and serves a different purpose than the counter above)
- on each day, the prisoner entering the room does the following:
- let n be the day number, minus 1, modulo 100.
- if the bulb is off and n equals their number, set their counter
to n+1. announce that everyone has been to the room if
their number is 99.
- else, if the bulb is off and n is greater than our counter, set our
counter to n.
- switch on the bulb if our counter is less than or equal to n; switch
it off otherwise.
The problem here is, that to increase the maximum counter by one,
someone who knows the current maximum counter must enter the room
on a day with n=counter-1, and, on the following day, the prisoner
with the number equal to the current maximum counter must enter the
room.
regards,
Bertram
--
`.oo' "Do not meddle in the affairs of Wizards, for they
,. (`-' are subtle and quick to anger." -- J.R.R. Tolkien
'^\`-' ) "Do not meddle in the affairs of wizards, for you
c-L'- are crunchy and good with ketchup." -- Terry Pratchett
Ed Murphy
> Not quite "the same." In the IBM puzzle the initial state of the switches
> is unknown whereas in the Berkeley puzzle the switch is known to be
> initially off. This makes a difference.
The difference seems minimal. If N switches with a known initial state can
be solved in D days using solution S, then N switches with a completely
unknown initial state can be solved in D+N days using solution S':
Day (I = 1 to N): Whoever goes in there, they ensure that switch #I matches
the desired initial state. Either they flip switch #I, or they do nothing.
Day N+1 onward: Apply solution S, with all questions of "if I have entered
the switch room before now" changed to "if I have entered the switch room
before now, but after Day N".
--
Ed Murphy <emur...@socal.rr.com> "I'm not sure I can go through
http://members.fortunecity.com/emurphy/ with it. Leave, I mean."
Andreas Gunnarsson
> Mark Pilloff <md...@uclink4.REMOVETHISberkeley.edu> wrote:
>
> > Not quite "the same." In the IBM puzzle the initial state of the switches
> > is unknown whereas in the Berkeley puzzle the switch is known to be
> > initially off. This makes a difference.
>
> The difference seems minimal. If N switches with a known initial state can
> be solved in D days using solution S, then N switches with a completely
> unknown initial state can be solved in D+N days using solution S':
>
> Day (I = 1 to N): Whoever goes in there, they ensure that switch #I matches
> the desired initial state. Either they flip switch #I, or they do nothing.
But the prisoners go to the room "from time to time, when [the warden]
feel so inclined"; we can't be sure that a prisoner visit the room each
day.
Andreas Gunnarsson
> Andreas Gunnarsson schrieb:
> > > http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb
> > > http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html
> >
> > On Fri, 26 Jul 2002, Mark Pilloff wrote:
> > > Not quite "the same." In the IBM puzzle the initial state of the switches
> > > is unknown whereas in the Berkeley puzzle the switch is known to be
> > > initially off. This makes a difference.
>
> Yes. Also, the "1 visit per day" rule does. However, still no prisoner
> sees the light unless in the room (else we can find out exactly when
> the 100th prisoner enters the room for the first time).
>
> > Also note that in the IBM puzzle the prisoners will always flip one
> > switch when they are in the switch room.
>
> I didn't see that as a structural difference - a non-switch in wwu's
> riddle is a flip of the "unused" switch in the IBM riddle. Or were you
> able to use the second switch to a more worthy end?
No, what I meant but failed to say was that if the prisoners could choose
not to flip any switch it would be trivial to reduce the problem to the
other one by having one person flip switch A and the others turn on switch
B only if they haven't already done so for the current position of A.
Since they always have to flip one switch, that is not possible.
I actually don't have a solution for the IBM puzzle where they don't know
how often someone enters the room, they don't know the initial positions
and they always have to flip one switch. I'd like to think that it's
because I haven't had time to think much about it, but it could just be
that I am too stupid. :)
Carl G.
"Ed Murphy" <emur...@socal.rr.com> wrote in message
news:aCY09.81$Jz.1...@twister.socal.rr.com...
The visits in the IBM problem are not necessarily daily. Here are some
added issues presented by the IBM problem:
1. The initial switch states are unknown.
2. Each prisoner *must* flip exactly one switch when they visit the switch
room, they can't choose not to flip a switch.
3. The spacing between visits to the switch room may vary.
4. The prisoners are not told when other prisoners are visiting the switch
room (i.e., the only way that a prisoner can determine if someone else has
visited the switch room since his last visit is if at least one switch is in
a different position from the way he left it).
Carl G.
Michael Mendelsohn
> Mark Pilloff <md...@uclink4.REMOVETHISberkeley.edu> wrote:
> > Not quite "the same." In the IBM puzzle the initial state of the switches
> > is unknown whereas in the Berkeley puzzle the switch is known to be
> > initially off. This makes a difference.
>
> The difference seems minimal. If N switches with a known initial state can
> be solved in D days using solution S, then N switches with a completely
> unknown initial state can be solved in D+N days using solution S':
>
> Day (I = 1 to N): Whoever goes in there, they ensure that switch #I matches
> the desired initial state. Either they flip switch #I, or they do nothing.
Completely valid idea; it doesn't apply, though, because in the IBM
puzzle, noone knows whether he/she is the first person to enter the
room.
Tricky, huh?
Have fun with with superficial similarities
Oleg
> Ed Murphy schrieb:
>> Mark Pilloff <md...@uclink4.REMOVETHISberkeley.edu> wrote:
>> > Not quite "the same." In the IBM puzzle the initial state of the
>> > switches is unknown whereas in the Berkeley puzzle the switch is known
>> > to be
>> > initially off. This makes a difference.
>>
>> The difference seems minimal. If N switches with a known initial state
>> can be solved in D days using solution S, then N switches with a
>> completely unknown initial state can be solved in D+N days using solution
>> S':
>>
>> Day (I = 1 to N): Whoever goes in there, they ensure that switch #I
>> matches
>> the desired initial state. Either they flip switch #I, or they do
>> nothing.
>
> Completely valid idea; it doesn't apply, though, because in the IBM
> puzzle, noone knows whether he/she is the first person to enter the
> room.
>
> Tricky, huh?
>
> Have fun with with superficial similarities
> Michael
I actually solved and mailed the IBM version a few days ago. Let's withhold
all spoilers until August, gentlemen.
--
"It's because they're stupid, that's why. That's why
everybody does everything." -- Homer Simpson.