Algorithm Design Exercise 1-29: Finding the Fastest of 25 Horses

2017-05-25 (Thursday) | 900 words (~4 minutes reading)

Notes to myself.

This is exercise 1-29 from The Algorithm Design Manual.

There are 25 horses. At most, 5 horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done.

This is quite a famous puzzle question and involves some algorithmic thinking.

The first key to understanding for me was to focus on excluding horses who are slower than at least 3 other horses. This lets you run a process of elimination instead of a process of selection.

The second key for me was that you’re not just sorting individual horses but also sorting sets by their fastest horse.

With those two points in mind, you can go through the process.

First we have to run 5 races to race all of the horses. Rather than label them $a_1$, $b_2$ etc like other explanations, I’ve colour-coded the horses in each set. This seems easier to think about for me.

After racing the 5 colour-coded sets, we’ve got 5 sets of horses where we know the relative ordering within each set:



5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎

Because we can eliminate any horse that is slower than at least 3 other horses, we can get rid of the last two horses in each group (the 4th and 5th positions), leaving us with 15 horses:



5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎

Now we race the fastest (1st position) horse from each group in a sixth race:



1🐎︎ 1🐎︎ 1🐎︎ 1🐎︎ 1🐎︎

This sixth race does two things. It lets us identify the fastest single horse overall, as it’s the fastest of the fastest. Less intuitively, but essential for solving the puzzle, is that it lets us order the original 5 groups and eliminate more horses.

Let’s say that the order of the sixth race was red, orange, purple, green and blue. Red came first, so it’s the fastest overall horse. We can now also incorporate this extra ranking across the groups:



1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎

(Notice that we’ve “eliminated” the #1 red horse, as we know it’s the fastest overall).

Remember that we can eliminate any horse that is slower than at least 3 other horses. That means we can eliminate the green and blue groups entirely now, because even their fastest horses were slower than at least the fastest red, orange and purple horses:



1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎

As you can see, we’re eliminating more and more horses with this “slower than 3” rule. We can apply it further. We know the 3rd purple horse was slower than the 2nd and 1st purple horse. We also know the 1st purple horse was slower than the 1st orange horse. That’s 3 horses, so we can eliminate the 3rd purple horse:



1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎

Similarly, we know the 2nd purple horse was slower than the 1st purple horse, which was slower than the 1st orange horse and the 1st red horse. Again, 3 horses were faster, so we can eliminate the 2nd purple horse too:



1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎

We can eliminate one more horse with the “slower-than-3” rule: the 3rd orange horse. It was beaten by the 2nd and 1st orange horses, which in turn were slower than the 1st red horse. So the 3rd orange horse is eliminated:



1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎


5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎

Notice that we only have 5 remaining horses to sort now, and only the 2nd and 3rd overall positions to find. We just run a race with those 5 remaining horses to find out:



3🐎︎ 2🐎︎ 1🐎︎ 2🐎︎ 1🐎︎

As it turns out in this example, the 1st purple horse and 2nd red horse take the top two positions in this race. That means the final top three are the 1st red, 1st purple and 2nd red horse:



🐎︎ 🐎︎ 🐎︎

This takes a total of 7 races: the initial 5 groups, the fastest-of-fastest race, and the surviving runners up race at the end.

See also


Tech mentioned