Problema 5 de la Fase Local de la Olimpiada Española de Matemáticas 2024 (viernes) Se dirige a una edad de: 16-17 años
En una fiesta hay 100 personas. Cada par de personas son o bien amigos o bien enemigos (una y solo una de las dos cosas).
Se cumple la siguiente propiedad: si A y B son enemigos y B y C son enemigos, entonces A y C son amigos.
Demostrar que hay dos personas X e Y que cumplen simultáneamente estas condiciones:
X tiene el mismo número de enemigos que Y .
X e Y son amigos.
Solución:
Si partimos de la idea de que no existe ese par de personas, que llamaremos la hipótesis inicial, puesto que todo el mundo tiene una cierta cantidad de enemigos, ordenemos a las personas por número de enemigos.
El que más número de enemigos tiene, al que llamaremos el repelente, tendrá un cierto número x de enemigos, y no ninguna persona en la fiesta con más enemigos que él.
Es evidente que x es mayor que 2, ya que necesariamente en caso de que x sea 2, habrá dos personas que tengan la misma cantidad de enemigos, y que serán amigos entre ellos (ya que habrá muchas personas con 0 enemigos, o bien con 1 enemigo o bien con 2 enemigos).
Ahora, tomemos a todos sus x enemigos (que serán más de 2), y ordenémoslos según el número de enemigos. Puesto que todos son enemigos del repelente, son amigos entre sí, por lo que no puede haber dos amigos con la misma cantidad de enemigos, según la hipótesis inicial.
Eso quiere decir que habrá x personas con diferente número de enemigos, y sólo puede haber un máximo de x enemigos por persona, por lo que habrá un repelente2, que también tendrá x enemigos.
Entonces, con los x enemigos de repelente2 podemos hacer lo mismo, ordenarlos por número de enemigos, y de nuevo habrá exactamente uno con cada posible cantidad de enemigos.
Además, tendremos que los enemigos de repelente2 no pueden ser también enemigos de repelente, ya que eso les obligaría a ser amigos.
En particular, hay un enemigo de repelente con exactamente un enemigo (amigo de todos los demás), y un enemigo de repelente2 con exactamente un enemigo, por lo que entre ellos serán amigos.
Eso genera una contradicción, es decir, que sí que se da siempre la propiedad propuesta.
