7
$\begingroup$

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!

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

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.

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

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 5 at 8:09
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Sorry, Spoilers are just not working for me today. >! ends up giving me Blockquote with an ! Spent more time on that than the answer. $\endgroup$ Mar 4 at 22:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – bobble
    Mar 4 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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