100 Prisoners and a Lightbulb
Part 3 of the prisoner themed puzzles series, you can read this one independently of the others, but they can be found here (1) and here (2).
OK, once again with have 100 prisoners in a prison and each has their own cell. Somewhere in the prison there is a special room which has a solitary lightbulb hanging in it, which is initially off and a lightswitch which can be used to toggle the bulb.
Every day the warden picks one of the prisoners and takes them to the room where they can observe the current state of the bulb and then they can toggle it on or off if they want. Then they are marched back to their cell until they are next chosen. The warden doesn't have to pick each prisoner equally; in fact there are no restrictions for the prisoner selection by the warden each day.
At any point, any of the prisoners can make the statement: “all of the prisoners have visited the room at least once.” If someone correctly asserts the statement then everyone gets to go free, but if they are wrong then everyone is executed, so you only want to make the statement when you are certain. The only way the prisoners have to communicate with the other inmates is by turning the lightbulb on or off, however they are given an initial period of time before it begins to come up with a plan. What system can you come up with to communicate and is there one which can get you out before you die of old age?
The first day where you could possibly be correct is day 100, but that is unlikely to be true, because the warden would have had to pick each prisoner once and only once. Let's think about how we can use the bulb. If we divided time into 100 day blocks and try to come up with a way of announcing when you have had all the prisoners come in within that time.
If it is the first day of the block (so day 1, 101, 201 etc) then if it is off then turn it on. If it is already on then announce that everyone has been in the room and go free.
On any other day then don't do anything if it is your first time visiting within that block of time. On your second visit within the same block then we have failed on getting all 100 to visit within that block, so you announce it by turning off the light. On visit 3 or more just leave it.
The idea here is that at the start of each block, say day 701 we turn it on. If this stays on for as long as no one has been in twice, but turns off as soon as we have failed. If it remains on until day 801 then you have won.
However this takes a horrifically long time at 1.072*10^44 days on average. This is around 10^41 years. To put that in context, the universe is around 10^10 years old. So if each year of the universe was actually the length of the universe so far, and if each year of that was stretched to the length of the universe so far and finally if each day of that was stretched to the length of the universe so far, then you lived that 10 times you would have just under the average amount of time this method would take. I dislike using life expectancies from people in the past to put a limit on how long you generation, who will see the singularity, will live, but you will not live this long.
Not surprisingly we can do better. The following method is far better and it abuses the idea that not all prisoners have to have the same role:
99 prisoners follow the command to do nothing if they enter the room with the lightbulb on, but to toggle it on the first time (and only the first time, this is important) they enter the room with it off.
The remaining prisoner turns off the bulb every time they see it on, keeping a tally of how many times they have done so. When that counter reaches 99 then all of the other prisoners must have been in the room and so this prisoner can make the announcement and everyone can go free.
This is full proof, but it takes a long time. Most of the time as 1 of the 99 you will turn up to a bulb which is already on because on average it will take a long time until the tally-er returns to the room. In fact the expected time until the statement is made is 10417.74 days or about 28.54 years. Well this is completely acceptable compared with that horrific number from above and it might be that most of the prisoners will live to see the release day. Can we drop this any lower?
By having multiple people count smaller subsets and then having one lead counter count how many subordinate counters have finished we can dramatically reduce the total number of days. I'm going to give brief overview of an extension to this system. Imagine everyone has 1 “token” that they are trying to deposit by going into the unlit room and turning on the bulb. If you come into the room and find the room already lit then you can turn it off and “collect” someone else’s token.
Once 50 people have collected the tokens from 50 others then we have 50 with 2 tokens and 50 without. This completes stage 0. Exactly the same thing can now happen with giving tokens worth 2 and others collecting them, called stage 1. This continues with tokens of 4, then 8 etc.
This method of counting effectively assigns mid level counters dynamically, however to do this in practice requires quite a lot of messy logic. If you want to read a good paper which gives an example of this binary token system for four prisoners then click here and go to page 5.
The best answer for n prisoners appears to be a hybrid of several of these systems and putting it all together for 100 prisoners the lowest expected jail time we have found is 3890 days which is just a bit over a decade.
My advice if you are stuck in such a prison is wait for as long as you can bare then make a guess. By a few years in you are almost certain to be correct anyway. As always with these puzzles, there are always real life considerations that mean you can weasel out of a puzzle. But that is not the point; the setting is only as a means to attempt to convey the logic at the heart of a puzzle in a more understandable way.
