Los ciclistas más rápidos (2)

[carroza]

Propongo una variante del problema propuesto por Jokin.

Tenemos un grupo de 100 ciclistas, y queremos determinar los 10 más rápidos, con su orden determinado. Solamente podemos poner a correr a 10 ciclistas cada vez. No tenemos registros de tiempos, pero sabemos que cada ciclista corre, en cualquier carrera, a la misma velocidad, y no hay empates. De cada carrera solamente podemos registrar el orden en que llegan los participantes.

¿Cuál es el minimo numero de carreras a realizar, y cómo hacemos para determinar, en su orden, los 10 mejores?

[Richard R Richard]

Hola carroza

Ocultar contenido

Mostrar solución Ocultar solución

Haces 10 carreras con 10 ciclistas diferentes,
la carrera 11 la realizas con los 10 ganadores de las 10 carreras previas, según el orden de llegada de esta carrera nombras al grupo de ciclistas que compitió con el ganador de la 11ava cómo a , al del segundo b, c,...j.
La carrera 12 la armas con el 2do a, 3ro a,4to a,5to a,1ro b,2do b,3ro b,1ro c,2do c,1ro d
Luego en esta carrera se pueden idéntificar 4 ciclistas rápidos más,
el tema es que surgen múltiples opciones en función del orden de llegada para armar la carrera 13 no me parece fácil expresar una lógica deductiva, solo me parece lógico que cualquiera fuesen esos resultados, en no más de 1 carrera adicional ya tienes a los 10 más rápidos , solo puedo estimar y no demostrar que son 14 carreras

Saludos

[carroza]

Hola. Gracias, Richard R Richard por participar

Expongo mi solución, usando la notación que propones

Ocultar contenido

Mostrar solución Ocultar solución

Los primeros pasos son, como Richard indica, realizar 10 carreras iniciales distribuyendo arbitrariamente a los 100 cicilistas, y realizar una carrera undécima con los 10 ganadores. Esto nos permite una identificación de los 100 ciclistas con la notación a,b,c ... i,j para las carreras iniciales, segun la clasificación de los ganadores en la carrera undecima, seguido por un numero que indica la posicion en la carrera inical. Así, la notación a5 corresponde a un ciclista que participó en la carrera inicial que ganó el que quedó primero de la undecima carrera, y obtuvo en esta carrera la posicion numero 5. La notación j3 corresponde a un corredor que participo en la carrera inicial que ganó el que quedó 10 en la undécima carrera, y quedó tercero en dicha carrera.

Con esta notación, a1 es el ciclista más rápido.

a2 (el segundo en la carrera inicial que ganó a1), y b1 (el ganador de su carrera inicial que quedó segundo tras a1 en la carrera undécima), son, probablemente, ciclistas muy rápidos, pero nadie nos asegura que estén entre los 10 ciclistas más rápidos.

La notacion propuesta sugiere que, tras las 11 carreras inicales, ordenamos a los ciclistas en una matriz 10x10. Miremos ahora a los ciclistas que están en la diagonal principal de la matriz: son a10, b9, c8, d7, e6, f5, g4, h3, i2, j1. Todos estos ciclistas tienen, al menos, 9 corredores más rápidos que ellos, y que estan situados por encima de la diagonal principal. Por ejemplo, para el ciclista e6, sabemos que e5, e4, e3, e2, e1, d1, c1, b1 y a1 son más rápidos que el. Por tanto, es posible (aunqe improbable) que e6 esté entre los 10 más rápidos. Asi que debemos considerar a todos los ciclistas de la diagonal principal, asi como los que estén por encima. Podemos olvidarnos de los ciclistas por debajo de la diagonal principal, tales como e7.

Organizamos la carrera numero 12 con los corredores de la diagonal principal. De estos corredores, solamente 1 podrá estar entre los 10 más veloces, ya que todos ellos tienen, al menos, 9 corredores más rapidos que ellos. Asi que seleccionamos al ganador de esa carrera, que denotamos por l1 (la duodécima letra l y la posicion 1).

La carrera numero 13 se organiza con los 9 corredores en la diagonal paralela a la principal a9, b8, c7, d6, e5, f4, g3, h2, i1, así como con el ganador de la carrera 12, l1. De esta carrera, denotada mor m, seleccionamos a los dos primeros m1, m2. Hay que notar que los corredores de la carrera 13 tienen, al menos 8 corredores más rapidos que ellos, situados por encima de su diagonal, así que solo un máximo de 2 pueden estar entre los 10 más veloces.

La carrerra numero 14 se organiza con los 8 corredores de la diagonal paralella a la principal a8, b7, c6, d5, e4, f3, g2, h1, y los dos primeros de la carrera 13, m1 y m2. De ellos seleccionamos a los tres mejores n1, n2, n3.

Siguiendo este procedimiento, llegamos a la carrera numero 20, que se organiza con a2 y b1, más los 8 mejores de la carrera numero 19. Los 9 mejores de esa carrera son, en este orden, los 9 más rápidos, y junto con a1, forman los 10 mejores.

Podeis ver que este procedimiento es fácilmente generalizable para $n^2$ ciclistas, organizados en carreras de n participantes. Son necesarias 2n carreras para obtener a los n mejores

Saludos