Mayor número de equipos con 16 victorias en un torneo

Question

Aquí hay un problema de una competencia de matemáticas, cuya solución requiere la enumeración de combinaciones. Estoy pidiendo confirmación de mi solución.

Veinte equipos están en un torneo de todos contra todos; cada equipo juega exactamente una vez contra cada otro equipo. ¿Cuál es la mayor cantidad de equipos que podrían tener al menos $16$ victorias?

Solución

Hay un total de ${}_{20}C_{2} = 190$ juegos jugados en el torneo; hay $190$ victorias y $190$ derrotas. Dado que $(12)(16) = 192$, menos de doce equipos en el torneo pueden ganar $16$ juegos. Si el resultado de un torneo incluye a un equipo $A$ con más de $16$ victorias, una de las cuales fue a expensas de otro equipo $B$, el resultado de otro torneo que es idéntico al primero excepto que el equipo $A$ pierde su juego con el equipo $B$ tendría al menos la misma cantidad de equipos con al menos $16$ victorias. Entonces, el resultado de un torneo con la mayor cantidad de equipos con al menos $16$ victorias es uno en el que ningún equipo tiene más de $16$ victorias.

Si el resultado de un torneo fuera tener exactamente ocho equipos con $16$ victorias, entre ellos tendrían un total de $24$ derrotas. Como hay otros doce equipos, cada equipo con $16$ victorias tendría que derrotar a otros cuatro equipos con $16$ victorias, pero esto daría lugar a $(4)(8) = 32$ derrotas entre ellos. Esto es una contradicción. Ocho equipos no pueden tener $16$ victorias.

El resultado de un torneo puede tener siete equipos con exactamente $16$ victorias. Cada uno de los equipos con $16$ victorias podría haber ganado todos los $13$ juegos contra los equipos con menos de $16$ victorias y la mitad de sus juegos entre esos equipos que terminaron con $16$ victorias. Cada uno de los equipos restantes puede ganar seis juegos entre ellos.

Answer 1

Su análisis es correcto

En general, con $N$ equipos jugando entre sí una vez, el mayor número $k$ de equipos que pueden ganar al menos $m$ juegos se puede encontrar considerando el número promedio que $k$ puede ganar entre ellos y el número que pueden ganar contra los demás, entonces $\dfrac{k-1}2+(N-k) \ge m$ lo que implica $$k \le 2N-2m-1$$

En su ejemplo con $N=20$ y $m=16$ esto da $k \le 40-32-1=7$ como usted encontró

Esto también muestra que el máximo siempre será impar