¿Determinar los 3 caballos más rápidos de 125 cuando sólo se dan 5 pistas de carreras sin usar el cronómetro?

Question

Tenemos 125 caballos, y queremos elegir el más rápido 3 caballos de esos 125. En cada carrera, sólo 5 caballos pueden correr al mismo tiempo porque sólo hay 5 pistas. ¿Qué es el número mínimo de carreras necesarias para encontrar los 3 caballos más rápidos sin usar un cronómetro?

Esta cuestión se resolvió fácilmente cuando había 25 caballos, pero para 125 caballos no es fácil de resolver. Este es el enlace de la cuestión que tampoco está resuelta.

Answer 1

La estrategia de OPs para $25$ los caballos pueden extenderse hasta $125$ caballos, lo que resulta en la determinación de la el más rápido tres caballos dentro de $33$ carreras.

Podemos obtener la siguiente información de una carrera con cinco caballos

• Los caballos en el $4^{th}$ y $5^{th}$ posición se puede descartar y todos los demás caballos que se sabe que son más lentos que estos.

• El $3^{rd}$ caballo es un candidato a lo sumo para el $3^{rd}$ posición final y se pueden descartar todos los demás caballos que se sabe que son más lentos que éste.

• El $2^{nd}$ caballo es un candidato a lo sumo para el $2^{nd}$ posición final y todos los demás caballos que se sabe que están como máximo uno por detrás de él, son candidatos para la $3^{rd}$ posición final y se pueden descartar todos los caballos más lentos.

• El $1^{st}$ El caballo es un candidato para la primera posición y reglas similares a las anteriores se mantienen para los caballos que se sabe que son más lentos que este.

Estrategia: La máxima cantidad de información de una carrera puede obtenerse tomando los mejores caballos de las carreras anteriores. De esta manera se puede descartar el máximo número de caballos.

Numeremos los caballos con $1$ a $125$ .

Carreras $1$ a $25$

El siguiente cuadro muestra las carreras $1$ a $25$ . Cada fila representa el resultado de una carrera. Podemos suponer, sin pérdida de generalidad, que la clasificación es la siguiente:

La posición más a la izquierda da el ganador de la carrera seguido de los demás según su posición. Los tres primeros están escritos en negrita. Son candidatos a las tres últimas posiciones. \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*}

$$ $$

Carreras $26$ a $30$

De acuerdo con la estrategia mencionada al principio, tomamos los ganadores de la primera $25$ carreras y obtener así las siguientes cinco carreras $26$ a $30$ . Supongamos de nuevo, sin pérdida de generalidad, los siguientes resultados

\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*} Así pues, tenemos los cinco caballos $1,26,51,76$ y $101$ en la primera posición, seguido de $6,31,\ldots,106$ en la segunda posición y $11,36,\ldots,111$ en la tercera posición. Los demás quedan descartados. De estos resultados obtenemos la siguiente constelación.

\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*}

Podemos ver cinco bloques que contienen cinco filas cada uno. Dado que el $4^{th}$ y $5^{th}$ posición ha sido gobernada desde el primer $25$ carreras, sólo tenemos tres columnas que respetar dentro de cada bloque.

Si nos fijamos en el primer bloque que corresponde al número de carrera $26$ con el resultado $1,6,11,16,21$ vemos que podemos descartar, el $4^{th}$ y $5^{th}$ posición $16$ y $21$ y todos los caballos más lentos que estos en las carreras anteriores. Por otro lado cuando se mira el caballo ganador con número $1$ todavía tenemos que considerar los caballos numerados $2$ y $3$ en el $2^{nd}$ y $3^{rd}$ posición.

$$ $$

Carrera 31:

Ahora consideramos la siguiente carrera con los cinco ganadores de carreras $26$ a $30$ y asumir WLOG el siguiente resultado:

\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*}

Como estos son los cinco caballos mejor posicionados, ya podemos concluir:

El el caballo más rápido es el número del caballo $1$ .

Obsérvese que sólo quedan tres bloques, ya que podemos descartar el número de caballos $76$ y $101$ y los bloques asociados que contienen todos los caballos más lentos que estos dos. Recordemos que $76$ y $101$ eran los caballos mejor posicionados de estos bloques. Así obtenemos la siguiente constelación:

\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*}

Según la clasificación del caballo mejor posicionado con el número $1$ El $2^{nd}$ con el número $26$ y el $3^{rd}$ con el número $51$ los otros caballos que hay que tener en cuenta están escritos en negrita.

$$ $$

Carrera 32:

Como sabemos que el número de caballos $1$ es el más rápido y según el resultado de la carrera $31$ tenemos los tres candidatos $$2,6,\text{ and }26$$ para la posición global dos (resp. tres) y los candidatos $$3,7,11,27,31,\text{ and }51$$ para la tercera posición de la general. Seleccionamos a los tres candidatos con la posición dos y a dos de los otros candidatos para la siguiente carrera.

\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*}

