Min-Max is a box that is capable of determining which of the two numbers is the higher (Max) and which is lower (Min).
I need to use minimum amount of boxes in order to sort 4 different numbers (any A, B, C, D). For example:
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this communityMin-Max is a box that is capable of determining which of the two numbers is the higher (Max) and which is lower (Min).
I need to use minimum amount of boxes in order to sort 4 different numbers (any A, B, C, D). For example:
You need at least
five boxes,
as each box makes a binary choice (factor of 2), and you have 24 possible orders for the relative values of 4 numbers. See below for an example of a 'minimal' box solution.
The worst-case situation is when the greatest number is at the bottom and/or the least one is at the top, so it/they need(s) to be shifted the farthest.
So you need at least:
three boxes to shift such a number to the opposite side,
and therefore:
five boxes are required in total;
like this (for example):
A - - +-----+ - - - - - - - - +-----+ - - greatest | | | | B - - +-----+ - - +-----+ - - +-----+ - - ... | | C - - +-----+ - - +-----+ - - +-----+ - - ... | | | | D - - +-----+ - - - - - - - - +-----+ - - least
For $n$ numbers you need:
$2*n-3$ boxes in total, arranged in the above illustrated $X$-shape.
Like this for $n=5$:A - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - greatest | | | | B - - +-----+ - - +-----+ - - - - - - - - +-----+ - - +-----+ - - ... | | | | C - - - - - - - - +-----+ - - +-----+ - - +-----+ - - - - - - - - ... | | D - - +-----+ - - - - - - - - +-----+ - - - - - - - - +-----+ - - ... | | | | E - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - leastand this for $n=6$:A - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - greatest | | | | B - - +-----+ - - +-----+ - - - - - - - - +-----+ - - +-----+ - - ... | | | | C - - - - - - - - +-----+ - - +-----+ - - +-----+ - - - - - - - - ... | | D - - - - - - - - +-----+ - - +-----+ - - +-----+ - - - - - - - - ... | | | | E - - +-----+ - - +-----+ - - - - - - - - +-----+ - - +-----+ - - ... | | | | F - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - leastAs you can see, if the top number needs to be shifted to the bottom, it needs to pass through $n-1$ boxes; the same is true for shifting the bottom number to the top; the centre box is shared for both directions, so we get $(n-1)+(n-1)-1$ boxes.