[Math] Determine Fastest 3 horses out of 125 when only 5 racing track are given without using stopwatch

algorithmsdiscrete mathematicspuzzle

We have 125 horses, and we want to pick the fastest 3 horses out of those 125. In each race, only 5 horses can run at the same time because there are only 5 tracks. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?

This question was easily solved when there were 25 horses but for 125 horses it is not solvable easily.Can anyone help me out with this complex problem?
This is the link of the question which is also not solved.

Best Answer

OPs strategy for $25$ horses can be extented to $125$ horses resulting in a determination of the fastest three horses within $33$ races.

We can obtain the following information from a race with five horses

  • The horses at the $4^{th}$ and $5^{th}$ position can be ruled out and all other horses which are known to be slower than these.

  • The $3^{rd}$ horse is a candidate at most for the $3^{rd}$ final position and all other horses which are known to be slower than this one can be ruled out.

  • The $2^{nd}$ horse is a candidate at most for the $2^{nd}$ final position and all other horses which are known to be at most one behind it, are candidates fo the $3^{rd}$ final position and all slower horses can be ruled out.

  • The $1^{st}$ horse is a candiate for the first position and similar rules than before hold for the horses which are known to be slower than this one.

Strategy: The maximum amount of information in a race can be retrieved by taking the best horses from former races. This way the maximum number of horses can be ruled out.

Let's number the horses with $1$ to $125$.

Races $1$ to $25$

The table below shows the races $1$ to $25$. Each row represents the outcome of a race. We may without any loss of generality assume, that the ranking is as follows:

The leftmost position gives the winner of the race followed by the others according to their position. The first three are written boldface. They are candidates for the final three positions. \begin{align*} \begin{array}{rrrrrrrrrrrrrrr} \mathbf{1}&\mathbf{2}&\mathbf{3}&\color{gray}{4}&\color{gray}{5}\quad &\quad\mathbf{26}&\mathbf{27}&\mathbf{28}&\color{gray}{29}&\color{gray}{30}\quad\ldots &\quad\mathbf{101}&\mathbf{102}&\mathbf{103}&\color{gray}{104}&\color{gray}{105}\\ \mathbf{6}&\mathbf{7}&\mathbf{8}&\color{gray}{9}&\color{gray}{10}\quad &\quad\mathbf{31}&\mathbf{32}&\mathbf{33}&\color{gray}{34}&\color{gray}{35}\quad\ldots &\quad\mathbf{106}&\mathbf{107}&\mathbf{108}&\color{gray}{109}&\color{gray}{110}\\ \mathbf{11}&\mathbf{12}&\mathbf{13}&\color{gray}{14}&\color{gray}{15}\quad &\quad\mathbf{36}&\mathbf{37}&\mathbf{38}&\color{gray}{39}&\color{gray}{40}\quad\ldots &\quad\mathbf{111}&\mathbf{112}&\mathbf{113}&\color{gray}{114}&\color{gray}{115}\\ \mathbf{16}&\mathbf{17}&\mathbf{18}&\color{gray}{19}&\color{gray}{20}\quad &\quad\mathbf{41}&\mathbf{42}&\mathbf{43}&\color{gray}{44}&\color{gray}{45}\quad\ldots &\quad\mathbf{116}&\mathbf{117}&\mathbf{118}&\color{gray}{119}&\color{gray}{120}\\ \mathbf{21}&\mathbf{22}&\mathbf{23}&\color{gray}{24}&\color{gray}{25}\quad &\quad\mathbf{46}&\mathbf{47}&\mathbf{48}&\color{gray}{49}&\color{gray}{50}\quad\ldots &\quad\mathbf{121}&\mathbf{122}&\mathbf{123}&\color{gray}{124}&\color{gray}{125}\\ \end{array} \end{align*}

$$ $$

Races $26$ to $30$

According to the strategy mentioned at the beginning we take the winners of the first $25$ races and obtain this way the next five races $26$ to $30$. Let's again without any loss of generality assume the following results

\begin{align*} \begin{array}{rrrrrr} \text{race 26:}\quad&\mathbf{1}&\mathbf{6}&\mathbf{11}&\color{gray}{16}&\color{gray}{21}\\ \text{race 27:}\quad&\mathbf{26}&\mathbf{31}&\mathbf{36}&\color{gray}{41}&\color{gray}{46}\\ \text{race 28:}\quad&\mathbf{51}&\mathbf{56}&\mathbf{61}&\color{gray}{66}&\color{gray}{71}\\ \text{race 29:}\quad&\mathbf{76}&\mathbf{81}&\mathbf{86}&\color{gray}{91}&\color{gray}{96}\\ \text{race 30:}\quad&\mathbf{101}&\mathbf{106}&\mathbf{111}&\color{gray}{116}&\color{gray}{121}\\ \end{array} \end{align*} So, we have the five horses $1,26,51,76$ and $101$ at the first position followed by $6,31,\ldots,106$ at the second position and $11,36,\ldots,111$ at the third position. The others are ruled out. From these results we obtain the following constellation.

