OFO 2019 Problema 6

[Luli97]

Sea $q$ un entero positivo. En una heladería en la que se ofrecen $q^2+q+1$ gustos de helado distintos, un grupo de exolímpicos compró un cucurucho con $q+ 1$ bochas de distintos sabores cada uno, de manera que para cualquier par de gustos distintos haya exactamente una persona que los haya elegido a ambos. Demostrar que cualesquiera dos exolímpicos eligieron exactamente un gusto de helado en común.

[Luli97]

Solución Oficial

Spoiler: mostrar

Si hubiera dos exolímpicos que tuvieran $2$ o más gustos en común, no se cumpliría la afirmación del enunciado "para cualquier par de gustos distintos haya exactamente una persona que los haya elegido a ambos".
Ya sabemos entonces que dos exolímpicos tienen a lo sumo un gusto de helado en común, veamos que no pueden tener ninguno en común.
Notemos que la cantidad total de pares de helados es $\binom{q^2+q+1}{2}$ y la cantidad de pares de helado que tiene cada exolímpico es $\binom{q+1}{2}$, por lo tanto la cantidad de exolímpicos debe ser:

$\frac{\binom{q^2+q+1}{2}}{\binom{q+1}{2}}= q^2+q+1$

Tomamos uno de los exolímpicos (por comodidad lo llamaremos Buso) y veamos que todos tienen exactamente un gusto en común con él.
Vamos a contar la cantidad de pares de helados que se forman con uno de Buso y uno de otro exolímpico. Buso tiene $q+1$ gustos de helado distintos, cada uno de estos gusto forma pares con los otros $q^2$ gustos posibles, de esta manera se forman $q^2 \times (q+1)$. Como cada exolímpico que tenga un gusto en común con Buso tiene otros $q$ gustos, la cantidad de exolímpicos que necesitamos para cubrir todos los pares como los de arriba es

$\frac{q^2 \times (q+1)}{q} = q^2+q$

pero esta es la cantidad de exolímpicos que no son Buso. Por lo tanto, todos tienen exactamente un gusto en común con ella.
Como la elección de Buso como exolímpica es arbitraria, esto también pasa si elegimos cualquier otro exolímpico. Así, probamos que cada par de exolímpicos tiene exactamente un gusto en común.

[enigma1234]

Spoiler: mostrar

Supongamos que hay n olimpicos para cada olimpico como elige $q+1$ sabores,tendremos $\binom{q+1}{2}$ parejas de sabores que fueron elegidas por un olimpico como no hay repeticion entonces tendremos $n.\binom{q+1}{2}$ parejas de sabores elegidas por un olimpico pero por el dato esto es $\binom{q^2+q+1}{2}$ de esto $n=q^2+q+1$.
Si un olimpico eligio los sabores $1,2,...,q+1$ entonces un olimpico no puede elegir 2 sabores igual que este pues contradice el enunciado,entonces como un sabor $x$ es elegido por los olimpicos $x_1,x_2,..,x_m$ entonces estos solo tienen en comun al $x$ entonces hay $q.m$ sabores distintos con los que $x$ es escogido 2 veces,pero como $x$ es escogido con otro sabor exactamente una vez entonces $q.m=q^2+q\to m=q+1$ entonces cada sabor de $1,2,...,q+1$ es elegido por otros $q$ olimpicos y entre estos no hay repeticion, entonces hay $q^2+q$ olimpicos con exactamente 1 en comun y como hay $q^2+q+1$ olimpicos entonces este olimpico tiene exactamente un sabor en comun con los demas.

[malen.arias]

Spoiler: mostrar

Para cada gusto va a haber $q^2+q$ parejas (una con cada uno de los otros gustos) y por cada cucurucho en el que un gusto está, este abarca $q$ parejas (una con cada uno de los otros gustos del cucurucho), entonces cada gusto estará en exactamente $\frac{q^2+q}{q}=q+1$ cucuruchos.
Como cada pareja de gustos está una sola vez, ningún par de exolímpicos va a poder tener $2$ o más gustos en común. Entonces entre cada par de exolímpicos hay $0$ o $1$ gustos en común.
Supongamos que $A$ y $B$ tienen $0$ gustos en común:
En el cucurucho de $A$ está el gusto $a$, como no está en el de $B$, $a$ debe estar en algún cucurucho con cada uno de los $q+1$ gustos del helado de $B$, pero a la vez estos gustos no pueden estar en el mismo cucurucho entre ellos porque se repetiría una pareja del cucurucho de $B$, entonces $a$ debe estar en otros $q+1$ cucuruchos, entonces $a$ está en $q+2$ cucuruchos, pero cada gusto estaba en $q+1$ cucuruchos, absurdo.Entonces no existe un par de exolímpicos con $0$ gustos en común, por lo que sí o sí debe haber un gusto en común.

[Gianni De Rico]

Advertencia

Spoiler: mostrar

La heladería vende menta granizada

Solución

Spoiler: mostrar

Sean $1,2,\ldots ,q^2+q+1$ los gustos.
Supongamos que dos exolímpicos eligieron al menos dos gustos en común, digamos que eligieron los gustos $g_1,g_2,\ldots$ (con $g_i\in \{1,2,\ldots ,q^2+q+1\}\forall i$) entonces en particular ambos eligieron el par (no ordenado) $(g_1,g_2)$, absurdo pues cada par de gustos fue elegido por exactamente una persona. El absurdo provino de suponer que existen dos exolímpicos que eligieron al menos dos gustos en común, luego, todo par de exolímpicos eligió a lo sumo un gusto en común. (*)

