This week the question is: Can You Beat the Heats?
There are 25 sprinters at a meet, and there is a well-defined order from fastest to slowest. That is, the fastest sprinter will always beat the second-fastest, who will in turn always beat the third-fastest, and so on. However, this order is not known to you in advance.
To reveal this order, you can choose any 10 sprinters at a time to run in a heat. For each heat, you only know the ordinal results, so which runner finishes first, second, third, and so on up to 10th. You do not know the specific finishing time for any runner, making it somewhat difficult to compare performances across heats.
Your goal is to determine with absolute certainty which of the 25 sprinters is fastest, which is second-fastest, and which is third-fastest. What is the fewest number of heats needed to guarantee you can identify these three sprinters?
And for extra credit:
At a different meet, suppose there are six sprinters that can race head-to-head. (In other words, there are only two sprinters per heat.) Again, they finish races in a consistent order that is not known to you in advance.
This time, your goal is to determine the entire order, from the fastest to the slowest and everywhere in between. What is the fewest number of head-to-head races needed to guarantee you can identify this ordering?
Highlight to reveal solution:
After a heat, I can eliminate the 7 slowest sprinters. I need to narrow the field to 3 sprinters. 25 – 3 = 22 = 3 * 7 and a bit. So I need 4 heats, just to find the top 3.
(Assume there is no faster way to do this, like choosing the sprinters for the 3rd heat in a clever way. I can’t think of such a clever procedure.)
Luckily that’s also enough to determine their order. Spend 3 heats eliminating 21 sprinters (always choosing sprinters that haven’t been eliminated yet), and there’s 4 left. The 4th heat will clearly show their internal order.
We need 4 heats.
And for extra credit:
With 2 sprinters, it’s easy. A and B race, we’re done.
With 3 sprinters, we need a little more. A and B race, turns out (WLOG) that A is the fastest. We want to check whether C fits in between them. So we race C against (WLOG) A. If C wins, we’re done. If not, we also need to race C against B. At most 3 races.
| Order | Race | Winner | Order |
| (1) A B | A | A B | |
| (1) A B | B | B A | |
| A B | (2) A C | A | A (B or C) |
| A B | (2) A C | C | C A B |
| B A | (2) B C | B | B (A or C) |
| B A | (2) B C | C | C B A |
| A (B or C) | (3) B C | B | A B C |
| A (B or C) | (3) B C | C | A C B |
| B (A or C) | (3) A C | A | B A C |
| B (A or C) | (3) A C | C | B C A |
(Going forward, I assume it’s possible to just add the nth sprinter to n-1 ordered sprinters, and that this is efficient. That I can’t do something clever like, I don’t know, shuffling 2 ordered groups into each other.)
With 4 sprinters, the complexity grows again. Assume we need 3 heats to order A, B and C. Turns out (WLOG) that the order is A B C. First we race B and D. If D wins, race A and D. If D wins again, it’s D A B C. If D loses, it’s A D B C. If on the other hand D loses to B, race D and C. If D wins, it’s A B D C. If D loses, it’s A B C D. 3 + 2 heats.
Notice D didn’t have to race everybody. Racing against B eliminates some options.
With 5 sprinters, there’s a little leap again. We use 5 races to obtain (WLOG) the order A B C D. Race E against (WLOG) B. Worst case, B loses and loses to C and will have to race D. 5 + 3 races.
With 6 sprinters, it’s more of the same. I want to add F to (WLOG) A B C D E, obtained after at most 8 races. Race against C, then against A or D, and worst case against B or E. 8 + 3 = 11 races.
Note: Binary Insertion Sort. There’s something going on with log2 here. I need 1 race to add a 2nd sprinter, 2 races to add a 3rd sprinter, 3 races to add a 5th sprinter. log2( x – 1) + 1 races to add the xth sprinter?
Stuff from ommadawn.dk (Lise Andreasen) 