Skip to content

Instantly share code, notes, and snippets.

@Per48edjes

Per48edjes/fiddler_05032024.md

Last active May 17, 2024 20:52
Show Gist options
  • Save Per48edjes/195034d009cabdd8bd3322e7400ad17a to your computer and use it in GitHub Desktop.
Save Per48edjes/195034d009cabdd8bd3322e7400ad17a to your computer and use it in GitHub Desktop.
Download ZIP
Fiddler on the Proof: Fiddler (05/03/2024)
Raw
fiddler_05032024.md

Fiddler on the Proof

Ravi Dayabhai & Conrad Warren 🏃 2024-05-03

Problem

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?

Solution

3 heats are sufficient to identify the top three sprinters among the 25 sprinters at the meet.

Rationale

Very quickly, it can be shown that the answer is either 3 or 4 heats:

  • Three heats are needed, at a minimum, such that everyone races at least once (read: not having a sprinter participate in a heat does not guarantee finding the top sprinters!).
  • Four heats can easily determine the top three runners:
    • Pick 10 runners for Heat 1, and make note of the top three finishers.
    • Pick 10 runners (among those that haven't raced yet) for Heat 2, and make note of the top three finishers.
    • Pick the 5 remaining sprinters who haven't yet raced yet and any other 5 runners for Heat 3, and make note of the top three finishers.
    • Take the top 3 finishers in each of the preceding Heats and any other sprinter for Heat 4. The top three finishers in this heat are the three fastest sprinters overall.

So the question becomes: can we determine the first-, second-, and third-fastest sprinters overall using only three heats?

Turns out, we can, indeed! First, let me introduce a bit of notation: let $H_{a,b}$ be the runner who finished Heat $a$ in $b$ th place.

Here's an outline of what's required to deduce the top three fastest sprinters over only three heats:

  1. Randomly choose 10 racers for Heat 1. Record $H_{1,1}$, $H_{1,2}$, and $H_{1,3}$.
  2. Randomly choose 9 racers among those who have not run yet. Race these 9 and $H_{1,2}$ in Heat 2. Keep track of the "Special Group" based on the results of this heat (more on this below).
  3. Take the remaining 6 sprinters who have not competed in a heat yet and race these against the "Special Group" for Heat 3.

The top three finishers in Heat 3 are the overall top three fastest sprinters!

So...what's the "Special Group"? It depends on how $H_{1,2}$ fares in Heat 2:

  • $H_{1,2}$ is $H_{2,1}$: The "Special Group" consists of $H_{1,1}$, $H_{2,1}$ (same as $H_{1,2}$), $H_{2,2}$, and $H_{1,3}$.
    • The top two finishers from Heat 1 need to stick around because while they are the fastest seen, they need to be tested against the yet-to-be seen runners in Heat 3.
    • We can say definitively conclude that at least 2 runners are faster than $H_{2,2}$, but cannot say yet who is the faster between $H_{2,2}$, and $H_{1,3}$ -- this will be decided in the subsequent heat.
  • $H_{1,2}$ is $H_{2,2}$: The "Special Group" consists of $H_{1,1}$, $H_{2,1}$, $H_{2,2}$ (same as $H_{1,2}$), and any other runner.
    • We don't care about $H_{1,3}$ anymore since we know at least 3 runners are definitively faster from the first two heats.
    • It doesn't matter who the last runner is in the "Special Group" since we already have determined the fastest three sprinters from the runners who've raced.
  • $H_{1,2}$ is $H_{2,3}$: The "Special Group" consists of $H_{1,1}$, $H_{2,1}$, $H_{2,2}$, and any other runner.
    • We don't care about $H_{1,2}$ anymore since we know at least 3 runners are definitively faster from the first two heats.
    • It doesn't matter who the last runner is in the "Special Group" since we already have determined the fastest three sprinters from the runners who've raced.
  • $H_{1,2}$ finishes 4th or worse:: The "Special Group" consists of $H_{1,1}$, $H_{2,1}$, $H_{2,2}$, and $H_{2,3}$.
    • Here we have 4 candidates for the top three spot among the runners who have participated in the first two heats, so we'll another heat to determine the final ordering.

Hopefully, this makes sense! 🏃

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment