The Horse Race

The 25 horses at the Belleville Race Track always finish according to their rank: the champion horse wins every race; the number two horse always finishes before everyone else, but loses to the champion; number three loses only to number two and champion and so on - the runt always finishes last. 

All of this was well-documented until the race officials lost all their records and time-keeping devices in a flood.  This was bad timing because they need to send their best three horses (ranked in order) to the National Championship as soon as possible.  All the horses look alike, so they need to hold a new set of races to re-establish their best, second-best, and third-best horses.  Their track can only hold 5 horses at a time.  What is the fewest number of races necessary to establish first, second, and third?

Hint: only 7 races are necessary.  But how?








Solution courtesy of Dan Phelan.


We will solve by eliminating horses that have no chance of placing in the top 3.  First divide the horses randomly into groups of 5 and race each group. 
[5 races]
This allows you to remove the 2 slowest horses from each group.  It also ranks each horse within that group.

Then race each 1st place horse from each group to establish the champion.  Call this the championship race.  Now for the sake of explanation, we will say the 1st place horse came from "group 1", the second place horse came from "group 2", the third place horse came from "group 3" and so on. 
[+1 race]

We now know the #1 horse.  Now we need to establish #2 and #3. 

• We can eliminate any horse that has ever lost to 3 or more horses, because there is no way it can place 2nd or 3rd.  Thus we can eliminate all horses from groups 4 and 5 from the running, because even their best horses still lost to the top 3 from the championship.  This leaves us with group 1, 2, and 3.  (15 horses)
  
• We can also eliminate the 4th and 5th place horses from groups 1, 2, and 3.  This leaves the top 3 horses from groups 1, 2, and 3.  (9 horses)
  
• We also know that its impossible for the slower horses in subgroup 3 to be in the top 3 since 3 horses are faster then them.  We can eliminate those as well.  (7 horses)  Similarly, we can eliminate the horse in 3rd place in subgroup 2 with the same logic (6 horses)
• The horse who came in 1st amongst the winners MUST be the fastest, so we can eliminate him from contention (5 horses).

Now we have 5 horses on a 5 horse track.  Run one last consolation race and the 1st place horse is the 2nd fastest and the 2nd place is the 3rd fastest.