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

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #25 on: Jul 26th, 2002, 1:07am »

I don't have a problem with the 'leader' solution - after all, the problem does use the word 'eventually'.

I'm also not sure why things can only be done in sets of 100 days. Sure, you need a minimum of 100 days to get all the prisoners through (meaning that for the leader solution, you need 199 days - the leader has to enter once for each new entry by another), but once you pass that minimum, there is nothing particularly magical about the number 100 in terms of days spent.

Just pray that the guy in on the first day isn't big Bubba who has the intellectual capacity of fried lard...
 IP Logged
Kozo Morimoto
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #26 on: Jul 26th, 2002, 1:09am »

Maybe we could start by looking at a case where number of prisoners is small.

if the number of prisoners = 1, this is a trivial case.
if the number of prisoners = 2, again, this is a trivial case.
How would you do it for 3 prisoners?  How would you do it for 4 prisoners?  Can you then extrapolate to n=100?

What information do the prisoners have:
1) number of times he/she has been in the living room.
2) when he/she was in the living room (ie which days since the meeting)
3) the binary semaphore of the previous prisoner to be in the living room.

Any other info?
 IP Logged
Kevin
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #27 on: Jul 26th, 2002, 2:43am »

Take a situation with 4 prsisoners.  Number the days as follows:
1
1,2
1,2,3
1,2,3,4
(total of 20 days).
Each prisoner goes into the room and only turns (or leaves)the light on when he/she knows that the current day number is equal to (or less than) the number of prisoners that have been into the room.  Otherwise, the prisoner turns the light off.

If you go through it on paper with some people (A,B,C,D) trying various combinations of prisoners, repeat visits etc, you find that eventually each prisoner builds up knowledge of the number of people that have been into the room based on the state of the light when they enter.  When somebody goes in on day 4 and the light is on, bingo.

Extrapolate this to 99.... is it quicker than 27 years??  Of course, after a while you don't really need the lower numbers, so perhaps the system can be refined a bit.

 IP Logged
S. Owen
Full Member

Gender:
Posts: 221
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #28 on: Jul 26th, 2002, 7:11am »

I believe I have the answer. It does not assume things that probably aren't implied by the problem, like that the prisoners can see the light bulb from their cell, or that they can gather after the first day.

The idea is that the prisoners will use the state of the light switch to (gradually) communicate information about who has been in the cell, from one day's prisoner to the next, until someone knows for sure that they've all been in there.

The night before, they gather and assign themselves numbers from 0 to 99. They then agree on the following rules for what to do in the room:

1) Let D be the current day. If you know that prisoner # D(mod 100) has been in the room, leave the light on. If you do not know that, leave it off.
2) If the light was on when you came in, then you know that prisoner (D-1)(mod 100) has been in the room before - remember that.

For example, if I am prisoner #59, and go in on day 845, and I see the light on, I know that #44 has been in there. Furthermore, if I know that #45 has been in somehow, then I leave the light on to spread that info to the next day's prisoner.

