Prisoners, apples & oranges - revisited

Question

You are one of twelve prisoners, and the warden has a game to play with you.

In a room, there are twelve boxes, four of them contain two apples, four contain two oranges, and the rest one of each, but no one knows which contins how many at the start. They also have '2 apples', '2 oranges' or 'apple & orange' labels (4 of each) on them, and it is known that none of the labels are placed correctly.

The prisoners know the initial positions of the labels.

Each round, six prisoners are randomly chosen to enter the room and see a fruit each from up to six boxes, and swap the labels of two boxes up to six times.

The prisoners have no knowledge of any visits aside from their own.

It is known that every odd-number visit from a prisoner gets to see the 'first' fruit of a box, and on even-numbered visits the 'second' fruit.

After that, they are put into a soundproof room where there is absolutely no communication.

On any visit, you can announce that all the labels have been placed correctly. After that, you and the other prisoners will be released if you're right, or executed if you're wrong.

As always, they may discuss a strategy beforehand.

What is the optimal solution to minimize the days needed to escape?

Answer 1

All boxes are named an numbered with their initial label. a1-a4 for the boxes initial labeled with "2 apples", ao1-ao4 for "apple & orange" label and o1-o4 for "2 oranges". They are labeled like this and we know these labels are all false.

Strategy rules

• A fruit of interest is defined in the strategy steps
• If you check a group of boxes (e.g. ao1-ao4), stop at the first finding of a fruit of interest
• If a group of boxes is checked, you start with the lowest number and the defined condition. E.g. ao1-ao4 initil labeld should be checked for a fruit of interest and ao1 is labeled with "2 apples", start with ao2 instead
• If you check a group of boxes for the second time, start with the box after your last finding
• If you couldn't progress with the rest of your box views, view unchanged boxes from a1-a4 or o1-o4

Starting strategy for the first prisoners to enter (as long as ao labeled boxes are incorrect labeled)

Check the first ao1-ao4 box with the label "apple & orange". If the fruit is an apple look in all 4 a1-a4 boxes, if the fruit is an orange look in all 4 o1-o4 boxes. Stop looking in boxes if you find a fruit with the same label (e.g. an apple in a original labeled "2 apples" box), remember this box and the ao box you checked and change their labels at the end of your turn. If all boxes contain the other fruit, change the labels of the first original labeled box with the ao box you checked. Repeat this strategy. Worst case: The first four prisoners are needed for this strategy

Now all ao1-ao4 boxes are labeled correctly. For the a1-a4 boxes and vice versa the o1-o4 boxes there are more possibilities.

1. Best Case: All a1-a4 boxes are labeled in their original label. Then a prisoner on the first day can change all labels from a1-a4 with the o1-o4 labels and can announce that all labels have been placed correctly.
2. Worst Case: A number of 1-3 boxes from a1-a3 in increasing order are labeled "apples & oranges" and 3-1 boxes (altogether 4 boxes are changed) from o1-o3 in increasing order are also labeled "apples & oranges". Some of the newly labeled boxes contain the not original labeled fruit -> No solution possible until a prisoner saw the second fruit of this boxes.
3. Some mixed results. E.g. a1 and a3 are newly labeled with "apples & oranges", a2 and a4 are original labeled. We know a3 has an apple as first fruit and is labeled correctly. a2 must have an orange as first fruit, because a2 was skipped in our first strategy. a1 could have and apple as first fruit => a2, a4 must have an orange as first and second fruit, because two of the o1-o4 boxes contain "apples & oranges" change labels from a2, a4 with the boxes o1-o4 with the original label and accounce that all labels have been placed correctly OR a1 could have an orange as first fruit => a4 must have an orange as first fruit or else a4 would be labeled with "apples & oranges" -> No solution possible until a prisoner saw the second fruit of this boxes.

With this in mind, in the best cases the next prisoner can check the unclear boxes and find a solution. In most cases the prisoners must wait for a second visit.

In a worst case the prisoners need two second visits. This will occur on the second or third day. The strategy is open the unclear boxes, if the number of unclear boxes is 8, the first prisoner will choose only 6. And the second prisoner with a second visit can announce. Else the first prisoner can announce. Per definition all original labeled and some "apples & oranges" boxes (see mixed results/worst case) are unclear boxes. From his first visit the prisoner knows 2-6 first fruits of unclear boxes, if the logic after the starting strategy helps him to reduce unclear boxes to a maximum of six boxes, he can open all this boxes, change the labels and announce.

Strategy for the second visit on unclear a1-a4 boxes (vise versa for o1-o4)

• Label "2 apples": First fruit must be orange
  • 2nd fruit apple -> "apples & oranges"
  • 2nd fruit orange -> "2 oranges"
• Label "apples & oranges": First fruit must be orange.
  • 2nd fruit apple -> labeled correctly,
  • 2nd fruit orange -> "2 oranges" Check a box labeled "2 apples", if you see an apple, check the unclear a1-a4 boxes labeled "apples & oranges" for an orange -> check o1-o4 unclear boxes labeled "2 oranges" for an apple -> "2 apples" in this box

In the best case scenario the prisoners escape in one day, worst case scenario with not more than one prisoner visiting twice on day two is three days and the normal case is two days.

The probability for no prisoner visiting twice on day two is ${p(k=0)}={{6\over12}{5\over11}{4\over10}{3\over9}{2\over8}{1\over7}}={6! 6! \over 12!} < 0.11\%$

The probability for one or less prisoner visiting twice on day two is ${p(k\leq1)}={p(k=1)+p(k=0)}={{6\over12}{5\over11}{4\over10}{3\over9}{2\over8}{6\over7}\binom{6}1+p(k=0)}\approx4.00\%$