Rioplatense 2015 - N1 P6

[Matías V5]

$30$ equipos de fútbol jugaron entre ellos $N$ partidos de modo que:

1. No hay dos equipos que hayan jugado más de una vez entre sí.
2. Para cualquier grupo de $20$ equipos, hay al menos $10$ partidos en los que se enfrentaron dos equipos de dicho grupo.

Determinar el mínimo valor posible de $N$.

[Emerson Soriano]

Spoiler: mostrar

Diremos que un par de equipos es bueno si estos jugaron durante el torneo. Sean [math]X=\left \{ x_1,\: x_2,\: ... \:,\: x_{16} \right \}, [math]Y=\left \{ y_1,\: y_2,\: y_3,\: y_4 \right \} y [math]Z=\left \{ z_1,\: z_2,\: ... \:,\: z_{10} \right \} una partición de los [math]30 equipos en esos tres conjuntos disjuntos tal que todos los equipos de [math]X hayan jugado con todos los equipos de [math]Z, los equipos de [math]Z hayan jugado todos entre sí, los equipos de [math]Y hayan jugado todos entre sí y los equipos [math]x_1, [math]x_2, [math]x_3 hayan jugado entre sí. Notemos que en este caso hay [math]254 partidos jugados, pero al tomar los siguientes [math]20 equipos: [math]X\cup Y, podemos notar que no hay [math]10 partidos jugados entre ellos. Esto muestra que [math]N\geq 255.

Ahora probaremos que [math]255 es el menor valor que puede tomar [math]N. En efecto, sea [math]A un grupo cualquiera de [math]20 equipos y sea [math]B el conjunto de los equipos restantes. Notemos que hay a lo sumo [math]\binom{10}{2}=45 parejas de equipos buenos en [math]B. También notemos que hay a lo sumo [math]200 parejas de equipos buenos tal que uno de ellos esté en [math]A y el otro esté en [math]B. Esto muestra que hay al menos [math]255-45-200=10 parejas de equipos buenos que están exclusivamente en [math]A, que es lo que buscamos.

[Matías V5]

El problema se refiere al menor valor posible de [math]N para el cual existe un ejemplo de partidos con esas características.

[Mijail]

Solo una duda eso significa que la solucion de Emerson es incorrecta

[Gianni De Rico]

Lo que yo veo me parece correcto, puede ocurrir que la solución original sí fuera incorrecta pero que la haya editad luego del comentario de Matías

[Fedex]