OFO 2019 Problema 6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Luli97

OFO - Mención-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 189
Registrado: Mar 16 Abr, 2013 8:23 pm
Medallas: 20
Nivel: Exolímpico

OFO 2019 Problema 6

Mensaje sin leer por 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.
3  
Avatar de Usuario
Luli97

OFO - Mención-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber
COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 189
Registrado: Mar 16 Abr, 2013 8:23 pm
Medallas: 20
Nivel: Exolímpico

Re: OFO 2019 Problema 6

Mensaje sin leer por 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.
1  
Avatar de Usuario
enigma1234

OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 OFO - Medalla de Oro-OFO 2024
Mensajes: 211
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 5
Nivel: Exolímpico

Re: OFO 2019 Problema 6

Mensaje sin leer por 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.

Avatar de Usuario
Male Arias

OFO - Mención-OFO 2016 OFO - Mención-OFO 2017 OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
COFFEE - Mención-COFFEE Ariel Zylber OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 28
Registrado: Vie 02 Oct, 2015 10:37 pm
Medallas: 9
Nivel: Exolímpico

Re: OFO 2019 Problema 6

Mensaje sin leer por Male 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.
2  
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: OFO 2019 Problema 6

Mensaje sin leer por 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.
5  
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: OFO 2019 Problema 6

Mensaje sin leer por 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.
Fallo inapelable.
Responder