# A Twenty-Five Horse Race

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!