Por qué 6 carreras no son suficientes en el problema de 25 caballos, 5 pistas

Question

El enigma de las carreras de caballos se ha planteado en mathSE varias veces ( 1 , 2 , 3 , 4 ); también hay un generalización . A continuación, reitero el rompecabezas:

25 caballos que corren a diferentes velocidades. Puedes correr con 5 caballos a la vez para clasificarlos por orden de velocidad, pero en realidad no aprendes sus velocidades numéricas al correr con ellos. ¿Cuántas carreras son necesarias para determinar el tercer caballo más rápido?

La estrategia correcta para hacerlo en 7 carreras se ha descrito en detalle aquí y en otros lugares de Internet. Pero ¿por qué no son suficientes 6 carreras?

---

El único intento de mostrar 6 carreras no es suficiente (en esta respuesta ) es bastante ondulado:

Ahora vamos a demostrar que $7$ carreras es óptima.

Utilizando la misma idea, podemos dibujar un gráfico dirigido para representar estas razas y relaciones. Los círculos o nodos son los caballos, y los caminos dirigidos representan que un caballo es más rápido que otro. Este sería el aspecto de una carrera, con el caballo más rápido a la izquierda:

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

Así que, básicamente, lo que queremos terminar para encontrar los tres caballos más rápidos es un nodo padre y un total de como máximo $5$ niños con una profundidad de $2$ de este padre, estando todos los demás nodos bajo $5$ niños. Necesitamos una carrera para comparar estos $5$ niños, y las otras razas para establecer el gráfico. Cada raza colocará $4$ caballos, ya que el caballo más rápido tiene que ser un caballo que ya haya corrido para poder ser comparado. La única excepción es la primera carrera, que puede colocar $5$ . $\lceil 24/4 \rceil = 6$ y lo añadimos a nuestra carrera de comprobación para demostrar que la mejor solución posible es $7$ razas, y de hecho se puede conseguir.

Realmente no sigo este razonamiento, y no creo que ofrezca una justificación rigurosa.

Ten en cuenta también que 6 carreras SON suficientes si tienes suerte. Así que un argumento correcto tendrá que apelar a algún tipo de escenario del peor caso.

¿Alguien tiene una versión rigurosa de este argumento, o un argumento riguroso diferente, para demostrar que 6 carreras no son suficientes? Me gustaría tener una solución lo más elegante posible.

Answer 1

Suponga que tiene un algoritmo para encontrar los tres primeros puestos en 6 carreras. Suponga que después de la quinta carrera $n$ los caballos han corrido. Si $n=25$ Entonces, la última carrera sólo puede determinar el ganador, pero no el segundo ni el tercer puesto: tiene que correr un caballo de cada carrera anterior, por lo que si los tres primeros puestos estuvieran todos en la misma manga o 1,2 en la misma y 3 en una diferente, no podría distinguir la diferencia.

Así que $n<25$ y en la última carrera hay que competir con los nuevos caballos contra los tres primeros puestos A1, A2, A3 (posiblemente sin saber el orden) del $n$ caballos que ya han corrido, de lo contrario no se puede determinar los tres caballos más rápidos en general con la última carrera.

Por lo tanto, $n=23$ o $n=24$ .

Si asume $n=23$ Entonces es imposible determinar los tres caballos más rápidos de 23 con 5 carreras:

No puede tener menos de tres ganadores diferentes, ya que sólo se permiten dos repeticiones.

Si tiene tres ganadores diferentes que no han sido comparados, entonces cualquiera de los 5 segundos puestos podría ser A2 o A3.

Si tiene cuatro o más ganadores diferentes que no han sido comparados, todos ellos podrían ser A1,A2 o A3.

Si $n=24$ Entonces hay que conocer un conjunto de cuatro caballos de los primeros 24 que contiene A1,A2 y A3. Pero esto es imposible en 5 carreras, ya que tienes al menos 4 ganadores diferentes que no han sido comparados, y por lo tanto estos cuatro caballos y los segundos puestos podrían ser todos A1,A2 o A3.

