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.
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.
The answer according to me should be $33$.
EXPLANATION:
Let us mark the horses as $X_i$ where $i=1,2,3,..,125$
First we divide the $125$ horses into $25$ groups of $5$ each.
Say we divide the horses in such a way that the $n^{\text{th}}$ group contains horses $X_{5n-4}$ to $X_{5n}$.
For each group, there is a group race where all the $5$ horses of the group run and the position-holders are separately identified.
In this way, $25$ group races are held.
Without loss of generality and solely for our purpose to explain the problem in easy language, we assume that the $1^{\text{st}}$, $2^{\text{nd}}$, $3^{\text{rd}}$, $4^{\text{th}}$ and $5^{\text{th}}$ position holders in the $n^{\text{th}}$ group race are respectively the horses $X_{5n-4},X_{5n-3},X_{5n-2},X_{5n-1}$ and $X_{5n}$.
Next we take the winners of the $25$ group races, whom we call the finalists.
From these $25$ horses, the fastest $3$ can be determined by holding $7$ races as per the 25 horse race problem.
So, by now, to keep track of the number of races, $25+7=32$ races are held.
Finally, again without loss of generality and solely for our purpose to explain the problem in easy language, we assume that the $1^{\text{st}}$, $2^{\text{nd}}$ and $3^{\text{rd}}$ position holders of this final race are $X_1,X_6$ and $X_{11}$ respectively.
Now since we are interested only in the three fastest horses, we can ignore the other $22$ finalists and the horses these $22$ finalists had defeated in their respective group races since none of the finalists can be among the top $3$ and the horses they had defeated also cannot be due to the same reason.
So the situation boils down to the $3$ horses $X_1,X_6$ and $X_{11}$ and the $12$ horses they had defeated in their respective group races i.e. $15$ horses in total.
Next comes an important logic:
So from the $15$ horses, we started our logic with, we are ultimately left with the $5$ horses namely $X_{4},X_{5},X_{6},X_{7}$ and $X_{11}$.
We organise $1$ more race with these $5$ horses and determine the second and third fastest horses.
CONCLUSION:
Thus, we have used in total $25+7+1=33$ races to determine the three fastest horses out of $125$ horses.
Hope this helps.