This process only gets started when some prisoner X goes in on a day that is equal to X, modulo 100 (i.e., #33 goes in on day 433, and since he obviously knows that #33 has been in the room since he's there now,  he leaves the light on. If tomorrow, #78 walks in, now #78 knows that too).

Eventually the info will spread enough so that someone knows for sure everyone has been in the room.

I ran a little simulation, and with 100 prisoners, it takes them about 95,000 days on average to know they've all been in there (though on average they will all have visited after about 450 days).
 IP Logged
biwema
Newbie

Posts: 5
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #29 on: Jul 26th, 2002, 7:42am »

Hi,

At the moment I don't know a better 'save' solution than this one with the prisoner who counts the people by only switching off the light. As they have to wait for 27 years on average, I would gamble a little bit if I were in that situation.

To be a little bit more sure, I use the switch as parity counter. Every prisoner toggles the switch only the first time when he goes to the room.

after one year, the probabilities are:

100 people have visited the room ~97%
99 people have visited the room ~3%
98 people have visited the room 0.085%
97 people have visited the room 0.002%

So, if after one year the light is off, it is 99.9% probable that everyone has vistited the room. If the light is on, it is 99.9% probable, that exactly 99 people have been in the room (97 people: 0.09%). In that case that person who hs not been to the room yet, can make the statement, that now everybody has been there when he visits the first time.

I think tis is much better than 27 years even if there is a small risk remaining. If you are a coward, just wait 2 years. The probability of being killed is 1/1000000 then.

hope that helps
 IP Logged
S. Owen
Full Member

Gender:
Posts: 221
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #30 on: Jul 26th, 2002, 8:05am »

I think the problem is asking for a mechanism by which the prisoners can be 100% sure that all have visited, instead of a probabilistic answer.

In a matter of just years, the probability would be extremely small that there was still someone who hadn't visited. So prisoners could take this gamble approach without any prior discussion, or any use of the lightswitch whatsoever, and get out in a few years.

See above for a 100% solution (albeit one that takes centuries!)
 IP Logged
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #31 on: Jul 26th, 2002, 9:16am »

I think the trick to this question is the line that states "he needs to murder no more than 10 prisoners".  Thus, you have up to 10 prisoners to play with.

Here's the way I see it,

Divide the 1000 bottles by 2, and assign 1 prisoner to each half.  Divide each half by a half and assign prisioners to each new half.  Divide the halved halfs by a half and assign a prisioner to each new half. Continue dividing by a half till your left with 1 prisioner assigned to 1 bottle.   You will noticed, if you count the divisions, that there are up to 10 division (some cases less).

If you have your prisioners drink this way, up to 10 will be murdered and you will have found the poisoned bottle.

One question though, this method uses almost 10 times the number required if you assigned one prisioner to one bottle.  So, I don't beleive it's the final solution.

Any other ideas?
 IP Logged
S. Owen
Full Member

Gender:
Posts: 221
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #32 on: Jul 26th, 2002, 9:21am »

You are talking about a different problem!
 IP Logged
Salem
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #33 on: Jul 26th, 2002, 2:33pm »

on Jul 25th, 2002, 9:11am, AGirl wrote:
 The fastest way to get the cons out (without resorting to weasles like marking things on the wall or being able to see the light) I can find is the following:   Info: 100 cons, 1 bit info transfer, random selection of cons.   You can only work in cycles of 100 days. Someone posted that solution already, but in stead of resetting every cycle you should reset but keep counting cycles.     The cons agree that they do not swich on the light, unless they have visited  the room more than once in the first cycle. If the light is switched on by someone, the cons know that soemone has been in twice and that at least one person has not visited the room. They have to wait until the end of the cycle and don't do anything.     The first one to start the second cycle switches off the light if he has been in the room twice or less (twice, because it's the second cycle). The light stays out unless someone comes into the room who has been in the room three times or more. Then the light goes on. If the light is on, it stays on for the rest of the cycle and the cons, again, know that chances are that at least one person has not been in the room and do nothing. In the third cycle the light only goes on if someone has visited 3 or more, in the 4th cycle 4 or more, etc.   If OTOH, at the end of a cycle, the light is out (i.e. every con has visited the room a number of times that is equal or less to the number of cycles that have passed) the first con of the next cycle can declare freedom.

This solution does not work. Imagine the following distribution:
First 100 days:
1 poor guy gets selected 50 times
50 guys (call them "group a") gets selected once
Second 100 days:
48 previously unselected people get picked twice
4 people from group a get picked

Nobody in the second group was picked twice, and yet there is still
one person who has not been in the room.
 IP Logged
waka
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #34 on: Jul 26th, 2002, 9:37pm »

Here is my answer for the question, which I believe is correct.  It is a variant of the leader solution previously proposed.

