So today at lunch, my co-worker gave me this puzzle to solve:
In some prison, there are 10 prisoners and a prison guard. The prison guard plans to randomly choose prisoners and take them one by one into a special room that has two switches. Either switch can be on or off and no one knows the starting state of each switch ahead of time. Upon entering the room, the prisoner must throw one (and exactly one switch). He cannot simply do nothing and then leave the room.
Once all 10 prisoners have entered the special room, the prison guard will let them go free, but there is a catch. One of the prisoners needs to declare when all prisoners have entered the special room at least one time. If his declaration is correct, they all go free. If not, they all die. Remember that the guard is bringing prisoners into the special room completely at random, and there is nothing to stop him from bring the same person into the room multiple times.
Now, before the big event, the prison guard is going to allow the prisoners to meet together and try to come up with a strategy to figure out how to determine how they'll know when all 10 prisoners have entered the special room at least once.
So what's the strategy?
Now I just heard this problem, and I've only put minimal thought into it so far. I will post back with the "official" answer in a few days, but before I do, I thought it would be amusing to entertain some of my quick responses, all of which (based on the problem as it was given to me) are completely valid:
My first solution:
Each prisoner who enters the room takes off one shoe and leaves it behind (while also throwing one switch as per the rules). When a prisoner enters the room and sees 9 shoes, he'll know he is the 10th prisoner.
My co-worker then replied that the prisoners don't have any shoes, or any clothes of any kind; they're completely naked.
My second solution:
Each prisoner who enters the room spits a giant loogie onto the ground (while also throwing one switch as per the rules). When a prisoner enters the room and sees 9 loogies on the ground, he'll know he is the 10th prisoner.
My co-worker then replied that the loogies will dry up and you won't be able to see them because the guard will wait a very long time between bringing each prisoner into the room.
My third solution:
Each prisoner who enters the room will leave a giant poo on the ground (while also throwing one switch as per the rules), and when a prisoner enters the room and sees 9 piles of poo, he'll know he is the 10th visitor.
At this point, we were all laughing too hard to have any further intelligent discussion on the matter.
But I do plan to think about this and report back with a "real" solution. I have a few ideas already, but I don't have sufficient time to get them into words.
If you'd like to post an answer, you're welcome to do so.
2 Responses
My solution: Eat lunch alone.
Ok, well my co-worker finally gave me the answer to this, but let me tell you… it's so complicated and convoluted and would be ridiculously difficult to explain, that I'm not even going to bother. Sorry.
Guess we'll just have to let the prisoners die.