One prisoner is designated to turn the light off. Only this designated prisoner may turn the light off. The rest of the prisoners are instructed to leave the light alone unless it is their first time in the room when the light has been off. In this case the prisoner will turn the light on. After the designated person turns the light off 99 times he can demand their freedom.
Not particularly elegant I grant you but guaranteed to work. It seems wasteful as once the light is on, all prisoners waiting to turn on the light have their turns wasted until the designated prisoner gets picked.
No. 2:
This solution relies on the prisoners being able to count days and cycles.
Starting on the day of the meeting, each prisoner starts counting days up to 100. This is one cycle. Once a cycle has been completed they start counting again.
During a cycle, as each prisoner enters into the room, they agree to leave the light in the off position. If, however, they have been in the room once before during this cycle, they turn the light on. Once the light is turned on it must remain on for the rest of the cycle to act as a signal to the rest of the prisoners that someone has been in the room more than once in this cycle (and hence someone will not have been in the room at the end of this 100 days.) On the 100th day the prisoner turns the light off, starting another 100 day cycle. If, on the last day of any 100 day cycle, the light is off the prisoners can demand their freedom with certainty knowing that everyone has been in the room.
I don’t like this solution; it isn’t very efficient as it throws away lots of data at the end of each cycle. The prisoners, most likely, be pushing up daisies before they get out. However, I think I might be able to tune this solution up.
Neither of these solutions is guaranteed to be optimal (i.e. It is highly likely that by the time they demand their freedom all of the prisoners will have already been in the room multiple times.)
Is there a solution guaranteed to be optimal? Can we find it? If not I still feel there has to be a better, more elegant solution than these two.
If it is the prisoner’s first time in the room, he toggles the light bulb. If it is a repeat visi, he does nothing. So, when the light bulb has been toggled 100 times (ON 50 times, OFF 50 times), the next prisoner can set them all free. Seems too simple…
That is too simple. How do you know when the light bulb has been toggled 100 times?
I’m curious as to what we mean by “optimal”. If our solution guarantees that we assert the claim on the first time that the last prisoner to enter the room enters the room, then we definitely have the optimal solution. But what if no such solution exists? The one that minimizes the expected duration before the claim is asserted?
Also, the solutions in the OP would work just as well for 4 or 60 or 2000 prisoners as for 100. Which makes me somewhat skeptical…
ObiWan, it’s common courtesy to indicate where you got a puzzle. I’m guessing that you got this one from William Wu’s riddle page, linked to in Weird Earl’s about a week ago. If you poke around on that site, you’ll find that it has a message board where this problem has already been discussed in some depth.
Looks like the answer they came up with on that site is as follows:
1. Designate one person to announce their freedom. Have each prisoner turn the light on during their first time in the room, and when the designee gets to the room, he turns it off. Once he’s turned it off 100 times (or 99 for himself), he says they’ve all made it.
That method is guaranteed to work (barring human error), but it would take an incredibly long time.
Why 100 times? I haven’t done the math but if any one person has been in say 20 times what are the odds that there is someone who hasn’t been chosen at least once? Similarly one person turning the light off 100 times does not garantee everyone else has been in the room(if the selection is truly random, if just the order is random then they just have to wait 100 days and everyone will have been through).
I think the only way to get the answer is going for statistically best chance. There is no way to be sure if the system is truly random. As far as I can tell there is no way to communicate 100 bits of information(every prisoner’s status) through the two bits of info available to each individual prisoner(two bits=the last prisoners choice and his own situation).
If you have never turned the light on before, turn on the light.
Leave room.
Wait to be chosen or released.
If chosen for a room visit again, go to step 1.
The one designee simply turns off the light 100 times. The only way the light is ever turned on is by a prisoner’s first visit to the room. If a prisoner arrives for multiple visits, he doesn’t touch the light. This ensures that only a unique, first-time visit causes the light to be lit. After the designee has turned off the light 100 times, he knows that there have been 100 unique visits.
The method proposed as ObiWan’s first, and also taken from the site, wouldn’t quite work as stated.
What do you do if you go in the room for the first time, and the light’s already on?
You have to keep at it until each prisoner has visited the room when the light was off and, the first time that happens, you turn it on.
So it would take even longer. Besides, for the designated guy to get in 99 times, when his odds are 1/100 of being picked each day…well, it’d be a long time.
I should have said, “The only way the light is turned on is if a prisoner has never turned it on before.” Obviously, many first-timers could arrive before the light was turned off, but their visits wouldn’t be “counted” by the light switch. If they arrive and the light is already on, they leave – it’s as though they were never there. If they arrive and the light is off, they turn it on – ONLY ONCE. After that, they don’t touch anything.
Nope, it would work exactly as it is in the OP. I had already included your suggestion. Note I said “The rest of the prisoners are instructed to leave the light alone unless it is their first time in the room when the light has been off.”
I agree that if it were phrased "“The rest of the prisoners are instructed to leave the light alone unless it is their first time in the room” it would fail.
Anyway, with Beeblebrox’s nitpick in place on Bricker’s solution I think we have got it.
OK Bricker, thanks for spelling it out (I was misinterpretting the original explanation).
So the designate would be counting either 1 persons’ previous entry to the room(the first prisoner in after the designate who is a first timer) or none(if everyone between his two visits were repeaters) each time he checked the light. I now see this would work for sure(eventually).
I don’t understand this objection:“Also, the solutions in the OP would work just as well for 4 or 60 or 2000 prisoners as for 100. Which makes me somewhat skeptical…”
Why should the problem be fundamentally different if there were 10 prisoners? As long as there are more prisoners than information choices it’s basically the same prob, is it not?
I coded this up in Matlab, and ran it 100 times. On average, it took 10,362 days (28.4 years) to be free. The minumum time was 8076 days, and the maximum was 13,422 days.
You turn on the light the first time you enter a dark room.
No one turns on the light more than once.
The counter always turns the light off.
No one else turns the light off, ever.
If you are the person chosen on the second day, you turn the light off, counting two, unless it was you who turned it on. You are the counter. When you turn off the light for the 100th time, you demand freedom.
There was an inelegant solution on the Wu site that I really like. My variant of it is:
The prisoners agree that the first one in the room smashes the light bulb and leaves 99 pieces. As each prisoner arrives for the first time, he takes a fragment. When a “newby” finds only one piece he can confidently declare their freedom!
Using the same assumption as Triskadecamus (that a prisoner is chosen every day and they can determine who’s first, second, etc.) you can attempt to reduce the time even further.
Using the same steps as Tris:
But instead of:
You wait for the third day. The prisoner on the first day does whatever he wants with the light and considers this his first visit. If the prisoner chosen on the second day is the same as the first (this is his second visit to the room) he turns the light off. If it is his first visit he turns the light on.
The prisoner chosen on the third day is the designated counter. If the light is on he counts three, if the light is off he counts two. Unless of course he was chosen on the first or second days and he would subtract his own previous visits from that count.
Using that method you can’t extend that to four days. Anybody else have an idea?
While posting my refinement on that site, I came up with a better refinement:
The first day there is a first time visitor, by definition. He can do whatever he likes, leave the light on or off, it is ignored the next day. The second day, if the visitor is not there on his first visit, he knows it, and he leaves the light off. The third day, if the visitor finds the light off, he knows the count is only two, including himself, if it is on, he knows the count is three, unless he, himself has visited before. In either case, he (the visitor on the third day) is now the counter. He turns the light off. Starting on the fourth day, the prisoners turn on the light once each at the first opportunity, (if they enter, and the light is on) and never again. The counter increments his count if the light is on, when he enters, and turns it off. The first three days are counted, unless the first three visits include repeats, which is unlikely.
You can extend Tris’s idea as follows: First visitor turns on light. After that, visitors leave the light on if it is their very first visit. The first time a visitor makes a second visit, he becomes the counter and switches the light off (he now knows how many prisoners have visited). For the rest of the opening 100 days, all visitors leave the light off. This gives the counter a head start of about 12 on average, which brings the expected release time down to about 9000 days.
(But all these ideas have been discussed on the forum Chronos linked to - the optimal solution appears to be ca. 3500 days)