Question
You are trying to find the 2 fastest dogs out of 12. Only 4 can race at the same time, however. You do not have access to their racing times. Also, as soon as every dog has raced once, only 3 can race at the same time. What is the minimum number of races required to find out the 2 fastest dogs?
Check your answer
Solution
Answer: 5
The minimum is 5 races.
First, divide the 12 dogs into three heats of four and race each heat. Suppose the results are:
\[
A_1>A_2>A_3>A_4
\]
\[
B_1>B_2>B_3>B_4
\]
\[
C_1>C_2>C_3>C_4.
\]
That uses 3 races.
Once every dog has raced, only 3 dogs can race at once. Race the three heat winners:
\[
A_1,\;B_1,\;C_1.
\]
Suppose the result is:
\[
A_1>B_1>C_1.
\]
Then \(A_1\) is definitely the fastest dog overall.
For second place, almost every dog can now be eliminated:
- \(A_3,A_4\) are slower than both \(A_1\) and \(A_2\),
- \(B_2,B_3,B_4\) are slower than both \(A_1\) and \(B_1\),
- every dog in heat C is slower than \(A_1\) and \(B_1\).
So the only possible second-fastest dogs are:
\[
A_2 \quad \text{and} \quad B_1.
\]
Race \(A_2\) and \(B_1\) in the fifth race. The winner is the second-fastest dog overall.
Therefore, the two fastest dogs can be identified in exactly 5 races.