The prisoners all gather the first night a choose a leader.  They impose the following rules:
- When any person other than the leader enters the room for the first time, they may turn the light on if it is off.
- When the leader enters the room, he adds one to his count of prisoners that have visited the room if the light is on.  He turns the light off before he leaves.
- When a person who has previously turned the light on enters the room and finds the light off, they may not turn it on.

When the leader's count reaches 99, he knows that every person has visited the room.  The light being on means "at least one new person has visited since my last visit."

Yes, this will take a long time.
Yes, it is a solution, as the question says nothing about a time limit.

This can be proven with a simple case of 4 prisoners:

Say Person #1 is the leader.
The light starts out off.

First, person #3 goes in.  He finds the light off so he turns it on.

Next comes #4, #3 again, and #2.  They all see that the light is on so they do nothing.

After this, say #1 comes back in.  Since he is the leader, he finds the light on and adds 1 to his count (making his count "1").  He turns the light off.

Next #3 comes in again, but since he previously flipped the switch, he leaves the light off.

After that, say #4 comes in.  The light is off and he hasn't turned it on before, so he turns it on.

Then, #2, #3, and #4 all come in several times.  They all leave the light alone because it is on.

The leader, #1, comes in again and finds the light on, so he adds 1 to his count, making it 2. Again, he turns off the light as he leaves.

Next come in #4 and #3, but since they have both flipped the light, they leave it alone.

Eventually, #2 comes in again, but since he hasn't flipped on the light yet, he turns it on.

After this, any combination of #2, #3, and #4 can come in.  They will all leave the light alone as it it already on.

Finally, when #1 comes in again, he sees the light is on, so he adds one more to his count, making it 3.  Since he can count himself as well, he knows that all 4 people have visited the room at least once.  He can now declare with absolute conviction that they have all visited the room.

Note that the number of prisoners and the order they come in doesn't matter.  Expand this to 100 prisoners or N prisoners, and it should work.

waka
 IP Logged
Mark Ebden
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #35 on: Jul 27th, 2002, 10:20am »

Hi,

I like Waka's solution, although for N=100 it will of course take several decades to execute.  If the leader happens to arrive in the room in short intervals (< 100d) at first, and longer intervals (> 100d) later on, the prisoners can get out in less than 20 a.  If the reverse occurs, they'll be there for over 50 a.  Average should be 30-something years.

Now let's think about that.  An average of more than three whole DECADES.  Compare it to the probability-focused answer earlier, in which prisoners were let out in two years with 99.9% certainty, or, not as good, let out in one year with 97% certainty.

Taking a vote amongst the 100 prisoners, how many are going to say, "well, that 0.1% chance is big enough that I will waste my life in jail instead"?

Exactly.  So I think the real answer to this riddle is, "Any solution that requires 100% certainty runs the risk of taking too long.  Hence, the probabilistic approach is best."

But I do like Waka's solution if we need precision.

Cheers,

Mark
 IP Logged
Mark Ebden
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #36 on: Jul 27th, 2002, 10:22am »

Testing... not sure if the last message got through.
 IP Logged
cnmne
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #37 on: Jul 27th, 2002, 10:34am »

If they just waited a few years, and occasionally flicked the bulb to pass the boredom, these would be the odds that a prisoner was never selected, with a leap day after 3 years:

1) it would be a miracle.
2) 93.48833%
3) 99.83549%
4) 99.99580%
5) 99.99989%

Technically, there is always a chance that a prisoner is not selected, even after they all die of boredom (or old age).  Being criminal masterminds, they probably choose five years and 1/100000 odds over a life sentance and accuracy.

If they are criminal retentives instead, the carry bit prisoner (one guy flicks off and carries 1 bit register overflow, everyone else flicks on first visit) is a real solution.  Assuming average distribution, 27 years seems a long time to wait.  After half that time the odds that they have all been in the room are a lot better than the odds of a spaceship crash landing on the prison.
 IP Logged
cnmne
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #38 on: Jul 27th, 2002, 10:47am »

above are the odds that all prisoners visited the room, not that 1 prisoner did not.
 IP Logged
