wu :: forums « wu :: forums - 100 prisoners & a light bulb » Welcome, Guest. Please Login or Register. Jan 19th, 2022, 11:08am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, ThudnBlunder, Eigenray, Grimbal, SMQ, towr, william wu)    100 prisoners & a light bulb « Previous topic | Next topic »
 Pages: 1 ... 18 19 20 21 22  ...  25 Notify of replies Send Topic Print
 Author Topic: 100 prisoners & a light bulb  (Read 161134 times)
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: 100 prisoners & a light bulb   « Reply #475 on: Sep 15th, 2005, 6:33pm »

But with 100 prisoners all those 1%'s add up...  based on around 8 million trials, I get the average number of days until all prisoners have been chosen as 518.65

--SMQ
 IP Logged

--SMQ

Guest
Guest

 Re: 100 prisoners & a light bulb   « Reply #476 on: Sep 18th, 2005, 11:35am »

Sorry, I haven't read all of the posts (so excuse me if I am repeating someone's arguments). All I can say is the 'leader' solution is absolutely fine, with one exception:
The initial state of the light switch is unknown. Suppose the light switch is initially ON. The leader flips it OFF and raises his count by 1, thus being mistaken. If he counts 99 flips, he cannot be sure all of his 99 fellow prisoners entered the room (he can miss a person).
He needs to count 199 flips, and prisoners must be allowed to turn the light on for the second time too.
With that slight modification, it guarantees 100% success.

This is the desired solution, since the problem clearly says that the prisoner who decides to make the statement wants to be 100% sure he is correct.
Some can argue it can take infinite time, but the problem's conditions imply that everybody visiting the room can also take inifinite time, given that the warden picks the inmates randomly.
 IP Logged
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #477 on: Sep 18th, 2005, 11:42am »

Guest,

The first person in the room can simply initialise the bulb to an agreed upon initial state.
 IP Logged
Guest
Guest

 Re: 100 prisoners & a light bulb   « Reply #478 on: Sep 18th, 2005, 11:44am »

Sorry for double-posting, but I have noticed that Salem's solution has a major flaw:
They decided that the first person who enters the room twice becomes the 'leader'... but how can a prisoner know that he is the first to visit the room twice? AND how do others know that he is the leader (from that moment)?
This approach is wrong, since the prisoners cannot exchange information by any means.
If they could have, the solution would have been reduced to this nonsense:
"When a prisoner enters the room for the first time, he lets the others know, and the 100th prisoner can state with certainty that every prisoner has been in the room."
Which is absurd, since the light switch becomes useless and the solution is trivial.

The bottom line is: nice try, but they cannot exchange information. I am convinced the 'leader' solution above is the correct one.
 IP Logged
Guest
Guest

 Re: 100 prisoners & a light bulb   « Reply #479 on: Sep 18th, 2005, 11:58am »

mattian, what you mean is that the first day is devoted to initializing the light switch to OFF. Okay, I agree, but that is acceptable only if they can keep track of time.

I also heard other variants of this problem, where the warden can summon a prisoner whenever he wants (meaning more than a prisoner per day, and also in non-regular time intervals). And what if they don't know what day it is? They cannot exchange info, they are in solitary confinement...

I'd like to think that the 199 count 'leader' solution is more general and is time-independent.

(N.b sorry for tripple posting, really really sorry)
 IP Logged
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #480 on: Sep 18th, 2005, 12:04pm »

No - what I mean is that the first prisoner (without having to dedicate his entire visit to initialising the bulb) can enter the room, initialise the bulb to the agreed upon state, and then, during the same visit, set the bulb's state according to the particular strategy.
 « Last Edit: Sep 18th, 2005, 12:06pm by mattian » IP Logged
Guest
Guest

 Re: 100 prisoners & a light bulb   « Reply #481 on: Sep 18th, 2005, 12:36pm »

Combine the first and second day into one, or don't, that's not my point.
My point is that the 199 count solution is general and time-independent and doesn't require the problem to formulate conditions such as:
- The warden must summon one and only one prisoner to his room, every day.

