Cómo encontrar un orden total con comparaciones restringidas

Question

Existen $25$ caballos con diferentes velocidades. Mi objetivo es clasificar a todos ellos, utilizando sólo las carreras con $5$ caballos, y tomando clasificaciones parciales. ¿Cuántas carreras necesito, como mínimo, para completar mi tarea?

Como respuesta parcial, sé que es posible determinar la primera $3$ caballos con $7$ carreras, y, mediante una ligera generalización del algoritmo óptimo utilizado para encontrar las tres primeras, tener la clasificación completa en $20$ corre.

¿Es posible hacerlo mejor?

¿Y si tenemos $n$ caballos y quieren clasificarlos con carreras con $k$ ¿Caballos?

Answer 1

Sólo algunos límites inferior y superior.

Debe haber al menos $13$ carreras, porque necesitas $25!$ resultados posibles, todas las ordenaciones posibles de los $25$ caballos - y sólo hay $120=5!$ resultados en cada carrera. Desde $120^{12}<25!<120^{13},$ definitivamente no puede hacerlo en $12$ carreras.

Con $n$ caballos y razas de $k$ caballo, necesitas al menos: $$\left\lceil \log_{k!}(n!)\right\rceil$$ carreras.

(Cuando $k=2,$ este es el mínimo habitual de $\log_2(n!)\approx n\log_2 n-n$ comparaciones para realizar una ordenación completa de una lista.

Sin duda puede hacerse en $30$ razas, considerando las 30 líneas en el plano afín finito $\left(\mathbb Z/5\mathbb Z\right)^2.$ Es una exageración: todos los caballos corren contra todos los demás.