This week’s Monday Math Madness was a bit of a brain strainer. I didn’t get the ideal solution, but hey, whatever. I still enjoyed working on it. The solution that I proposed is after the fold.
It’s easier for me to think about the problem by changing it a bit. Instead of using laptops, I’m going to pretend that we have 25 blank envelopes with the numbers 1 to 25 written on a slip of paper inside them. (Each envelope corresponds to a laptop, and the numbers are the speed of the laptop. To be clear, in my scenario, I’m saying the envelope with 25 in it corresponds to the fastest laptop and the envelope with the 1 in it corresponds to the slowest laptop.) We can hand the five envelopes to someone who will re-order them from smallest number to largest number and hand them back to us.
We want to find the envelopes with the 25, 24, and 23 on the slip of paper inside of them.
Because this is a bit of a complicated problem to think about, I made visual aids to show what’s going on at each step. In the visual aid, we can see what’s in the envelope to see how each step works!
Let’s just jump right in by getting some initial information about the envelopes. First, we should divide the 25 envelopes into 5 groups of 5 envelopes each, and test each of these groups. That will give us some basic information.
Because we’re mathematicians and math teachers, we like to label things, so we’re going to give each of these envelopes a name. For the first group, we will call the envelopes:
A1 < B1 < C1 < D1 < E1
(Recall I said that the person will order them from smallest number to largest number.)
We will name the second, third, fourth, and fifth groups similarly, to get the following:
A1 < B1 < C1 < D1 < E1
A2 < B2 < C2 < D2 < E2
A3 < B3 < C3 < D3 < E3
A4 < B4 < C4 < D4 < E4
A5 < B5 < C5 < D5 < E5
Clearly the envelope with 25 in it is either in E1, E2, E3, E4, or E5 (if this isn’t clear, think about this: if you take 25 numbers and split them into 5 groups of 5, the number 25 has to be in one of the groups, and when you rearrange them from smallest to largest, 25 will be the largest number in one of those groups.) Thus, we hand those envelopes to the person who reorders them from smallest to largest.
We take the largest of those and know with certainty it has 25 written on the slip of paper inside! Let’s set it aside.
Let’s think about the envelopes with 24 and 23 in them. I can say with certainty that the envelope with 24 in it is either in one of the D or E envelopes. I can also say with certainty that the envelope with 23 in it is in one of the C, D, or E envelopes.
If this isn’t clear, think about this. If 24 were in one of the Cs, for example C3, then D3 must be 25 (because D3>C3), and then there isn’t anything E3 could be! A similar argument follows for 23.
So to be repetitive, we know that 24 is in one of the D or E envelopes, and 25 is in one of the C, D, or E envelopes.
Hand all the D envelopes to the person to order from smallest to largest.
This is great, because we know that 24 is either the largest remaining E (after we took out the envelope with 25 in it) or the largest D. Let’s file that information away for a minute and work on finding 23.
We know 23 is in C, D, or E — but we already have D and E ordered, so we should order C.
So we give all the C envelopes to the person to order from smallest to largest.
We know that 23 is either in the largest C envelope, the largest or second largest D envelopes (24 could be in the largest, so 23 could be in the second largest), or the largest remaining E envelope.
So we know that 24 is either in the largest D or largest E envelope, and the 23 is in the largest E envelope, the largest or second largest D envelope, or the largest C envelope.
So we hand the person largest E envelope, the largest D envelope, the second largest D envelope, the largest C envelope, and (as a filler) envelope A1 (we know that all the A envelopes are less than 22). Hence, we are guaranteed to have 23 and 24 in those 5 envelopes.
We get them back and the largest of those envelopes is 24 and the second largest of those envelopes is 23. And we are done! A total of 9 tests!
After we take out the envelopes with 23 and 24, the board in our example looks like this:
It took us a total of 6 tests to find the envelope with 25 in it, and 9 tests to find the envelope with 23 and 24 in it.
So it takes 9 tests to get 23, 24, and 25.