Sorting 6 boxes by selecting 3 boxes each time

Question

There are 6 boxes, each containing a distinct number. You can select 3 boxes and the Oracle will tell you which box has the smallest number and which has the largest number of the three selected boxes. Can you use 6 steps (selections) to work out the exact order of numbers in each box, from smallest to highest? Can you solve this in fewer than 6 steps? Good luck!

Answer 1

Here is a strategy that, I think, does five steps, at most.

Step 1: Pick any three boxes for comparison. Label A as the smallest, C as the largest and B as the middle.
Step 2: Pick B and two of the unknown boxes. Either both will be larger than B (case 2.1), both smaller (case 2.2) or one larger and one smaller (case 2.3).

In Case 2.1:
Label the new boxes bigger than B as D and E (with D<E).
Step 3: Pick A, B and the remaining unknown box, F.
Step 4: If F < B then pick C,D,E and the order of boxes is determined. Otherwise pick C,D,F.
Step 5: Pick C,E,F for comparison and the order of the boxes is determined.

In Case 2.2:
Label the new boxes smaller than B as D and E (with D<E).
Step 3: Pick B, C and the remaining unknown box, F.
Step 4: If F>B, then pick A,D,E for comparison and the order of the boxes is determined. Otherwise pick A,D,F.
Step 5: Pick A,E,F for comparison and the order is determined.

In Case 2.3:
Label the box smaller than B as D and the box bigger than B as E.
Step 3: Compare A,D and the remaining unknown box, F.
Step 4: IF F< max(A,D), pick B,E,C for comparison and the order is determined. Otherwise, compare C,E,F.
Step 5: If F > min(C,E), the order of the boxes is determined. Otherwise, compare F,B and any other box to determine the final order of the boxes.

Answer 2

There's an elegant overkill with six selections: with boxes numbered as $\mathbb{Z}_6$, take selections $\{i, i+1, i+3\}$ for each $i\in\mathbb{Z}_6$, addition of course also done modulo 6. In this way, every pair of boxes has been directly compared at least once.

Answer 3

Here's another 5-step strategy, similar to @hexomino's:

Steps 1 & 2:

Divide the boxes into two groups of three, and compare each group. Label the boxes of the first group in ascending order as A, B, C. Label the boxes of the second group in ascending order as D, E, F. We now have A < B < C and D < E < F

Steps 3 - 5:

Compare B, D, and E, yielding one of these results after 3 total comparisons:

Case I: A < B < C and A < B < D < E < F
In this case, at most two more steps are needed to position C relative to D, E, and F, completing the sort (for example, C,D,E and C,E,F).
Case II: A, D < B < C, E and D < E < F
In this case, two more steps complete the sort, one for each side of B. For example, A,D,B and C,E,F.
Case III: A < B < C and D < E < B < C and D < E < F
In this case, two more steps are needed to complete the sort: A,D,E to position A relative to D and E, and B,C,F, to position F relative to B and C.

Overall, the fully-sorted result is obtained in 4 steps 10% of the time

(when the first group happens to contain the two smallest numbers, and the other member of that group is on the appropriate side of the median of the second group),

and in five steps the other 90%.

Answer 4

I used the Quicksort idea:

Let the boxes have values 1 - 6
Line the boxes up left to right and label their positions ABCDEF

Preliminary

1: Sort ABC in place (1 ) Choose the middle box (B) Label it P
2: Sort BDE in place (2)
3: Sort PCF in place (3)
P is now in the correct place and everything smaller is to the left, and everything larger is to the right.

Simple Case:

If P is at C or D (mirror cases):
4: Sort ABC,
5: Sort DEF DONE! (5 sorts total)

Less Simple Case:

If P is B, then AB are in place and we need to sort CDEF
4: SORT CDE , Label D as new pivot - This will be 4 or 5
5: SORT DEF. Our pivot is now in the correct place. Possible states are:
3456
3465
3456
4356

Simply sort the "fat" side of the pivot.

6: If our penultimate state is CPEF - Sort PEF
6: If our penultimate state is CDPF - Sort CDP

If P is E, then similarly sort ABCD.