All I'm saying this solution is more general. It is even a solution to the same problem, with more strict rules, like:
- The warden can summon a prisoner to his room whenever he wants (as many prisoners as he wants per day, and in non-regular time-intervals too). Which implies he can decide not to summon prisoners at a certain day.
And those rules only present more difficulties to time-dependant solutions, where prisoners have to count days.
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #482 on: Sep 18th, 2005, 7:14pm »

Yes, that is a solution to the more general problem. But as I just pointed out to thrillseeker a few days ago, the discussion in this thread is about the specific problem where the warden chooses exactly one prisoner a day, and the prisoners are able to keep track of days.

Just about every solution in this thread (except the oft repeated trivial "leave a mark" and "the meeting was in the room" solutions) was given with these assumptions, and should only be interpreted in the presence of these assumptions. I.e., you have not spotted a major flaw in Salem's solution - you have just noted that it does not apply to situations other than the one Salem offered it for.

The more specific problem addressed here is quite interesting in its own right. Because the prisoners are able to track days, they have the capacity to greatly reduce their expected release time over that available even under Salem's shortcut (refered to later in the thread as a "snowball round"). Paul Hammond suggested a means to cut Salem's time by nearly two-thirds. To read up on the ingenious solutions offered by Paul and by his successors, you can read through the thread, or else, read the summary I gave starting here. Note some of the numbers I gave were out-of-date even when I gave them, and there were some improvements since that summary, which you will have to find by reading onward. Mattian in particular has done much to improve our understanding of several of the schemes that I never incorporated. (Also, I fully admit that the summary is not easy reading - I had to do a lot of both condensing, and fleshing out concepts not fully explained when originally posted.)

The situation wherein the prisoners are not picked once a day (or are not able to track days), and wherein they do not know the state of the bulb is also valid, but should not be mixed with this discussion. If you would like to explore it more, I strongly urge that you start a new thread. It has been partially addressed in the "100 prisoners and 2 light bulbs" thread, but as the name indicates, that thread also introduces a second bulb to the situation.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
mattian
Senior Riddler

Gender:
Posts: 404
 Re: 100 prisoners & a light bulb   « Reply #483 on: Sep 18th, 2005, 7:28pm »

on Sep 18th, 2005, 7:14pm, Icarus wrote:
 Mattian in particular has done much to improve our understanding of several of the schemes that I never incorporated.

Maybe I'll finish what I started with that one day when I'm not working 16-7.
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #484 on: Sep 18th, 2005, 7:46pm »

You will notice that I never updated my summary with your new values, like I said I would, either. So I am not about to scold you for not finishing your review!
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Ed W
Guest

 Re: 100 prisoners & a light bulb   « Reply #485 on: Sep 22nd, 2005, 8:57pm »

ok people if this is crack pot please let me know, but if I was a prisoner in this situation this is what i would do.
Forget the light switch that helps you none. You have to devise a plan that you can measure. so i propose this.
First, if you can leave things in the room, just have a prisoner leave a shoe, shirt, or something accessable to all prisoners, once you have 100 shoes, shirts, or something else you would know all people have been in it at least once. Obviously if you already left a shoe dont leave another one.
If this option is not available I would turn my attention to the light bulb. I would instruct the other inmates to use the light bulb as a measuring tool. Tell the inmates to start at a wall (North, South, East, or West), then unscrew the light bulb and place it flat on the floor against the wall. Then when the next person comes in have them move the bulb one full light bulb in front of the previous spot. Once you get far enough you should be able to measure how many 'bulbs' away the bulb is from the starting wall, once your 100 bulbs away from the starting point you've got it.
Ok people, tell me what you think, I dont have a fancy math equation to tell how many days it will take but it seems that these two ideas would work. this is what i would do so its the best i got.

e
 IP Logged
BNC
Uberpuzzler

Gender:
Posts: 1732
 Re: 100 prisoners & a light bulb   « Reply #486 on: Sep 22nd, 2005, 9:05pm »

on Sep 22nd, 2005, 8:57pm, Ed W wrote:
 ok people if this is crack pot please let me know,   e

Hi Ed,

This answer is not "crack pot" as you call it, but it was proposed numerous times before. If you can find the time to read through it (rather long) thread, you will find many of this type of suggestions, and the general agreement among the forum regulars that it is more interesting to solve it "within the box" -- with the fancy math.
 IP Logged

