4
$\begingroup$

You are in a group of sixty prisoners, and the warden has a game to play with you.

In a room there are sixty boxes. Each box can contain either two apples, two oranges or one of each, but you don't know which contains how many. When the game starts, each prisoner can go in the room and pick one fruit each from two of the boxes (including labelled ones). Then he is allowed to put '2 Apples', '2 Oranges' or 'Apple & Orange' labels on one or two of them (if they are unlabeled). EDITED: He is also allowed to change the labels of up to two boxes he didn’t look in. When all 60 prisoners have visited the room and there is at least one unlabeled box, the process starts again from the first prisoner.

After that, they will be put in a soundproof room, with there is no communication, one for every prisoner. When all the boxes are labeled, the prisoners are freed if they are all placed correctly, or exceuted otherwise.

You can simply have every box checked, then label each one with the fruit you get, but you only have a $(\frac{2}{3})^{60} = 2.7197216 \times 10^{-11}$ chance of getting freed.

What is the optimal plan to maximise the chances of the prisoners being freed?

$\endgroup$
15
  • 1
    $\begingroup$ When you pick one fruit from each box, is there a "first fruit" and a "second fruit"? Or is it possible that, even if everyone looks in a particular box, one of the fruits never gets picked? $\endgroup$
    – Deusovi
    Oct 15, 2022 at 17:15
  • 1
    $\begingroup$ @Deusovi Even if everyone looks in a particular box, it's possible that one of the fruits never gets picked. $\endgroup$ Oct 15, 2022 at 17:23
  • 2
    $\begingroup$ Interesting puzzle! Seems like it's taking inspiration from the usual mislabeled boxes puzzle, but with an interesting twist. Looking forward to puzzlers solving this puzzle :D $\endgroup$
    – justhalf
    Oct 15, 2022 at 17:25
  • 2
    $\begingroup$ Why did you change from 2/3 to 1/2? Isn't it really 2/3? If you pull out an apple, it's more likely that the box contain two apples than one apple+one orange. $\endgroup$
    – justhalf
    Oct 15, 2022 at 17:32
  • 2
    $\begingroup$ Hm... do you know if this has a "clean" answer? I feel like it would be very hard to prove optimality here. $\endgroup$
    – Deusovi
    Oct 15, 2022 at 17:44

2 Answers 2

7
$\begingroup$

As I understand the problem, the answer is:

There is no strategy to maximize the probability of freedom.

Because

You can never be sure someone saw both fruits of a given box. So there will always remain some uncertainty for some boxes.
If nothing is reset between rounds, you can always add a round by not labelling uncertain boxes, to learn more and reduce the probability to miss a fruit and mislabel a box.
But that means that to maximize the probability to be free the prisoners have to play forever.
To actually be free the prisoners must compromize between the risk of death and the time to conclude.

$\endgroup$
1
  • 3
    $\begingroup$ This is right; particularly, consider the strategy "Each prisoner is assigned a box; for n rounds, they choose that box and look inside. (They also open another box and ignore whatever was inside it.) Then, on the nth round, they label their box to the best of their knowledge". This gives strictly increasing probability if you increase n, and you can get as close to 100% as you like. $\endgroup$
    – Deusovi
    Oct 15, 2022 at 21:43
-1
$\begingroup$

Here is the process that all prisoners need to follow:

  1. all prisoners are assigned numbers from 1 to 60.

  2. Randomly, any prisoner will go into room and will examine Box one = 2 * ((prisoner number) mod 30)- 1 Box two = 2 * ((prisoner number) mod 30)

    like Prisoner_1 and prisoner_31 both will examine Box_1 and Box_2, P_2 and P_32 both will examine B_3 and B_2,
    P_30 and P_60 both will examine B_59 & B_60

  3. if selected box has no label, he will pick fruit from left side of the box and label it as per following table:

box fruit old label new label
1 orange 2-orange
1 apple 2-apple
2 orange 2-orange
2 apple 2-apple
  1. if selected box has label, he will pick fruit from right side of the box and label it as per following table:
box fruit old label new label
1 orange 2-orange 2-orange
1 orange 2-apple apple and orange
1 apple 2-orange orange and apple
1 apple 2-apple 2-apple
2 orange 2-orange 2-orange
2 orange 2-apple apple and orange
2 apple 2-orange orange and apple
2 apple 2-apple 2-apple

Once, all 60 prisoners have visited room, all the 60 boxes will have right labels.

This process will work even if all boxes have just one fruit in all of them OR any permutations/combinations of orange and apple in all the boxes.

PS: It has been mentioned in comment that one fruit may not be picked even after all prisoners looks into the box. My point is: It is a possibility. not a constraint. It is like Everyone tosses a coin and it is possible that no one gets a head. There s no restriction or constraint that prisoners can not decide from which side of the box they can pick, right? Prisoners are at liberty to pick any one fruit from the box whichever way they want. Also, it was mentioned that boxes are left untouched, unshuffled and unchanged throughout the process. So if all prisoners agree beforehand to follow the same above strategy, they all can be freed with 100% guaranteed result

Edited: Edited to make it more clear.. pick left side of fruit was changed to pick fruit from left side of the box and likewise for right side. also, added PS: phrase.

$\endgroup$
6
  • 3
    $\begingroup$ There is no "left side of the fruit" or "right side of the fruit". It was confirmed in the comments of the question that "Even if everyone looks in a particular box, it's possible that one of the fruits never gets picked". $\endgroup$ Feb 13, 2023 at 15:54
  • $\begingroup$ @JaapScherphuis, I agree and I know. It is a possibility not a constraint. It is like Everyone tosses a coin and it is possible that no one gets a head. There s no restriction or constraint that prisoners can not decide from which side of the box they can pick, right? $\endgroup$ Feb 14, 2023 at 6:06
  • $\begingroup$ It has been mentioned in comment that one fruit may not be picked even after all prisoners looks into the box. My point is: It is a possibility. not a constraint. Prisoners are at liberty to pick any one fruit from the box whichever way they want. Also, it was mentioned that boxes are left untouched, unshuffled and unchanged throughout the process. So if all prisoners agree beforehand to follow the same above strategy, they all can be freed with 100% guaranteed result. $\endgroup$ Feb 14, 2023 at 6:06
  • 1
    $\begingroup$ "It's possible that one fruit isn't picked after all prisoners look" is a constraint. It means that you can't make a strategy that makes it impossible - you can't choose which of the two fruits you pick. $\endgroup$
    – Deusovi
    Feb 17, 2023 at 15:16
  • 1
    $\begingroup$ If it was just a possbility, it would be no more meaningful than "it's possible nobody looks in box 1": there would be no reason for OP to say that, because it's just saying "you can choose a bad strategy if you want". So instead, the intended interpretation is that it's not possible to guarantee both fruits are seen - that is, there's no way to pick the "left fruit" or the "right fruit" in a box. $\endgroup$
    – Deusovi
    Feb 17, 2023 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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