\begin{align*} \begin{array}{rrrrrrrrr} \mathbf{1}&\mathbf{2}&\mathbf{3}\quad&\quad\mathbf{26}&\mathbf{27}&\mathbf{28} \quad\ldots&\quad\mathbf{101}&\mathbf{102}&\mathbf{103}\\ \mathbf{6}&\mathbf{7}&\color{gray}{8}\quad&\quad\mathbf{31}&\mathbf{32}&\color{gray}{33} \quad\ldots&\quad\mathbf{106}&\mathbf{107}&\color{gray}{108}\\ \mathbf{11}&\color{gray}{12}&\color{gray}{13}\quad&\quad\mathbf{36}&\color{gray}{37}&\color{gray}{38} \quad\ldots&\quad\mathbf{111}&\color{gray}{112}&\color{gray}{113}\\ \color{gray}{16}&\color{gray}{17}&\color{gray}{18}\quad&\quad\color{gray}{41}&\color{gray}{42}&\color{gray}{43} \quad\ldots&\quad\color{gray}{116}&\color{gray}{117}&\color{gray}{118}\\ \color{gray}{21}&\color{gray}{22}&\color{gray}{23}\quad&\quad\color{gray}{46}&\color{gray}{47}&\color{gray}{48} \quad\ldots&\quad\color{gray}{121}&\color{gray}{122}&\color{gray}{123}\\ \end{array} \end{align*}

We can see five blocks containing five rows each. Since the $4^{th}$ and $5^{th}$ position has been ruled from the first $25$ races, we have only three columns to respect within each block.

If we look at the first block which corresponds to the race number $26$ with the result $1,6,11,16,21$, we see that we can rule out, the $4^{th}$ and $5^{th}$ position $16$ and $21$ and all horses slower than these in the former races. On the other hand when looking at the winner horse with number $1$ we have still to consider the horses numbered $2$ and $3$ at the $2^{nd}$ and $3^{rd}$ position.

$$ $$

Race 31:

Now we consider the next race with the five winners of races $26$ to $30$ and assume WLOG the following result:

\begin{align*} \begin{array}{rrrrrr} \text{race 31:}\quad&\color{blue}{\mathbf{1}}&\mathbf{26}&\mathbf{51}&\color{gray}{76}&\color{gray}{101}\\ \end{array} \end{align*}

Since these are the five top positioned horses, we can now already conclude:

The fastest horse is horse number $1$.

Note, there are only three blocks remaining, since we can rule out the horses number $76$ and $101$ and the associated blocks containing all horses slower than these two. Recall that $76$ and $101$ were the top positioned horses of these blocks. So we obtain the following constellation:

\begin{align*} \begin{array}{rrrrrrrrr} \color{blue}{\mathbf{1}}&\mathbf{2}&\mathbf{3}\quad&\quad\mathbf{26}&\mathbf{27}&\color{gray}{28} \quad&\quad\mathbf{51}&\color{gray}{52}&\color{gray}{53}\\ \mathbf{6}&\mathbf{7}&\quad&\quad\mathbf{31}&\color{gray}{32}& \quad&\quad\color{gray}{56}&\color{gray}{57}&\\ \mathbf{11}&&\quad&\quad\color{gray}{36}&& \quad&\quad\color{gray}{61}&&\\ \end{array} \end{align*}

According to the ranking of the top positioned horse with number $1$, the $2^{nd}$ with number $26$ and the $3^{rd}$ with number $51$ the other horses which are further to consider are written in boldface.

$$ $$

Race 32:

Since we know that horse number $1$ is the fastest and according to the result of race $31$ we have the three candidates $$2,6,\text{ and }26$$ for the overall position two (resp. three) and the candidates $$3,7,11,27,31,\text{ and }51$$ for the third overall position. We select the three candidates with position two and two of the other candidates for the next race.

\begin{align*} \begin{array}{rrrrrr} \text{race 32:}\quad&\color{blue}{\mathbf{2}}&\mathbf{6}&\color{gray}{26}&\color{gray}{31}&\color{gray}{51}\\ \end{array} \end{align*}

Only the first and the second position of this race is relevant, since the first gives us the horse with overall position two and the next one provides us with a candidate for position three while the horses with number $26,31$ and $51$ are ruled out. We conclude:

The horse with number two has the overall rank $2$.

We have now the following situation

\begin{align*} \begin{array}{rrrrrrrrr} \color{blue}{\mathbf{1}}&\color{blue}{\mathbf{2}}&\mathbf{3}\quad&\quad\color{gray}{26}&\color{gray}{27}& \quad&\quad\color{gray}{51}&&\\ \mathbf{6}&\color{gray}{7}&\quad&\quad\color{gray}{31}&& \quad&\quad&&\\ \color{gray}{11}&&\quad&\quad&& \quad&\quad&&\\ \end{array} \end{align*}

$$ $$

Race 33:

Last but not least we have to determine which of the horses will get the $3^{rd}$ rank. In the current situation only the horses with number $3$ and $6$ are candidates for the third rank. So the final race is a toss between these two

\begin{align*} \begin{array}{rrrrrr} \text{race 33:}\quad&\color{blue}{\mathbf{3}}&\color{gray}{6}&&&\\ \end{array} \end{align*}

We finally conclude the horse with number three has overall rank $3$.

Note, that there are different possible outcomes for the race 32, but in all cases there are not more than $33$ races necessary to determine the three fastest horses.

Related Question