Edward Smith
Guest

 Re: 100 prisoners & a light bulb   « Reply #487 on: Oct 16th, 2005, 5:44am »

I don't think anyone has proposed a solution in n time.  The puzzle page defines 'optimum' as least amount of days, not most number of prisoners.

If each prisoner just claims that he is the 100'th, then on the 100th trial, one prisoner will go free.

Voila, no?

Edward
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: 100 prisoners & a light bulb   « Reply #488 on: Oct 16th, 2005, 9:38am »

Not really.  The problem states:

"The prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity."

There is only one chance, then the game is over.  I understand this as meaning the claim must be made only with 100% certainty to be true.  This being said, probabilistic solutions have been given in this thread.
 IP Logged
JocK
Uberpuzzler

Gender:
Posts: 877
 Re: 100 prisoners & a light bulb   « Reply #489 on: May 8th, 2006, 11:52am »

The light bulb is a red herring. A perfectly acceptable solution (no secret signaling, no telepathy, no cheating, ...) exists that does not use the light bulb and that:

1) allows the prisoners to make their claim immediately after the 100th prisoner has visited the living room

2) reaches a degree of certainty that is as close to 100% one desires (provided one is willing to increase the amount of preparation).

Will post the solution later...
(no kiddin' don't want to spoil another - related - thread)

 IP Logged

solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.

xy - y = x5 - y4 - y3 = 20; x>0, y>0.
ctsio
Newbie

Posts: 1
 Re: 100 prisoners & a light bulb   « Reply #490 on: May 28th, 2006, 3:13am »

ok here is the best solution which I have come up with so far.

On the first day, the first prisoner enters the room and turns on the light because it is his first time in the room.

For every day which follows, if a prisoner enters the room and it is their first time in the room then they leave the light on.

