An interview question that came my way and spoke to my interests:

Your task is to determine which three horses out of a group of 25 horses are the fastest. You may race up to five horses at a time. How many races are required?

Have a crack at it yourself, if you’re so inclined. There are spoilers below the line.

Bounds

There must be at least five races: each horse must appear in a race.

The most brutal way I can think of requires at most 11 races: pick any five horses in the competition and race them. Remove the slowest two from the competition. Repeat until you’ve eliminated 22 horses.

So that gives us a lower bound of 5 and an upper bound of 11 without doing too much thinking.

My approach

I think it can be done in seven races, and would be extremely surprised if it could reliably be done in six.

Here’s my approach:

  • Split the 25 horses into five groups of five, and race each group. (5 races)
  • Race the five horses that won their races, determining a champion and a runner-up (1 race)
  • The most complicated one: the final race involves
    • The second- and third-placed horses in the champion’s first race
    • The second- and third-placed horses in the champion’s second race
    • The second-placed horse in the runner-up’s first race

The champion and the two fastest horses in the final race are (in that order) the fastest three horses.

Why?

In this system, the final race involves every horse that hasn’t been beaten by at least three other horses – taking ‘beaten’ to include a horse that’s definitely faster being beaten. (For example, take the race won by the horse that finishes third in race six: every horse in that race except the winner must be slower than the winner, as well as the first two horses in race six).

I thought that was an interesting question – did you come up with a different approach? Can you do it in fewer races? I’d love to hear about it if so!