S. Owen
Full Member

Gender:
Posts: 221
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #39 on: Jul 27th, 2002, 11:00am »

I like Waka's solution more than mine as it appears to work faster. It also guarantees success, which is the intent of the problem, I imagine.

I think it needs one tweak though:

"- When any person other than the leader enters the room for the first time, they may turn the light on if it is off."

Should this not be:

"-When any person other than the leader enters the room, and has never turned the light on, they may turn the light on if it is off."

It's not just the first time they enter, as they may enter for the first time while the light is on.
 IP Logged
Eyal Peer
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #40 on: Jul 27th, 2002, 6:28pm »

Waka's solution does not work.
You can always find a pattern in which everyone has used their "First time - turn on" option, but no one ever counts 100.

I know, since I thought of a solution just like this myself untill some mathematician I talked to disproved it.
 IP Logged
waka
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #41 on: Jul 27th, 2002, 11:07pm »

srowen-
Yes, you are correct.  A prisoner is only allowed to turn on the light iff they have never turned it on before.  Sorry, that should have been more clear.

Eyal-
I remain unconvinced that my answer is wrong.  Can you provide an example (or even better, a proof) of when my solution fails?

As I stated before, nothing about the riddle states that it must be completed in a certain amount of time.  Frankly, I don't care what the context of the problem is... the riddle is not asking for a solution that is the most realistic.  It is asking for a solution that is 100% reliable, given infinite time.  I don't find the probability solutions adequate because they fail to answer the riddle... they are solving the context and not the riddle's requirements.

So, if my solution does indeed fail, I'd love to know when!

waka
 IP Logged
tim
Junior Member

Posts: 81
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #42 on: Jul 28th, 2002, 12:20am »

Waka: Your answer works with probability 1.  To a mathematician, that is not the same as saying that it always works

One example where it fails is if the leader is only ever picked 90 times.  Yes, the probability of such a sequence goes to zero as time goes to infinity, but there are an infinite number of infinite sequences that have this property.

In fact, there is technically no guarantee that all prisoners will ever visit the living room.  Again, the probability is zero, but "probability zero" does not mean "impossible".
 IP Logged
Salem
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #43 on: Jul 28th, 2002, 6:49am »

Here is a modified solution which could cut down on the expected time it would take for the prisoners to get out.

It is based on the "leader" idea, but you get a good jump start

The first person to go in the room 2 times is the "leader".
He turns on the light. If he goes in for the second time on
day 65, then he knows 64 prisoners have been in the room.
Nobody does anything else until the 100th day.

Note: this first set of 100 days creates four groups of prisoners:
Group A) inmates that entered the room for the first time and the light was off.
Group B) inmates that entered the room for the first time and and the light was on
Group C) inmates that did not enter the room
Group D) the leader who entered the room twice and turned on the light.

The person that gets picked on the 100th day has a special job. If they are from group A or group D, they turn off the light. If they are from group B or C, they leave the light on.

After the first 100 days, the solution is just like the "leader" solution. Here is what each group does the next time they are selected:

Group A) nothing, they have already been counted
Group B) turn on the light the next time they enter the room and the light is off
Group C) turn on the light the next time they enter the room and the light is off
Group D) turn off the light if the light is on, decrement the number of people left to enter the room.

This could cut off a significant number of
 IP Logged
dlau
Newbie

Posts: 3
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #44 on: Jul 28th, 2002, 11:22pm »

I like my friend's solution, where everyone defecats in the corner once, and when there are 100 pieces, the prisoner will tell the prison guard. (or a slightly more reasonable soln of breaking the lightbuib into 100 pieces)

David
 IP Logged
johnP
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #45 on: Jul 29th, 2002, 2:05am »

Heh, I'm no expert, but these are my thoughts on the subject:

1) There's no way to make sure all the prisoners will be picked by the warden. No matter how many years pass, you can never be 100% sure all the prisoners get picked.

