This puzzle is based on 100 Prisoners' Names in Boxes:
Names in Boxes
- The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room.
- One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
- The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed.
The night before this game is going to be played also happens to be the Princess's birthday. During her birthday dinner with her father, the King, they have the following conversation:
King: Happy Birthday Princess! I'm going to give you $1000 to spend on whatever you want this year!
Princess: But I don't want money, Daddy! I don't want you to execute the prisoners!
K: Now now honey, you know I can't do that! Besides, their leader, Robin Hood, has already boasted that he has come up with a 30.68% of survival strategy, though I haven't personally figured out what it is yet...
P (silently, to herself): Really? I've already figured out that strategy.
P: Why not? They don't deserve to die!
K: Okay, I won't just free them all, but I'll give you a chance to save them. I'll let you spend birthday money on helping the prisoners out...
You, dear reader, are the Princess. You have a budget of $1000. You do not know any of the prisoners names or the order they might go in, except for Robin Hood. Here is what you may buy:
- \$500: Send a message to the prisoners. This message can be as long as you want, within reason.
- \$500: Allow the prisoners to send a message to you. The prisoners know you and trust you, and they know you can influence the outcome, but they do not know what you are able to do to influence the game specifically. Messages may be sent in either order, but must occur before any of the other game actions. This message can also be as long as they want (within reason).
- Update: It is reasonable / by design to assume that they would tell you their numbering scheme for the straightforward solution.
- Update: It is by design that two way communication is "possible" but consumes all your money, and therefore almost certainly not worth it.
- \$0: Receive a complete list of all the Prisoner's names (this is here so that you would have the list NOW, but not during the messaging phase).
- \$10: After any messages have been sent, you may open one box and read the name. Update: You may do this more than once.
- \$100: You may swap the names in any two boxes.
- \$100: You may choose that their leader, Robin Hood, go first (otherwise, it is random).
- \$300: You may name another prisoner that is not Robin Hood to go first (again, otherwise it is random).
- \$100: Completely randomize the boxes.
When a Prisoner enters the room, his name will be announced to you before he opens any boxes. You will be able to read the name on the paper when the prisoner does.
- \$10: During the game, you may allow any prisoner to open one extra box. Update: You may buy this multiple times (this was originally intended, but I didn't realize it wasn't clear).
- \$500: After a prisoner has opened a box, you may swap it with any other box to provide a different result. You must do this immediately upon the prisoner reading the name in the box.
- Update: I have raised the price of this to a value that doesn't invalidate existing answers "correctness" but does increase the worst-case-scenario cost of pursuing that particular strategy, in an attempt to make it worthwhile to possible pursue less expensive strategies.
Other facts: You, as the Princess, place infinite value on the prisoner's lives. It is of more value to spend all your money to get even just a marginally higher chance of prisoner survival. You suspect, correctly, that the prisoners would not number themselves in a way that is immediately straightforward so that the game could not be rigged against them by the King, but they are willing to tell YOU that numbering scheme in their private message.
Update: Yes, you can assume during game play you may take notes / have a perfect memory. You're a perfect logician (as are the prisoners), isn't everyone in these sorts of puzzles?
- Can you get all the prisoners to survive? What is the probability of survival?
- If it is 100%, what is the most amount of money you can save?
- If it is not 100%, what is the most amount of money you can save while still having a maximum survival probability?
Note: in this question the user talks about introducing a friend but these rules are more interesting and complicated.