After a period of time eventually one prisoner will enter the cell for their second time. Call this person the LEADER. On the day that this happens the LEADER will know how many people have been in so far. E.g if the LEADER is found on day 50 then 49 people have been in the room for their first time. (I.e we don't include the LEADER twice )

From that day forth, if a person enters the room and has already been in there before they do nothing. If a person enters the room and the light is off and it is their first time in the room they turn it on. This signals to the LEADER that a new person has been in the room. If a person enters for the first time and the light is already on they do nothing because that means someone else is already signalling to the LEADER that they have been in the room for the first time.

Basically the LEADER, every time they enter the cell, if the light is on then they add 1 to the tally and turn the light off. If the light is already off they do nothing.

When the LEADER has counted to 100 then they are free.

 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: 100 prisoners & a light bulb   « Reply #491 on: May 28th, 2006, 7:14am »

So, what happens when prisoners A,B,C arrive in the sequence
A,C,A,B,C
Wouldn't C as well as A think they're leader?

You could amend it by never switching on the light for the first 100 days (except by the first prisoner), this way there can be only one leader. (As there is guaranteed to be a double, or the last prisoner knows all have been there)
 « Last Edit: May 28th, 2006, 7:23am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
alien
Guest

 Re: 100 prisoners & a light bulb   « Reply #492 on: May 29th, 2006, 1:44pm »

 « Last Edit: May 29th, 2006, 5:15pm by alien » IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #493 on: May 29th, 2006, 5:01pm »

A summary of the methods suggest at the time is available on page 16 starting here. I admit it is not easy reading, but it still beats the heck out of reading through the first 15 pages. It also puts most of the "in-the-box" solutions into a common idiom, which makes it easier to interpret new ones.

Your solution seems to be a variant of the single solution that I did not put in that idiom. Of course, part of why I didn't bother to translate that one was that it was extremely long running.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: 100 prisoners & a light bulb   « Reply #494 on: May 30th, 2006, 8:34am »

Also, the current leader (with an average runtime of 3460 days) is detailed in this post by Leonid Broukhis which refines this post of his which builds on this post of mine which describes a refinement of this post by gypo which is the last method described in Iacrus' summary.

--SMQ
 IP Logged

--SMQ

Sjoerd_de_Vries
Newbie

Posts: 1
 Re: 100 prisoners & a light bulb   « Reply #495 on: Jun 29th, 2006, 2:38am »

Hello guys,

I would like to present not a solution but two frameworks that provide a mechanism for the guaranteed optimal solution within those frameworks. I believe that all current solutions without pre-defined roles fit into those frameworks, except the idea of non-equal sized tokens.

The first framework is about token transfer. A prisoner initially has one token. When a prisoner enters the room at day t, and the light is on, he receives an amount of tokens equal to the pre-defined quantity from the previous day, x(t-1). Then, if his current total of tokens is larger than the pre-defined quantity of today, x(t), he turns the light on and subtracts x(t) tokens from his inventory. However, he will not do this if his inventory contains more tokens than y(t). Therefore, a solution can be generalized to a set of x and y values for each day.
It has been suggested before on this forum as a radically different solution, however most solutions are just a special case of this general scheme.
A snowball stage can be easily coded into this scheme by incrementing x(t) by 1 each day while keeping y(t) to infinite, and in a later stage x(t) can be set to v and y(t) to v+1, where v is the amount of tokens that an assistant leader has to collect.

The second framework is about the distributions of tokens. You can sort the number of token each prisoner has from high to low. The initial distrbution is 1, 1, 1, [ 1 ]97 (so 100 x 1), while the terminal distribution is 100,  0, 0, 0, [ 0 ]96 (1x 100 and 99 x 0). There are about 190 million of these distributions, and at any step the current state can be described as a 190 million x 2  matrix. The first element codes for the probability of that distribution to be present, while the second element codes for the probability that the light is on if that distribution occurs.
Now, you can carefully keep track of this matrix and assess the effect of every operation. In addition, you could devise a scoring scheme for each distribution, being dependent on the inequality (the more unequal the distribution, the better), the probability of the light being on, and the amount of tokens that the light encodes (which is the same for every distribution). Once you have done this, you 1. don't need to simulate anymore; 2. can incrementally optimize your solution for every single day, independent of what happens on other days.

So the only thing that needs to filled in is the scoring scheme, which would probably involve some kind of entropy; an information theorist (which I am not) should be able to provide it.

My apologies for this very lengthy post.
 « Last Edit: Jun 29th, 2006, 2:45am by Sjoerd_de_Vries » IP Logged
alien
Guest

 Re: 100 prisoners & a light bulb   « Reply #496 on: Sep 5th, 2006, 11:19am »

Fellow riddlers. I have but an optimal solution, which works in one day. Little did we know, that one of the prisoners is Bruce Lee. So when they meat in the courtyard, to discuss the optimal solution, he applies his martial arts, and snaps all their necks. And since he is the only prisoner left, when the warden takes him to the central room with one bulb, he declares that all prisoners have been to the room, and takes the bulb with him as a souvenir.
 « Last Edit: Sep 5th, 2006, 11:23am by alien » IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: 100 prisoners & a light bulb   « Reply #497 on: Sep 5th, 2006, 11:43am »

You know, of all of the "thinking out-of-the-box" solutions, I believe this is the first time selecting a leader by preemptively killing the other 99 prisoners has been suggested.

--SMQ
 IP Logged

--SMQ

Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: 100 prisoners & a light bulb   « Reply #498 on: Sep 8th, 2006, 6:17pm »

Alas for Bruce, the warden demands that someone announce when all 100 prisoners have visited the room. And worse, the warden does not bring dead prisoners to the room, so all 100 will never visit.

And worse yet, the prison has hired real guards, who know how to shoot their guns and are quite willing to do so, not hollywood guards who either abandon their guns in a show of machoistic idiocy, or stand around like imbeciles until he finishes off the closer guards. This means Bruce has no chance for escape.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
flamingdragon
Uberpuzzler

Gender:
Posts: 671
 Re: 100 prisoners & a light bulb   « Reply #499 on: Nov 15th, 2006, 4:34pm »

Has an answer been found to this yet and what is it if there has been one?

I don't want to read through 20 pages looking for the answer.
 IP Logged

"The fool doth think he is wise, yet the wise man knoweth himself to be a fool"

"He who commands the past, commands the future. He who commands the future, commands the past."
 Pages: 1 ... 18 19 20 21 22  ...  25 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »