| Prisoners' Dilemma |
[Jul. 7th, 2008|11:25 pm] |
OK, so I keep seeing other people post intriguing puzzles, and there's at least one I have that I guess most people who'll read this haven't seen. I know there is a solution.
So, there's a bunch of prisoners (a few hundred), each with a unique name1. They have a sadistic warden who is in charge of feeding them. The warden is somewhat lazy and wishes to cut costs, so he challenges the prisoners to a puzzle before they can be fed.
For each of the 3 alotted mealtimes, he will put each prisoner's name into a box, then shuffle the boxes, placing them at random along the back wall of the mess hall. The prisoners will then individually and randomly be called into the hall and allowed to nominate a box for the warden to open and read the contents. Each prisoner may continue to nominate boxes until either the warden reads his name or he has nominated half or more of the boxes. He will then be led out into the yard, with no contact with the yet-to-enter prisoners. The warden closes all of the boxes and calls in the next prisoner - every prisoner is presented with the exact same box arrangement.
Clearly if the prisoner touches the boxes in any way, leaves any notes behind, or attempts any form of communication whatsoever with his yet-to-enter comrades after he's entered the hall, the warden will have them shot.
Only if every prisoner finds his or her name will any of them be given meal tickets. If any one prisoner fails to find their own name, no prisoner will get a ticket. On the plus side, the warden is offering to give two tickets each if they do succeed. The prisoners are a hardy bunch and only need to eat once every few days on average to survive. Meal tickets can be hoarded and redeemed at any time, and the prisoners generally have a few spares lying around as they're used for trade.
The prisoners' job is to either come up with a strategy (the warden promises not to listen to their plans, but of course can try to predict them) which can keep them alive, or demonstrate to the prison authorities that the warden is a sadistic bastard - in which case they'll be able to get a new warden (who'll probably give them another sadistic game next week).
Obviously if you know the answer offhand, don't post it immediately. Some people may want to think about it. :)
1 Also, they can't change their names. Thankyou, Sticky.
Misunderstandings that've resulted in edits: Prisoners need to win as a group, not just individually. Meal tickets are completely transferrable and the prisoners need only ensure that the tickets stay afloat on average. Boxes are not removed from the mess hall even if a prisoner finds his name. |
|
|
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
bucko909's journal