2) Each of the 100 men live in solitary cells. When you consider that they are allowed to hold one meeting, while remembering how small a solitary cell is (certainly not big enough to hold 100 persons, assuming it's not some crazy hotel-sized solitary cell), it's sort of obvious that the only place to hold the meeting is in the living room.

Thus, the prisoners should agree to meet on day one. Then they will all have visited the central living room, and they're all free to go.

Another solution is equally simple: When a prisoner is picked to go to the living room, he stays there (in other words, he doesn't return to his cell). After 100 days, they talk to the warden. This solution is worse though, since it takes 100 days for them to get out of prison. It however covers the possibility that the prisoners are supposed to visit the livingroom AFTER the meeting they're allowed (the meeting doesn't count as a visit).

I might be totally wrong here of course. Maybe there is a solution? But if each man goes back to his cell after visiting the living room, I can't see how it's possible to make sure they all visit the living room. It sure is likely in the long run, but not much to base an escape plan on. They simply cannot devise a plan when someone eventually will be certain that 100% of the prisoners have visited the room.
 IP Logged
francois
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #46 on: Jul 29th, 2002, 5:37am »

I ran some tests :
1 prisonner/day approach (with knowledge propagation) : about 100000 days
wait for 100 day cycle were each prisonner has gone in the room once : too long

I think Salem's variant on the leader approach is interesting but wouldn't yield that big an improvement for N=100 as you'll probably only have a 10 to 20 person headstart (rather than the 64 in the example).

I've tried variants on the 1 prisonner/day approach: more generaly instead of associating one prisonner per day, you could associate a group of prisonners in order to spread the information faster among all prisonners. For example (for N=4):
day 1 : {1}
day 2 : {2}
day 3 : {3}
day 4 : {4}
day 5 : {1, 2}
day 6 : {3, 4}
day 7 : {1, 2, 3, 4} // actually this one is a bit stupid
However testing showed it's generally worse than the basic approach.

I wonder if there's a significantly better solution. I think this riddle is very interesting but not very "riddlish" - I don't think there is a clear solution. It has more of a information theory problem feel.
 IP Logged
David Gómez Noguera
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #47 on: Jul 29th, 2002, 6:56am »

here is a new solution, based on a propagation solution posted here.
each prisioner will be asigned a number, corresponding to a day on a 100 days cycles.
Prisioner 1 will turn on the light if he enters on the first day of the cycle, always.
Prisioner n will LEAVE the light on ONLY IF:
he entered on day n and the light was on (duh!) thus meaning that prisioners 1 through n-1 have been in.
he entered on day k, and some other day he entered on day k+1 and that time the light was on (thus meaning that he knows prisioners 1 through k have been in) (of course, if he does not know, but it has happened before, the prisioner k+1 wouldnt know... error probability)

Then after a 100 day cycle, prisioners could roll numbers so that 1 is now 100, and 2 is 1... and 100 is now 99.

Have never been good at probs, so i dont know  the odds.
 IP Logged
Salem
Guest

 Re: How to Solve 100 prisoners & Light bulb?   « Reply #48 on: Jul 29th, 2002, 7:04am »

Francois,
My modification may "only" buy you 10-20 prisoners, but that is 10-20
cycles which have an expected period of 100 days. That is some
significant time when you are in jail

Also, the modification gives you a (very small) chance of getting out in 100 days.
 IP Logged
Gamer555
Newbie

Posts: 19
 Re: How to Solve 100 prisoners & Light bulb?   « Reply #49 on: Jul 29th, 2002, 8:26pm »

Phew! So is nobody (besides maybe Eyal) protesting the "leader" solution (turn it off and add one to count if on)

PS: Tim is right. No solution (besides the silly ones) will work, cause the warden could just not ever put 1 prisoner into the room! Oops! If we had a guarentee that SOMETIME all prisoners would be put into the room (which I think we'd have to assume) we could use the 'leader solution'.

Phew! 3 pages isn't easy to read!
 IP Logged
 Pages: 1 2 3 4  ...  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 »