Problema 2: TOP 5

[Mórtimer]

Un club de tenis tiene $50$ miembros. Para descubrir a los mejores jugadores, el club organizó una serie de $35$ partidos uno contra uno de modo que cada miembro juegue al menos un partido.
Sabemos que la edad de Carlitos es el mayor entero positivo $k$ que cumple la siguiente propiedad: “sin importar cómo el club haya organizado los partidos, siempre hay un conjunto de $k$ partidos en los que juegan $2k$ miembros distintos”. Hallar la edad de Carlitos.

[Mórtimer]

Solución oficial:

Spoiler: mostrar

Veremos que el máximo tal $k$ es $k=15$, y por ende, Carlitos tiene $15$ años.

Probemos primero que para $k\ge 16$ hay torneos en donde la condición no vale.
Numeremos los miembros del $1$ al $50$ y consideremos el torneo donde:
A: El miembro $1$ juega contra $2$, $3$, ..., $22$ ($21$ partidos)
B: Los otros $28$ miembros juegan $23$ con $24$, $25$ con $26$ y así ($14$ partidos).
Si $k\ge 16$, consideremos por el absurdo $16$ de los $k$ partidos con $32$ miembros distintos. Al menos dos de los partidos deben ser del tipo A (pues hay solo $14$ de tipo B), y por ende ambos incluyen a $1$, por lo que no habrá $32$ miembros distintos. El absurdo provino de suponer que $k=16$ valía para todos los torneos, así que necesariamente $k\le 15$.

Probemos ahora que $k=15$ anda para todos los torneos.
Supogamos que sin pérdida de generalidad, $1$ y $2$ juegan entre ellos. Tenemos un conjunto de $t=1$ partidos con $2t$ jugadores distintos.
Veamos un proceso para ampliar un tal conjunto de $t$ partidos y $2t$ jugadores a uno de $t+1$ y $2(t+1)$ jugadores siempre que $t\le 14$.
Notar que hay $s\ge 50-2t$ jugadores fuera de estos partidos. Si dos de ellos juegan entre sí, entonces podríamos agregar este partido al conjunto y tendríamos $(t+1)$ partidos con $2(t+1)$ jugadores.
Entonces, supongamos por el absurdo que esto no pasa. Como cada jugador participa en un partido y no hay dos de estos $s$ en un mismo partido, hay al menos $s$ partidos "nuevos", además de los $t$ del conjunto. Entonces, como hay $35$ partidos
$$(50-2t) + t \le s+t\le \#\text{partidos}=35$$
Luego $50-t\le 35$, lo que implica $t\ge 15$. Pero esto contradice $t\le 14$, de modo que llegamos a un absurdo. Entonces, demostramos que siempre existen dos jugadores que juegan entre sí y el conjunto puede expandirse.
Repitiendo este procedimiento simempre que $t\le 14$, se llega a un conjunto de $14+1=15$ partidos con $30$ jugadores distintos, lo cual prueba lo deseado.

[usuario250]

Muy bueno. Algunas pistas

Spoiler: mostrar

1) separar los jugadores en:
A: los que jugaron más de un partido
B: los que jugaron exactamente un partido y ese partido fue contra uno de A
C: los que jugaron exactamente un partido y ese partido no fue contra uno de A

Spoiler: mostrar

ver que fue contra otro de C

2)Tomando el tamaño de A (a) y la cantidad de partidos entre jugadores de A (x, que puede, o no, ser 0):
A partir de a y x definir:
i) Tamaño de B y de C

Spoiler: mostrar

con esto ya tenemos la cantidad de partidos entre jugadores de C

ii) mínimo de jugadores de A que jugaron al menos un partido contra uno de B.

[Fran5]

Spoiler: mostrar

Sea $p_i$ los partidos jugados por el jugador $i$.

$\sum p_i = 70$

$\sum (p_i-1) = 20$.

Luego supongamos que el jugador $1$ jugó contra $2, \ldots, 22$ jugaron contra $1$ y que los restantes de a parejas. Claramente hay $21+\frac{50-22}{2}=35$ partidos y podemos elegir como mucho $15$ parejas .

Supongamos que existe alguna disposición con $k\leq 14$ parejas o menos. Luego tenemos como mucho $2k$ jugadores hasta acá y por lo tanto al menos $50-2k$ que necesariamente jugaron un partido contra alguno de estos. Esto implica que hay al menos $50-2k$ partidos extra y por lo tanto hay al menos $k+50-2k=50-k \geq 36$ partidos. Absurdo