100 Prisoners' Names in Boxes - Save them all!

Question

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:

Message Phase:

• \$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.

Preparation Phase:

• \$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.

Game Phase

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.}

Answer 1

Assumption 1:

Due to Robin's boast, the prisoners will follow the strategy outlined in Gilles' solution to the original 100 names question. Basic strategy is each prisoner name is assigned a secret number and the prisoner opens the corresponding box, if the prisoner doesn't find their name, they then move on to the box of the name they did find. All prisoners are saved if there are no cycles of length 51 or more.

Assumption 2:

You can use the $10 game phase action multiple times for the same prisoner.

Assumption 3:

You can write down what is happening, or have an infallible memory.

Strategy:

When a prisoner comes along who doesn't find their name in the first 50 boxes (there is a cycle of 51 or more), keep paying \$10 until they do. When they do eventually find their name, use the \$400 \$500 dollar option to swap two boxes and break this cycle into two cycles no more than 50 in length. This should be possible by swapping the 50th box of the next prisoner on this cycle, with the one containing their name, upon it's opening. You know where this box is as you have witnessed the entire cycle previously.

Results:

100% of the time, it works everytime!

Costs:

Between \$0 (%30.68 of the time) and \$900 \$1000 (Cycle of length 100)

Notes on pre-game:

I am fairly sure that without the numbering system all the preparation phase options are useless, thus there is a minimum outlay of \$500 to get the numbering system pre-game.. as you can no longer message the prisoners without using all your money, you'll need to swap at least one box (\$100), but you don't know where the names are, and you can only look in 40 boxes (\$400) with your remaining money.. which isn't enough to achieve 100% save-all rate.

Notes on during game:

By following my strategy, the in-game \$10 option actually buys you three things; what name is in the box, how the numbering system works for this node and the option for the prisoner to check one more box. You also get two of these for free during the first 50 boxes, information you don't have previously, and worth at least \$500 pre-game (\$10 each even without the numbering system). This out-weighs the \$400 surcharge for swapping boxes in-game as opposed to pre-game.

Answer 2

We can

Save all the prisoners

For an expected cost (rounded to the cent) of

$\texttt{\$}500+100\sum_{c=51}^{100}{\frac1{c}}=\texttt{\$}568.82$

By

Messaging (for $\texttt{\$}500$) Robin Hood to tell him to go ahead with his strategy he expects to have a $30.68\%$ success rate
(we may as well also lay that out for him too, just in case).
But that he should number alphabetically (we could go by name without first letter to obfuscate).

and then swapping (for $\texttt{\$}100$) two "opposite" names from the (only) cycle of length $\gt50$ if one exists (with probability $\sum_{c=51}^{100}{\frac1{c}}$)
- by opposite I mean if we have a single cycle of length $n\gt50$ pick a name and traverse the cycle by $\lfloor\frac{n}2\rfloor$ steps and swap it with that name making two cycles of $\lfloor\frac{n}2\rfloor$ and $n-\lfloor\frac{n}2\rfloor$ instead.

Answer 3

Incorrect, missed a key rule as part of the Names in Boxes

Going off the same Assumption 1 as Arth, but for Assumption 2:

You cannot use the $10 game phase action multiple times for the same prisoner.

Strategy:

When a prisoner comes along who doesn't find their name in the first 50 boxes (there is a cycle of 51 or more), they get one extra attempt to find their name in the 51st box. Then use the $400 dollar option to swap two names to break the cycle. Swapping the first box with the 51st box should remove the cycle correctly.

Results:

99-100% Saved

Costs:

Either \$0 (30.68% of the time with 100% Saved) or $410 (2% for 100% Saved if name is in the 51st box, otherwise 99% Saved)

Notes:

Hope I did this right, first time answering here.

Answer 4

1000 dollars with 100 percent chance:

The princess spends 500 dollars to allow the first prisoner to read every name ( even if he finds his own first ). The princess records the names, and spends the other 500 on sending the order of the boxes to the prisoners.

Answer 5

Assumption

the princess is in the room with the prisoner - the prisoner is announced to her, and she sees the names as the prisoner looks at them.

Assumption

as the actions taken during game phase require the princess to let someone know during game the princess can speak, as long as what she says is not obviously a game-breaking hint

Assumption

the prisoners suddenly altering their behavior after even the most innocuous of phrases will lead the king to assume it is obviously a game-breaking hint.

Assumption

as the setup is message phase, the preparation phase, and then game phase in that order, and messenger phase is mentioned to not reoccur once it is past, I assume that once the first prisoner is lead into the room no further 'preparations phase' actions will be allowed in the time between prisoners.

Strategy

Start with sending a message. The message will outline the princess' assumption of the numbering system that can be used to get the 30.68% survival strategy. Each prisoner should continue opening boxes up to their limit of 50 even after they've found their own name. They should still use the numbering system - but if they know their box is odd, they add one to any even number and vice versa until their number is found (obviously avoiding boxes they already checked), then proceed to check the rest of the boxes normally. The princess will signal even or odd (precise passcode below) if she knows where the name is in the boxes - and several possible signals will be discussed in the message, depending on what the princess is allowed to do or say during game phase.

During game phase

If the princess can, at the beginning of game phase, tell each prisoner she can purchase extra boxes if they need them - if she uses their name, she knows which box their name is in, and if she says (for example) she can purchase "a few" extra boxes, their box is even; if she uses "some" the box is odd. Alternatively, she may smile if they should check even or nod if the box is odd (and neither if she doesn't know), if she is not permitted to speak. Or, every time they make eye contact with her, she blinks quickly twice for even, thrice for odd (and a slow blink if she doesn't know). If they aren't in a position for eye contact, maybe squeezing her hand against an armrest or rail, or tapping a finger in the same two-or-three pattern will suffice. The important thing is that these tells were announced in the message (If I'm the one who tells you, look for code words, if the guard is the one who says it, look for nod-or-smile or a blink pattern), and she sticks to it. There should also be a tell for breaking a pattern (maybe cough to add one to the next number? or pinch the bridge of her nose, or rub her eyes?) in case the princess doesn't know their box, but does know they've started a pattern that doesn't lead to it in time.

Results

every prisoner can be saved - At worst, 50 boxes will be known by the end of the first prisoner's turn, and the princess can buy up to 50 extra boxes, which means she can know all of them. Once she knows which box each name is in, she can signal even or odd and they will find their box without needing extra turns.

Costs

Best case, 500 for the message alone. Worst case, the full 1000 is spent. If the first prisoner happens to have their name be in the last box (that is, the hundredth they check) - all 500 is spent, but every box is known and can be signaled afterwards for no further costs. After that, every prisoner saves a minimum of 10$, because at minimum one more box is discovered.

Notes

Since the prisoners are all following the same basic pattern (pick a box "at random" based on their number, then picking subsequent boxes based on the contents) it is not likely to be obvious that the princess is signaling anything. Since it still takes a variable amount of time, and can go all the way up to the fiftieth box or more depending on chance (and if she knows) - it is likely the king will assume good luck, or that the prisoners are somehow communicating, rather than the princess signalling. The message should preferably include this reasoning, since it helps avoid clumsiness.

Extra Note

if preparation phase does reoccur between prisoners, it might be wiser to buy extra boxes between prisoners, to help avoid the situation where the princess does not know the prisoner's box number, but the prisoner is on a pattern that doesn't lead to it. The princess might, for example, pick either even or odd boxes (based on which one she knows more of) so even if she doesn't know all the boxes, she can offer a guess based on what's left.