3
$\begingroup$

100 Prisoners' Names in Boxes

The following puzzle is a variation of the above puzzle.

Names in Boxes

  • The names of 4 prisoners are placed in 4 wooden boxes , one name to a box, and the boxes are lined up on a table in a room. The boxes are numbered 1,2,3 and 4.
  • The names are randomly placed. Therefore, box 1 is equally likely to contain the name of any of the 4 prisoners. Same is the case for the other boxes.
  • One by one, the prisoners are led into the room; each may look in at most 2 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
  • Each prisoner, before entering the room, needs to call out which 2 boxes they will open. They can then open only these 2 boxes.
  • 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.
  • What strategy can they use to maximize their survival ?
$\endgroup$
5
  • $\begingroup$ Can you clarify the second to last point for me? Say prisoner 1 doesn't find his/her name after opening the two boxes - are they immediately executed at that time or do the other three still go and look? $\endgroup$ Nov 5 '20 at 22:06
  • 1
    $\begingroup$ @PartyHatPanda , I don't think that it would matter if they are immediately executed or executed after everybody has had their turn. But, anyhow, let us assume that they are all executed after all of them have had gone in and looked. $\endgroup$ Nov 5 '20 at 22:23
  • $\begingroup$ Please don't add a new question to your post after someone answers it. Instead, ask a new question and then link to this one as an explanation. $\endgroup$
    – bobble
    Nov 8 '20 at 4:06
  • $\begingroup$ @bobble , what if the only person who has answered the question is ready to include the answer to the second question in his answer ? The second question is is what if there are 100 people who can each open 2 boxes . I wish to keep all the question answers at one place for future readers . This is also because the second question is just a small extension of the first question. $\endgroup$ Nov 9 '20 at 18:44
  • 2
    $\begingroup$ It is Puzzling.SE's policy that questions should not be majorly changed after they are answered. It is also our policy that there shouldn't be multiple questions in the same post. Adding a new question after a good answer has already been given violates both of these policies. It doesn't matter that the question is related. You can, again, simply ask a new question. $\endgroup$
    – bobble
    Nov 9 '20 at 18:55
4
$\begingroup$

I think the answer is

The first two prisoners choose the first two boxes, and the last two prisoners choose the last two boxes. The chance of survival is $1/6 \approx 16.7\%$.

Reasoning:

Let's imagine a graph of four nodes and four edges, where each node represents a box and each edge connects the two boxes chosen by a prisoner. Then there will be four nodes and four edges, and an edge cannot be a self-loop.

Given such a graph, observe that a cycle of any size in the graph will permit two possibilities. E.g. if three prisoners A, B, C choose boxes 1-2, 2-3, 3-1 respectively, there are two cases where all three will find their own names: ABC and CAB.

Also, if such a cycle has any branches, they do not increase the overall cases of survival: in addition to the last example, if D chooses 1-4, D is essentially giving up the chance to see their name in box 1 (since one of ABC will never find their name otherwise).

Moreover, if a connected component has more edges than nodes (e.g. D chooses 1-2 instead), the chance of survival drops to zero, since they don't have enough distinct boxes to find all their names.

Therefore, in order to maximize the chance of survival, the prisoners need to maximize the number of disjoint cycles in the graph, which gives two cycles of two nodes each. Then they will survive in four cases out of $4!=24$ total cases, giving $1/6$ chance of survival.

$\endgroup$
6
  • $\begingroup$ What do you mean by a cycle here ? I can't see how there can be any cycle since the nodes (boxes ) don't have edges connecting each other nor do the prisoners have edges going from one prisoner to the other. $\endgroup$ Nov 6 '20 at 0:58
  • 1
    $\begingroup$ @HemantAgarwal A box is a node, and a prisoner is an edge between two boxes. $\endgroup$
    – Bubbler
    Nov 6 '20 at 1:04
  • $\begingroup$ I am trying to understand your method although I am not able to do so completely. I will get back to you after studying it further. Meanwhile, can you consider posting one more answer using permutations and combinations but without using the concept of cycles, edges, nodes, etc ? $\endgroup$ Nov 6 '20 at 1:18
  • $\begingroup$ @HemantAgarwal I've got some solution that way, but it doesn't sound very elegant (compared to this one, IMO). Hopefully someone else will post it. $\endgroup$
    – Bubbler
    Nov 6 '20 at 1:49
  • $\begingroup$ can your method above be used for a larger number of prisoners? Say, 100 prisoners who can each open 50 boxes . $\endgroup$ Nov 8 '20 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.