USAMO $1989$, Problema $2$
Problema $2$ de USAMO, $1989$: Los $20$ los miembros de un club de tenis local han programado exactamente $14$juegos de dos personas entre ellos, con cada miembro jugando en al menos un juego. Demuestre que dentro de este horario debe haber un conjunto de seis juegos con$12$ jugadores distintos.
Mi intento de solución: dado que hay$20$ jugadores, cada uno de los cuales ha jugado al menos un juego, el menor número de partidos que se deben organizar para acomodar a todos los jugadores sería $10$. Ahora,$4$quedan más partidos, que se pueden jugar como máximo $8$ de estos $20$jugadores. Así, al menos $12$ de los jugadores no pueden jugar más de $1$partido, y por lo tanto debe existir un conjunto de seis juegos con$12$jugadores distintos . Este, creo, será el principio rector de una prueba rigurosa.
Tengo las siguientes dudas nublando mi mente:
- ¿Mi razonamiento es sólido, es decir, libre de trampas?
- Si es correcto, ¿cómo enmarcar el razonamiento anterior en una demostración matemáticamente rigurosa?
Editar: Como lo señaló Ben en los comentarios, la declaración en cursiva no está justificada. Al parecer, pasé por alto muchas posibilidades al enmarcar esta prueba. Por lo tanto, me gustaría obtener algunas sugerencias para proceder con una prueba más razonable.
Respuestas
Me temo que hay una trampa. Si intentas probar que hay 6 juegos con 12 jugadores distintos entre los que han jugado exactamente 1 juego, fallarás. He aquí un ejemplo:
$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$
Si bien hay 6 juegos con 12 jugadores distintos, solo 5 juegos son entre los jugadores con exactamente un juego.
Así que aquí hay una pista: divida a los jugadores en dos grupos, los que tienen un juego y los que tienen más. Luego empareje jugadores con un juego, después empareje jugadores con un juego con jugadores con más y finalmente jugadores con más juegos.
EDITAR : Segundo enfoque
Si cada persona es vista como un vértice y cada juego como una ventaja, la pregunta pide demostrar que existe una coincidencia de tamaño al menos $6$. De manera equivalente, podemos probar que el tamaño de la coincidencia máxima$MM$ es de tamaño al menos $6$. Tenga en cuenta que una coincidencia máxima divide los vértices en dos conjuntos, uno con bordes en el$MM$, de tamaño $2\cdot |MM|$, y uno sin, de tamaño $20 - 2\cdot |MM|$por nuestro problema. Dado que todos los vértices son de grado al menos$1$, concluimos que hay al menos $20 - 2\cdot |MM|$bordes entre las dos particiones. Ahora,
$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$