Prisoner puzzle.
Thursday morning flight back home from Maryland and New Jersey. Puzzle time!!!
Since last week I was pilloried for lowering my standards of puzzle (once again, I am amazed that people think I have standards), I picked a slightly harder one this week. I heard a variation of this in Car Talk last week as I was taking Tasha somewhere.
If you know this, you will get it immediately. If you had heard this before, it is fun trying to remember the answer. If you have never heard it before, it would be interesting to solve it. Let me know thru FB message if you would like some hints.
As always, do not write on comments section if you have figured it out. This is to give others a chance to solve it. Send me a FB message.
There is a slightly easier version and a slightly tougher version of this puzzle. The puzzle goes roughly like this.
There is a prison with 15 prisoners for life in individual cells with no ability to communicate with each other whatsoever. One day, the warden took all of them out and gave them a chance to go out free. However, there was a catch.
He showed them an isolated room from outside in a separate part of the jail and told them that there were two switches inside. One on the left and the other on the right. The switches were connected to absolutely nothing. They could only be flipped to the on or off position.
The warden, starting the next day, was randomly going to pick a prisoner – at random times (could be few a day or could be none some day) – and take him inside the room. While inside, the prisoner would have to flip any one switch once. (If it is on, he flips it off and vice versa). However, he had to flip one (and only one) switch. He could choose which one to flip, of course.
Slightly easier version: The warden told them that both the switches were initially in off position.
Slightly more difficult version: The warden told them that nobody – including himself – knew what the starting positions of the switches were.
And then the warden said – “I need somebody among you – I don’t care who – some day – I don’t care when – to come and tell me that you are confident that all the prisoners have visited the room at least once. If that person is right, all of you go scott free. If not, all of you will be put to death.”
He gave them sometime to get together that day to devise a strategy to see if they could come up with a foolproof plan to get out.
Can you suggest a strategy (for both the easier and more difficult case)?
Remember, they don’t need to tell immediately after all of them have visited once. They just need to be absolutely sure that each one of them has visited the room at least once.
An aside – am impressed by how well the Car-Talk producers are editing and splicing the best episodes from the past together to create the re-runs we listen to these days….only wonder if either Click or Clack is still involved in providing the voice-over for the sponsor names..
Yep. Do you listen to Wait Wait don’t tell me?
but of course, yes Rajib. slightly trickier though with the need to censor some things from my 11-year old 🙂
How about Says You?
Says You? hmmm, never heard of that. Guess our local NPR affiliate, WBUR, does not broadcast Says You. Need to find the podcast to this one
You can buy old podcasts. Awesome radio show on English words and phrases..
The answer to the puzzle is very elegant. But it might be easier to comprehend if I build up to the final solution. I am going to build up to the solution in three consecutive Comments entires.
FIRST A MUCH SIMPLER VERSION OF THE PROBLEM:
Everything remains the same except (1) there is only one switch starting with OFF position and (2) the prisoners can choose to either flip the switch or not (meaning they can just come out doing nothing or flipping the switch exactly once). Well, first they elect one of them as their captain (I will call that person C). Now C has to find out thru that switch when all of them have gone in at least once. So, this is what he will do. He will ask the others that whenever any of them are brought into the room, if the switch is OFF, they should flip the switch ON. But if they have ever done this before (meaning switched it ON once before), then they should just come out. If the switch is already ON, just do nothing and come out. Therefore, every prisoner will switch the switch ON only once in their life. The captain C himself, when taken into the room will flip the switch OFF if it is ON. If it already OFF, he will just come out.
So what happens when C is taken in for the first time and he finds the switch OFF? It means nobody has come in before him. What if he finds it to be ON? It means at least one prisoner has gone in before him and switched it ON. (After that and before he came in, all other prisoners taken in including multiple visits by the original one would leave the switch ON). Let’s say the prisoner who did that was P. Now C switches it OFF.
Next time C is taken in (whenever that is), if he finds it still OFF, it means either nobody has been taken in after his previous visit or only P has gone in (maybe even multiple times). Since P has done the flipping to ON once before, he is not going to touch it any more.
What if C finds that the switch is actually ON? Well, that means, certainly somebody other than P – let’s say Q – has gone in in between C’s two visits and has switched it ON. It could be that others have gone after Q or even P has gone – or any of them including Q has gone multiple times before C came in the second time, but that is immaterial. (remember, once the switch is ON, everybody simply comes out). Now C switches it OFF.
You see how the logic goes now? Everytime C switches it OFF, he knows for sure that another distinct person has entered the room after his last visit. And therefore when he switches it off the 14th time, he can declare with full surety that all prisoners have gone in at least once. (He being the 15th person, has obviously gone in)
Now, let’s ratchet it up a little.
SECOND VERSION OF THE PROBLEM:
Everything remains from the FIRST VERSION, except this time (1) there are two switches – both are off and (2) every prisoner has to flip one switch at least. This, if you recollect was the easier version in the original problem I had posted.
Well, the solution is essentially the same as the FIRST VERSION. Let’s keep the left switch as the one that C explained the rules to the prisoners like before (we will call that the scorekeeping switch – equivalent of the single switch we had before). But if the prisoner in the previous version would have done nothing, in this case he would just flip the right switch – let’s call it the useless switch. The state of the useless switch is completely immaterial. It is there just so that the prisoner can respect the rule “you have to flip some switch” if by the rules of C given above, he does not have to flip the scorekeeping watch.
And that is it!
So, C tells everybody – “when you are taken in, if you find the scorekeeping switch OFF, flip it to ON. But do this only once. If you ever have done this before, do not do it ever again. Instead simply flip the useless switch. And if the scorekeeping switch is already ON, again, do not touch it – just flip the useless switch”.
And C just flips the scorekeeping switch to OFF every time he finds it ON; else, he flips the useless switch. After 14 switching OFF of the scorekeeping switch, he will declare that all 15 have been to the room at least once!!
Now for the hardest version.
THIRD VERSION OF THE PROBLEM:
Everything remains the same as the SECOND VERSION except nobody knows the initial state of the switches.
Let’s think about it step by step. Again, we do not care about the state of the useless switch. Let’s focus on the scorekeeping watch.
What if C gave the same instructions as before?
If initially the switch was OFF, everything works like before. Possible answer could be “after 14th switch”, C declares he is sure.
Will this work when the switch was ON to begin with?
If the switch was ON to begin with, all prisoners other than C would have left it untouched. First time C came in, he could switch it off. So the “after 14th switch” of above will not work. Actually he could be off by one. (and that would be if he was the first guy brought in and found the switch ON and there was one guy that was never brought in). Okay, so C switched it OFF first time he came in. But he does not know whether somebody came before him since he does not know what the initial state was. After this though, if he does it for 14 more times, he will be sure. So is the answer that after the 15th flip, he can declare that he is sure?
While it is true that after the 15th flip he is indeed sure – assuming the beginning position was ON, he cannot rely on that strategy. The reason – and this is tricky – is that if that was the strategy he was going to follow, and the initial state was OFF, there will never be a 15th flip!! They will be in prison for ever. It would work if the initial state was ON but they are doomed to be in prison for ever if the initial position was OFF!
So you extend your thought process a little more. Since C was never sure the first time that he flipped it OFF – was it from an initial position ON or some prisoner had switched it ON, you ask the prisoners to do the flipping by the above rules as before. But instead of stopping after one flips (and by stopping I mean fiddle with the useless switch), ask them to stop after two flips.
So what that means is a prisoner when brought in will look at the scorekeeping switch. If it is ON, he will leave it alone and flip the useless switch. If it is OFF, he will switch it ON. But he will never go beyond switching the scorekeeping watch ON more than TWICE. If he has done it for the second time, he simply starts flipping the useless switch.
C, on his part, keeps switching the scorekeeping switch OFF when he find it ON and if already OFF, flips the useless switch.
What happens after the 28th flip that C has done? Remember, no prisoner can ever go over 2 flips.
If the original setting was OFF, that means each prisoner has flipped the switch exactly twice. C is absolutely sure that he can declare success.
What if the original setting was ON? Well C did the first flip OFF. The other 27 were done by the prisoners. Since nobody can go over 2, it means thirteen have done it twice and one of them have done it once. C is still sure of success.
Would 27 have worked? Nope. As you see, if the original setting was OFF, 27 would work. But if the original setting was ON, it could be that C did the first one and thirteen others did it twice and there was one prisoner who was never brought in ever.
Thus C waits for the 28th flip and then declares success.
Whew! That took me almost an hour of thinking how to construct the logic!!
This is so much simpler than my solution. But mine did not require a gatekeeper – every prisoner after a while knew if all others were already in the room.
Marek – would love to know your solution. every iteration I could come up with had a coordinator or gatekeeper.
Here it goes: The idea is for each prisoner to switch the left switch only after certain number of times he/she entered the room. Prisoner #1 does it on first entry every 16 entries, prisoner #2 on second and so on. On other entries they switch the right switch. Each prisoner records left switch state only. He also draws a tree of possibilities on how the sequence he saw could have been created knowing when each prisoner can switch the left switch. When there the tree shows that the only way the sequence could have been created is only when everybody has at least bean once, the person who discovers that screams Eureka and gets everybody out of jail. The number of combinations will be pretty large but they have nothing else to do anyway. And they do not really have to check every combination, they just need to make sure that combinations that exclude one or more prisoners are not possible. And I also realized that by recording both switches we can make the time shorter. I also suspect that there is a way to speed this up by assigning a more complicated sequence to each prisoner – for example 0110010010 or something like that, but I have not tested this assumption.