25 Horses

Question

You have 25 horses and a five-lane track, each race compares 5 horses with no timer, giving only finishing order. Horses are perfectly consistent. What is the minimum number of races to find the top 3 horses, and how?

Accepted Answer

7 races. Races 1–5: five heats of five. Label heats by their winner-rank later. Race 6: the five heat winners. Call the result A > B > C > D > E (heats named accordingly). Immediately: - The overall champion is A's heat winner = A (it beat everyone directly or transitively). ✓ 1 found. - D, E, and their entire heats are out (at least three horses provably ahead). Who can still be 2 or 3? Only horses with at most two provably-faster horses: - A_2, A_3 (2nd, 3rd in A's heat), - B and B_2, - C. That's exactly 5 horses: one final race fits them all. Race 7: race A_2, A_3, B, B_2, C; the top two finishers are the overall 2 and 3. Lower bound argument (why 6 can't work): 6 races observe at most 30 horse-slots; an adversary argument shows some candidate orderings remain indistinguishable, in particular, after any 6 races there exist two horses whose relative order is unresolved yet both could be in the top 3. Interviewers usually accept the candidate-counting argument: after races 1–6, five candidates remain for two spots, and no subset-of-5 race was yet run to separate them... so a 7th is necessary and sufficient.

25 Horses

Problem

Your answer

Hints

More Brainteasers & Logic to train on