7
$\begingroup$

There are 5 boxes labeled A, B, C, D and E. Each box contains a distinct number, but you don't know what it is. You can select three boxes and the Oracle will tell you which box contains the median* of the three selected numbers. How can you figure out which box contains the median of all 5 numbers? Can you do it in the least number of steps (selections)? Good luck!

*The median of a set of numbers is a number that has just as many numbers above and below it in the set.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
15
$\begingroup$

I'll use my own box labelling so that the method is shorter to describe.

Step 1: First I'll remove the labels, then pick any three boxes and test them. Whichever of the three boxes is the median I'll label B, and the other two boxes are A and C.

Step 2:

Pick B and the two unlabelled boxes. If the median of these is again box B, then we are done - B must be the median. If the outcome is another box, I'll label that box E, and the other unlabelled box becomes D.

Step 3:

Test A, C, and E. The outcome of this test is the median of the five boxes.

Reasoning:

If the first two tests have the same answer B, then that must be the median because B must have A,C on either side and also D,E on either side. So it has 2 boxes on either side and is therefore the median.
If second outcome is E, then median cannot be B (B has D, E, and one of A,C on one side) and also not D (it has B, E on one side, and beyond B there must also be one of A or C).
Note also that whichever side of the median B lies, one of A or C must lie beyond it, leaving no room for anything else. This means that B and D lie on different sides of the median. Removing them both will not change the median, so that the median must be whichever one of A, C, E lies in the middle.

Proof of optimality:

Suppose there was a method using only two steps. The two steps must involve all 5 boxes (any untested box could be the median but you would never know it from the results of your tests on the other boxes). Therefore the two tests must have exactly one box in common. If the shared box is the median in one of the two tests, then with appropriate box labelling it matches the first two steps in the solution above. After those two steps, any of A, C, E could still be the median (e.g. ABCDE, CBEDA, CBAED). Regardless of which of the three boxes from the first test you choose to reuse in the second test, it is possible for the outcome of the second test to be such that the shared box is the median in only one of the tests. So two tests are not guaranteed to be sufficient.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very well done! This is even better than my intended solution that uses more steps. I wonder if this genetalizes to more boxes? $\endgroup$
    – Dmitry Kamenetsky
    Jan 21, 2021 at 13:08
  • 1
    $\begingroup$ I think in your last line it should be "ABCED, CBEDA, CBAED", because E must be between B and D after the second step. $\endgroup$
    – wimi
    Jan 21, 2021 at 14:03
  • $\begingroup$ Thanks @wimi. I'd already fixed it once and still got it wrong. $\endgroup$
    – Jaap Scherphuis
    Jan 21, 2021 at 15:27
  • $\begingroup$ The logic in the last paragraph is slightly incomplete. Although two tests must have one box in common, the second one doesn't necessarily have to use the box B. It could also use A or C. I'm sure you can easily fix it. $\endgroup$
    – WhatsUp
    Jan 22, 2021 at 6:53
  • $\begingroup$ @WhatsUp Thanks, I fixed it. I found it tricky to explain clearly without just listing lots of possible outcomes. $\endgroup$
    – Jaap Scherphuis
    Jan 22, 2021 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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