Ahora, cada gusto está en $q^2+q=q(q+1)$ pares de gustos (pues se empareja con los $q^2+q$ gustos restantes), cada exolímpico que elige ese gusto los usa para $q$ pares (pues lo empareja con $q$ gustos restantes que eligió), por lo tanto, afirmo que cada gusto fue elegido por exactamente $q+1$ exolímpicos. En efecto, supongamos que hay un gusto elegido por a lo sumo $q$ exolímpicos, entonces aparece en a lo sumo $q^2<q^2+q$ pares (pues $q>0$ por ser un entero positivo), absurdo, luego todo gusto es elegido por al menos $q+1$ exolímpicos. Supongamos que hay un gusto elegido por al menos $q+2$ exolímpicos, luego, aparece en al menos $q(q+2)=q^2+2q>q^2+q$ pares (pues $q>0$ por ser un entero positivo), absurdo, luego, cada gusto es elegido por a lo sumo $q+1$ exolímpicos. Por lo tanto, cada gusto es elegido por exactamente $q+1$ exolímpicos.

Sea $n$ la cantidad de exolímpicos, consideremos un tablero de $n\times (q^2+q+1)$ donde la casilla $(i,j)$ está pintada si y sólo si el $i$-ésimo exolímpico eligió el $j$-ésimo gusto de helado.
Como cada exolímpico elige exactamente $q+1$ gustos de helado, el tablero tiene exactamente $n(q+1)$ casillas pintadas (contando por filas).
Como cada gusto es elegido por exactamente $q+1$ exolímpicos, el tablero tiene exactamente $(q^2+q+1)(q+1)$ casillas pintadas (contando por columnas).
Luego, $n(q+1)=(q^2+q+1)(q+1)$ pues ambos son la cantidad de casillas del tablero, y como $q+1>q>0$ por ser $q$ un entero positivo, tenemos $n=q^2+q+1$.

Digo que un gusto tapa a un par de personas si ambas personas eligieron ese gusto.
Como cada gusto es elegido por $q+1$ personas, entonces cada gusto tapa $\binom{q+1}{2}$ pares de personas, en total tapan $(q^2+q+1)\binom{q+1}{2}=\frac{(q^2+q+1)(q+1)q}{2}=\frac{(q^2+q+1)(q^2+q)}{2}=\binom{q^2+q+1}{2}$ pares de personas. Además, hay exactamente $\binom{q^2+q+1}{2}$ pares de personas.
Supongamos que hay al menos un par de personas que no es tapado por ningún gusto, entonces por Palomar, al menos un par de personas es tapado por al menos dos gustos (pues hay a lo sumo $\binom{q^2+q+1}{2}-1$ pares de personas que pueden ser tapados y hay $\binom{q^2+q+1}{2}$ pares de personas tapados), pero eso significa que esas personas eligieron al menos dos gustos en común, lo que es absurdo puesto que ya demostramos que todo par de personas elige a lo sumo un gusto en común. El absurdo provino de suponer que al menos un par de personas no es tapado por ningún gusto, luego, todo par de personas es tapado por al menos un gusto. Es decir, todo par de exolímpicos eligió al menos un gusto en común. (**)

De (*) y (**) tenemos que cualesquiera dos exolímpicos eligieron exactamente un gusto de helado en común.

[Sandy]

Spoiler: mostrar

Primero veamos que, si hay $q^2+q+1$ gustos, habrá $\frac{(q^2+q+1)(q^2+q)}{2}$ pares distintos de gustos. Dado que cada uno elige $q+1$ gustos, cada uno elige $\frac{(q+1)q}{2}$ pares. Como cada par de gustos lo elige un solo exolímpico, en total habrá $\frac{\frac{(q^2+q+1)(q^2+q)}{2}}{\frac{(q+1)q}{2}}=q^2+q+1$ exolímpicos.

Ahora, la cantidad de maneras de elegir dos bochas del mismo gusto será $\frac{(q+1)q}{2}$ por cada uno de los $q^2+q+1$ gustos, es decir que en total habrá $(q^2+q+1)\times \frac{(q+1)q}{2}=\frac{(q^2+q+1)(q^2+q)}{2}$ maneras de elegir dos bochas del mismo gusto.

Notemos ahora que la cantidad de pares de exolímpicos que se pueden armar es $\frac{(q^2+q+1)(q^2+q)}{2}$.

Por lo tanto, vemos que la cantidad de pares de exolímpicos posibles es la misma que la cantidad de pares de bochas del mismo gusto posibles, por lo que, en promedio, para cada par de exolímpicos habrá un par de bochas del mismo gusto.
Pero dos exolímpicos no pueden compartir dos gustos, ya que cada par de gustos lo elige exactamente un exolímpico.

Entonces, recapitulando:
Por cada par de exolímpicos hay en promedio un par de bochas del mismo gusto.
Ningún par de exolímpicos puede corresponderse con dos pares de bochas del mismo gusto (porque cada par de gustos se elige una sola vez)

Por lo tanto, quedamos con que cada par de exolímpicos tiene no más de un par de bochas iguales, y en promedio tiene un par de bochas iguales. Esto quiere decir que cada par de exolímpicos tendrá exactamente un par de bochas del mismo gusto, o, lo que es equivalente, cada par de exolímpicos comparte exactamente un gusto de helado, que es lo que queríamos demostrar.