# Prisoners, apples & oranges

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?

• 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?
– Deusovi
Oct 15 at 17:15
• @Deusovi Even if everyone looks in a particular box, it's possible that one of the fruits never gets picked. Oct 15 at 17:23
• 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 Oct 15 at 17:25
• 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. Oct 15 at 17:32
• Hm... do you know if this has a "clean" answer? I feel like it would be very hard to prove optimality here.
– Deusovi
Oct 15 at 17:44

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.

• 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.
– Deusovi
Oct 15 at 21:43