# Sorting 6 boxes by selecting 3 boxes each time

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!

• I am also interested in sorting 7+ boxes. But I don't know how to solve that efficiently? Mar 6, 2021 at 0:27

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.

• I believe this is correct. I think there is a shorter/simpler solution though. Mar 4, 2021 at 12:49
• @DmitryKamenetsky By "shorter" do you mean four steps? Mar 4, 2021 at 12:52
• Sorry I was referring to a shorter explanation. Mar 4, 2021 at 22:22
• This is pretty elegant. Looks like it works and catches all the cases. Mar 5, 2021 at 0:36
• @DmitryKamenetsky, I'd be interested in your shorter explanation Mar 12, 2021 at 1:27

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.

• If you use a fixed strategy (i.e. no selection depends on the outcome of a previous comparison), then 6 is the minimum, and yours is certainly the most elegant of those. Proving 6 is minimal for fixed strategies is a nice exercise. Mar 5, 2021 at 8:09
• Is there a formula of permuations and combinations that helps us easily realise that every pair of boxes (when 3 boxes are taken at a time) can be compared to each other in 6 steps ? Secondly, is there a proof that for fixed strategies, 6 is the minimum ? Nov 4, 2021 at 0:42
• @HemantAgarwal, for the former, just counting gives 6choose2=15 pairwise comparisons to be made, to be done 3 at a time requires at least 5. However, that would require a perfect partitioning, which is impossible because each box needs to be compared to 5 others, but comparisons happen against 2 others at a time, so parity doesn't work out, and you'll need at least 6. (See mathworld.wolfram.com/SteinerTripleSystem.html.) That doesn't say you need 6 with a fixed strategy though, and I don't have a proof of that. Nov 7, 2021 at 17:08

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%.

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.

• Sorry, Spoilers are just not working for me today. >! ends up giving me Blockquote with an ! Spent more time on that than the answer. Mar 4, 2021 at 22:16
• I've attempted to spoiler parts of the answer - sorry if I did the wrong parts. For the two-spaces trick to work, you need to use a new >! for each line. As you can see in the Markdown source. Mar 4, 2021 at 22:33