How to find the 3 fastest horses?

Question

There are $25$ horses. You can take $5$ horses at a time and race them. Each horse always finishes the race in the same amount of time, and there are no ties. The only information you get from each race is the order that the $5$ horses finished in. What is the smallest number of races you need to find the $3$ fastest horses, in order?

---

I found this problem on Brainy Miscellany and cannot figure out the best answer. Please help.

Answer 1

First let's show that it's possible to do this in $7$ races.

Group the $25$ horses into $5$ groups of $5$ and race them. The 4th and 5th place horses of each race cannot possibly be one of the three fastest. We are left with $15$ horses.

Let us label these remaining horses, using a $6$th race to help us. Race the fastest horse from each of the first $5$ races, and then label the races from $a$ to $e$ based on the finishing position of the corresponding fastest horse, with the horse from race $a$ being the fastest. Let $h_n$ represent a horse in race $h$, finishing in $n$th place.

Clearly, horse $a_1$ is the fastest horse of all. We also know that $a_1$ beat $a_2$ and $b_1$. No other horse can possibly be in overall position $2$ because one of these horses finishes between them. $a_2$ beats $a_3$, and $b_1$ beats $b_2$ and $b_3$, as well as every horse in races $c$ through $e$.

Similarly, the only horses that can be in overall position $3$ are $a_2$, $a_3$, $b_1$, $b_2$, and $c_1$. These are the horses that could possibly have no horses in between it and position $2$.

All we have to do left is race those $5$ ($a_2$, $a_3$, $b_1$, $b_2$, and $c_1$) and you'll have the fastest three.

---

Now let's prove that $7$ races is optimal.

Using the same idea, we can draw a directed graphs to represent these races and relations. The circles or nodes are horses, and the directed paths represent one horse being faster than another. Here would be what one race would look like, with the fastest horse on the left:

$$ \circ\rightarrow\circ\rightarrow\circ\rightarrow\circ\rightarrow\circ $$

So basically, what we want to end up with to find the three fastest horses is a parent node and a total of at most $5$ children with a depth of $2$ from this parent, with all of the other nodes being under $5$ children. We need a race to compare these $5$ children, and the other races to set up the graph. Each race will place $4$ horses, as the fastest horse needs to be a horse that has already raced in order to be compared. The only exception is the first race, which can place $5$. $\lceil 24/4 \rceil = 6$, and we add that to our check race to show that the best possible solution is $7$ races, and it can in fact be attained.

EDIT: I fixed the errors hopefully. I'll continue to fix the proof as needed.

Answer 2

Seven races:

1. Five heats of 5 horses
2. A final of the 5 winners, to crown the fastest horse. Retire the horses that finished fourth and fifth.
3. A playoff, with the remaining two horses from the final, as well as the horses from the heats that finished second and third to the champion, and second to the runner-up. The champion doesn't need to be in the playoff. The top two horses in the playoff are the fastest after the champion.

Answer 3

The question

Let's recap the important information

• 25 horses
• all horses have always the same speed and they don't get tired
• horses don't have the same speed
• you can get the order of 5 arbitrary horses with one experiment
• Question: What is the minimum number of experiments you have to run to get the 3 fastest horses?

Find an upper bound

Find only fastest horse

Obviously, you need to race at least every horse. So you need at least $\frac{25}{5} = 5$ experiments. Lets say the horses have are named by letters and $a > b$ means $a$ is faster than $b$. So you get:

$a < b < c < d < e$

$f < g < h < i < j$

$k < l < m < n < o$

$p < q < r < s < t$

$u < v < w < x < y$

But after $5$ experiments with distinct horses you don't know which of the 5 winners ($e, j, o, t, y$) is the fastest. So you need at least $1$ more experiment to get the fastest one:

$e < j < o < t < y$

Great, we can find the fastest one with 6 experiments! (It's $y$).

Find fastest and second fastest horse

But what about the two fastest ones? Well, eventually $x$ is faster than $t$. So you have to make another test. But you can be sure that $e$, $j$ and $o$ are not second fastest, so you can skip them.

The only candidates for the second-fastest horse are $x$ and $t$. So keep in mind that we have $3$ horses left that we can compare in this race!

We can find the fastest and the second fastest horse in $7$ experiments.

Find first, second and third-fastest horse.

Who could be third-fastest?

$x, t$ and the next one in the queue who was second fastest. So:

• if $x$ is second fastest, then $t$ and $w$ could be third-fastest.
• if $t$ is second fastest, then $x$ and $s$ could be third-fastest.

So we only have $s$ and $w$ as candidates for the second-fastest place!

As a result:

We need 7 races to find the 3 fastest horses.

The pattern

In the first step you get queues with the fastest horse on top. In all following steps you only compare the top of those queues.

Imagine you have queues of cards. Those cards have an order. In the first step, you make 5 queues of ordered cards. In every following step you compare the top of that queues.

A more general solution

Let's say you have $n$ horses and in each experiment you can compare $m$ horses and you want to get the top $t$ horses.

If $m \geq n$, you're ready. You only need one experiment.

Else, you make $\lceil \frac{n}{m} \rceil$ experiments to get the queues.

If $\lceil \frac{n}{m} \rceil < m$, you make $t$ comparisons of the top of the queues.

Else you make queues of the top of the queues ... ok, I really don't want to go through this now.

There might be better solutions, but I thing this is a good start.

Sorting algortihms

I would like to mention that sorting alorithms have $m = 2$. In that case, the optimal number is well-known:

• You can have $n!$ permutaitons of $n$ elements.
• With every step, you can half the number of candidates
• $\log_2(n!) <\log_2(n^n) = n \cdot \log_2(n)$

Answer 4

Solution: answer is 7 races.

Step 1: First, we group the horses into groups of 5 and race each group in the race course. This gives us 5 races.

W11 W12 W13 W14 W15

W21 W22 W23 W24 W25

W31 W32 W33 W34 W35

W41 W42 W43 W44 W45

W51 W52 W53 W54 W55

Step 2:we race the 5 level 1 winners(w11,w21,w31,w41,w51) ans assume winning order of this race is w11,w21,w31,w41,w51

Step 3: BECAUSE WE NEED TOP 3 AND W41 HAS COME 4TH Position that is the reason we don't need to consider W41 W42 W43 W44 W45 and also W51 W52 W53 W54 W55 now we have

W11 W12 W13 W14 W15

W21 W22 W23 W24 W25

W31 W32 W33 W34 W35

Step 4: because we need top 3 then dont need W14 W15 W24 W25 W34 W35

now we have

W11 W12 W13

W21 W22 W23

W31 W32 W33

Step 5: because in 6th race W31 has come on 3rd position that is the reason we do not need to consider W32,W33 and also we will not consider W23 now we have

W11 W12 W13

W21 W22

W31

Step 6: top 1 is already achieved which is W11(winner of 6th race) remaining are

W12 W13

W21 W22

W31

Step 7: now race W12 w13 w21 w22 w31 to get 2nd and 3rd winner

Hence answer is 7 races.

25 horses 5 tracks 5 fastest horses puzzle | Google Interview Question http://codinginterviewquestionsans.blogspot.in/2017/07/25-horses-5-tracks-5-fastest-horses.html