Can You Beat the Heats?

This Week's Fiddler

First, we know that there must be at least three heats. Two heats would only sample at most 20 players, leaving 5 players that we have no data on. Now we can show that there is a solution available with using exactly three heats.

Choose 10 players to go on a first heat. Say first place is A, second place is B, and third place is C.

Now choose B and 9 new players to go into a second heat. Say first place is D, second place is E, and third place is F.

Now we determine who we send to the last heat. In addition to the remaining 6 players, we can throw in up to four previous players who are candidates for being top 3. It all depends on where B placed in the second heat. If...

  1. B is D, then A, B, C, and E are the candidates we send. This is because if A and B are the best, C and E are the only players who stand a shot at being third.
  2. B is E, then A, B, and D are the candidates we send. This is because A and D are both better than B, making B third in said list, removing all other players in the first two heats from being relevant.
  3. B is F, then A, D, and E are the candidates we send. This is because all three are strictly better than B, preventing B from having a shot at top 3.
  4. B is not D, E, or F, then A, D, E, and F are the candidates we send. This is because B cannot be top 3, making C not top 3, and leaving the other four as candidates.

After doing this, simply take the top 3 of the third and final heat as the answer.

Answer: 3


Extra Credit

Merge-insertion sort (10 steps)

We want to sort 6 items while minimizing comparisons. The algorithm that does this best is merge-insertion sort.

First, pair up the six sprinters, and compare each of the pairs. Say they are A, B, C, D, E, and F, and they are paired A-B, C-D, and E-F. Without loss of generality, let's continue saying that A beat B, C beat D, and E beat F. This requires three head-to-head races.

Now we want to face the winners of each pair (A, C, and E) off with each other to get an absolute ordering; in the worst case, this requires three races. WLOG, let's say A beats C, who beats E. Since F is worse than E, we can safely put F after E.

Now we have an ordering between four of the sprinters: A, C, E, and F. We can binary search the positions of the final two, starting with B, facing off against E. If B wins, B faces off against C; otherwise, B faces off against F. By the end of these two races, we know where B lands, as we already know that A beats B.

To determine D's position, we do the same thing, except now starting with the middle sprinter after C. Let's say B landed between E and F in the last two races, leading the order to be A, C, E, B, and F; in this case, we would first match D against B. Then, we match D against either E or F, allowing for a final position to be determined after two races.

In all, the worst case with this algorithm would take 10 races (3 + 3 + 2 + 2) to fully order the six sprinters.

Site note: This is a sequence A001768 on OEIS!

Answer: 10