Por lo tanto, todos los casos conducen a una contradicción, por lo que la suposición de que 6 es suficiente, es insostenible.

Answer 2

$A_1$ $A_2$ $A_3$ $A_4$ $A_5$
$B_1$ $B_2$ $B_3$ $B_4$ $B_5$
$C_1$ $C_2$ $C_3$ $C_4$ $C_5$
$D_1$ $D_2$ $D_3$ $D_4$ $D_5$
$E_1$ $E_2$ $E_3$ $E_4$ $E_5$

Corremos $A,B,C,D,E$ grupos.- $5$ carreras.
Ahora dice que tenemos que determinar el $3$ rdido caballo más rápido. Así que si echamos un vistazo a la situación aquí, $A_1$ corre más rápido que todos. Así que ya tenemos el primero. Ahora tenemos que comparar $A_2$ y $A_3$ con $B_1$ y $B_2$ y $C_1$ .
Sé que pensarás que por qué estoy escribiendo todo esto, esta es la solución clásica. Pero la riguroso solución es también esto: En el inicio, tuvimos que comparar $35$ caballos. Y después de lo que parecía conveniente, (el $5$ carreras), $10$ caballos se quedaron para comparar.
Este tipo de preguntas sólo exigen una solución creativa No puede haber una prueba rigurosa para este tipo de preguntas. Es como pedir una solución única para $x+y+z=10$ . (Sólo un ejemplo).
Porque incluso en el $7$ método de carrera, primero asumimos el orden de las posiciones de llegada de los caballos. Así que hay muchos, muchos soluciones, pero no puede haber una solución menor que ésta.
Editar : En este tipo de preguntas, sólo tomamos el peor escenario posible, no que la persona pueda tener suerte. Si esto fuera cierto, la respuesta sería obviamente $0$ . Y supuse que usted sabía todo esto.

Answer 3

Solución: la respuesta es 9 carreras.

Paso 1: En primer lugar, agrupamos los caballos en grupos de 5 y hacemos correr a cada grupo en el hipódromo. Esto nos da 5 carreras.

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

Paso 2: se corren los 5 ganadores del nivel 1 (w11, w21, w31, w41, w51) y se asume que el orden de victoria de esta carrera es w11, w21, w31, w41, w51 (ESTA ES LA 6ª CARRERA)

Paso 3: PORQUE NECESITAMOS EL TOP 5 Y W51 HA LLEGADO A LA QUINTA POSICIÓN esa es la razón por la que no necesitamos considerar W52 W53 W54 W55 ahora tenemos

W11 W12 W13 W14 W15

W21 W22 W23 W24 W25

W31 W32 W33 W34 W35

W41 W42 W43 W44 W45

W51

Paso 4: porque necesitamos el top 5 entonces no necesitamos W25 W34 W35 W43 W44 W45

ahora tenemos

W11 W12 W13 W14 W15

W21 W22 W23 W24

W31 W32 W33

W41 W42

W51

Paso 5: ya se ha conseguido el top 1 que es W11(ganador de la 6ª carrera) los restantes son X W12 W13 W14 W15

W21 W22 W23 W24

W31 W32 W33

W41 W42

W51

Paso 6: candidatos a la 5ª posición: W51 W42 W33 W24 W15. 1 CARRERA PARA OBTENER LA 5ª POSICIÓN (esta es la 7ª carrera)

restantes son

X W12 W13 W14

W21 W22 W23

W31 W32

W41

Paso 7: candidatos a la 4ª posición: W41 W32 W23 W14. 1 carrera para conseguir la 4ª posición ((esta es la 8ª carrera)

X W12 W13

W21 W22

W31

Paso 8: Candidatos a la 2ª y 3ª posición: W12 W13 W21 W22 W31. 1 carrera para conseguir la 2ª y 3ª posición ((esta es la 9ª carrera)

Por lo tanto, la respuesta es 9 carreras.