First of all, let me say that this puzzle is hard. It took me a long time to solve it. After I did, I ran into several other versions. I am posting the original puzzle (as I know it) here, and below it, two easier versions of the same puzzle. If you are reasonably good at puzzles, try the harder version. If not, try one of the easier versions (they are still hard). In any case, you might want to give yourself a few days for this one.
The Prison Clock Puzzle
In a country that simply mocks the
Geneva Convention (
whose name we shall not mention), there is a
prison. In this prison, there are a hundred prisoners on death row. The
warden has a
penchant for
puzzles,
riddles and
brain teasers, and decides to give one to the prisoners. He calls the 100 prisoners on death row and explains the puzzle to them:
There is a room in the prison in which there is a clock (a regular 12-hour wall clock with an hour hand and a minute hand). The clock has stopped, and will never move again of its own accord. Whenever the warden chooses, a prisoner will be taken to the room and will have to move the clock exactly 3 hours forwards or backwards (the choice is up to the prisoner). The prisoners will have no means of communicating with each other (other than by moving the clock). Whenever any prisoner wants, he can go the warden and tell him: "All the prisoners have been in the room." If he is correct, they will all be let go. If he is not, they will all be shot at a public execution and there will a party afterwards which they will not attend.
The order that they will be taken into the room will be at the warden's discretion. The only thing promised is they will all be taken to the room infinitely many times. That is, for each prisoner, given an integer N, there will be a time that the prisoner will have been in the room N times. (If you dislike sentences that are mathematically oriented and you are not sure exactly what that means, then work within the following assumption: within their lifetime, each prisoner will have been in the room a gazillion times, but at any given time you cannot assume that the prisoner has been in the room even once).
The prisoners will have one hour to confer, after which they will be separated. Then they willl be taken in turns to the room. They may not communicate with each other until one of them tells the warden that they have all been in the room.
What strategy should the prisoners choose to ensure they are all released?
Answers to the questions you have, but really shouldn't
- No, they cannot write on the wall of the room, or scratch a mark on the clock, or use any other method of conveying information. They do not eat together or have any social contact. There is very sophisticated surveillance equipment in the prison, and if one of them is caught trying to cheat, he will be sent into the sex offenders' ward wearing a girl scout uniform.
- No, they don't know when the clock stopped. Nor do they know which prisoner will enter the room first. Nor does a prisoner that enters the room
know if he is first.
- No.
- Yes, one prisoner can go 10 times in a row, and it may be 5000 times before prisoner number 1776439 goes. The order is "random" (What is truly random?). But, as I said, they are all assured of being in the room as many times as you want.
Below are some easier versions of this puzzle, in case it's too hard for you.
Don't read below unless you have given up
P.S. The problem with writing nodes like this is that I want to be
fair to everyone. Not everyone can solve every puzzle, and sometimes if this puzzle really
is too hard, you might want an easier version, instead of just giving up. So I decided to add two easier versions of this puzzle. However, we have a saying in
my country that goes "
An opening calls the thief." Basically, even if you COULD solve the original puzzle, you might be tempted to look at the easier version after a short while of trying. Now this is a
really difficult puzzle, so after about half an hour, you will probably be
tempted to look at an easier version. Or even at
the solution. DON'T. It will not be fun and you will never know whether you could have solved it. I think that 2 days is a reasonable amount of time to give up after.
Seriously. This puzzle is very tough for most people. If you give up in less than an hour, you are not being fair on yourself, as very few people can solve this puzzle in less than an hour. That said,
An easier version of this puzzle
Instead of a clock, there is a
lighbulb. There is an on/off switch. The prisoners can choose whether to flip the switch or not (i.e. they can switch it on or off or leave it as it is). Nothing else changes.
So - to recap - 100 prisoners, no communication. 1 lightbulb in a room. They don't know if it's on or off at the start, and all they can do is switch it on or off, if they so wish. When one of them tells the warden they have all been in the room there is a farewell party.
(Some space left here intentionally so that your eyes don't "drift" to the easiest puzzle.)
The easiest version of this puzzle
The prisoners are told that the lightbulb is off before any of them go into the room. Nothing else changes.
Solution
This is obviously going to be in small print, so that you will have a chance to change your mind before you actually read it (if you havn't solved it) and so that you won't accidentally "glimpse" part of a solution when "looking over" the solution "without actually reading it". Some people (not you, of course), might do it in order to try to get some
subconscious hint, when they are feeling stumped, but we both know that's bullshit, so I will not allow it. Anyway, the solution is below.
The bulk of the puzzle is the easiest puzzle. The other two just have some more information to confuse you and make the puzzle a bit more difficult. If you solved the original puzzle, you will probably have reduced it to the third puzzle anyway.
Solution to easiest version:
The prisoners choose a tallier (henceforth to be known as "Electric Boogaloo"). Whenever Electric Boogaloo enters the room, he switches on the lighbulb (unless it is already on). He is the only one that switches the lightbulb on. So the first time he enters the room, it will be off and he will switch it on. All the other prisoners switch the lighbulb off exactly once. So, if a non-Electric Boogaloo prisoner enters the room and the lightbulb is off, he doesn't touch it. If it is on, and this is the first time he sees it on, he turns it off, and if he already switched it off sometime before, he leaves it on.
Electric Boogaloo keeps a tally of how many times the lightbulb has been switched off. As each prisoner switches it off exactly once, this, unsurprisingly, is also a tally of how many prisoners have been in the room. Whenever he enters the room and it is off, he adds 1 to the tally and switches in back on.
When the lightbulb has been switched off 99 times, it means that all the prisoners have been in the room. So, the 99th time that Electric boogaloo goes into the room and sees the light switched off, he can go to the warden and tell him they have all been in the room.
Solution to easier version:
Obviously the problem here is how the first non-EB prisoner knows if the lightbulb is on because he entered before EB or if EB switched it on. We don't try to solve this. Instead, we continue with our original strategy, only this time, every prisoner switches the lighbulb off twice. Then, when EB sees that the bulb has been switched off 197 times, then he is guaranteed that all prisoners have switched it off al least once. 98 prisoners switched it off twice after EB switched it on, and one prisoner switched it off once after EB. Therefore, all the prisoners have been in the room. It is possible that one prisoner switched off the lightbulb before EB was in the room, but then EB will have spotted his second time, which is enough.
Solution to the original puzzle:
All we have to do to solve this problem is notice that the clock can only reliably be in two states (not four). This is because the prisoners MUST move the clock. First, let's assume the clock stopped on 12. Then, 12 o'clock or 3 o'clock is one state (say "off") and 6 o'clock and 9 o'clock is the other ("on"). For any given clock position, it is possible to stay in the same state or change state. Thus, if the clock is at 12 ("off"), and the prisoner wants to change the state, he moves it back 3 hours (to "on"). If he wants the clock to stay in the same position, he moves it forward 3 hours. Of course, it doesn't matter at what time the clock actually stopped (it doesn't have to be 12, 3, 6 or 9). Anything between 12:00 and 5:59 is "off" and and everyting betweem 6:00 and 11:59 is "on". Then the solution is just like for the easier puzzle.