Sólo la primera y la segunda posición de esta carrera son relevantes, ya que la primera nos da el caballo con la posición general dos y la siguiente nos proporciona un candidato para la posición tres mientras que los caballos con número $26,31$ y $51$ se descartan. Concluimos:

El caballo con el número dos tiene el clasificación general $2$ .

Ahora tenemos la siguiente situación

\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*}

$$ $$

Carrera 33:

Por último, pero no por ello menos importante, tenemos que determinar cuál de los caballos obtendrá el $3^{rd}$ rango. En la situación actual sólo los caballos con número $3$ y $6$ son candidatos al tercer rango. Así que la carrera final es un sorteo entre estos dos

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

Finalmente concluimos el caballo con el número tres tiene clasificación general $3$ .

Tenga en cuenta que hay diferentes resultados posibles para la carrera 32, pero en todos los casos no hay más que $33$ carreras necesarias para determinar los tres caballos más rápidos.

Answer 2

El responder según yo debería ser $33$ .

EXPLICACIÓN:
Marquemos los caballos como $X_i$ donde $i=1,2,3,..,125$
En primer lugar, dividimos el $125$ caballos en $25$ grupos de $5$ cada uno.
Digamos que dividimos los caballos de tal manera que el $n^{\text{th}}$ el grupo contiene caballos $X_{5n-4}$ a $X_{5n}$ .
Para cada grupo, hay una carrera de grupo donde todos los $5$ caballos de la carrera del grupo y los titulares de los puestos se identifican por separado.

De esta manera, $25$ carreras en grupo se celebran.

Sin pérdida de generalidad y con el único fin de explicar el problema en un lenguaje sencillo, suponemos que el $1^{\text{st}}$ , $2^{\text{nd}}$ , $3^{\text{rd}}$ , $4^{\text{th}}$ y $5^{\text{th}}$ los titulares de los puestos en el $n^{\text{th}}$ grupo de carreras son, respectivamente, los caballos $X_{5n-4},X_{5n-3},X_{5n-2},X_{5n-1}$ y $X_{5n}$ .

A continuación, tomamos los ganadores del $25$ razas de grupo, a las que llamamos finalistas .
De estos $25$ caballos, los más rápidos $3$ se puede determinar manteniendo $7$ carreras según el Problema de la carrera de 25 caballos .

Así que, a estas alturas, para llevar la cuenta del número de carreras, $25+7=32$ carreras se celebran.

Por último, de nuevo sin pérdida de generalidad y con el único propósito de explicar el problema en un lenguaje sencillo, suponemos que el $1^{\text{st}}$ , $2^{\text{nd}}$ y $3^{\text{rd}}$ los titulares de la posición de esta carrera final son $X_1,X_6$ y $X_{11}$ respectivamente.
Ahora bien, como sólo nos interesan los tres caballos más rápidos, podemos ignorar los demás $22$ finalistas y los caballos estos $22$ finalistas habían derrotado en sus respectivos carreras en grupo ya que ninguno de los finalistas puede estar entre los primeros $3$ y los caballos que habían derrotado tampoco pueden deberse a la misma razón.
Así que la situación se reduce a la $3$ caballos $X_1,X_6$ y $X_{11}$ y el $12$ caballos que habían derrotado en sus respectivas carreras de grupo, es decir $15$ caballos en total.

A continuación viene una lógica importante:

1. Excluimos $X_1$ de todos nuestros cálculos ya que sabemos que es el más rápido.
2. $X_{11}$ puede ser, en el mejor de los casos, el tercero más rápido, por lo que los caballos a los que había vencido en su carrera de grupo no pueden estar entre los tres más rápidos, pase lo que pase.Así que ignoramos estos $4$ caballos a saber, según la consideración, $X_{12},X_{13},X_{14}$ y $X_{15}$ .
3. También $X_{6}$ puede ser, en el mejor de los casos, el segundo más rápido, por lo que entre los caballos que había vencido en su carrera de grupo, $X_7$ puede ser en el mejor de los casos el tercero más rápido y los otros no pueden estar entre los tres primeros caballos más rápidos, pase lo que pase.Así que ignoramos esos $3$ caballos a saber, según la consideración, $X_{8},X_{9}$ y $X_{10}$ .
4. Del mismo modo, estableciendo los mismos argumentos, desde el grupo $1$ , $X_{2}$ puede ser, en el mejor de los casos, el segundo más rápido y $X_3$ puede ser en el mejor de los casos el tercero más rápido y los otros no pueden estar entre los tres primeros caballos más rápidos, pase lo que pase.Así que ignoramos esos $2$ caballos a saber, según la consideración, $X_{4}$ y $X_{5}$ .

Así que desde el $15$ caballos, con la que empezamos nuestra lógica, nos quedamos finalmente con la $5$ caballos a saber $X_{4},X_{5},X_{6},X_{7}$ y $X_{11}$ .

Organizamos $1$ más carrera con estos $5$ caballos y determinar el segundo y tercer caballo más rápido.

CONCLUSIÓN:
Así, hemos utilizado en total $25+7+1=33$ carreras para determinar los tres caballos más rápidos de $125$ caballos.

Espero que esto ayude.