IMO 2001 - P3

Problemas que aparecen en el Archivo de Enunciados.
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:

IMO 2001 - P3

Mensaje sin leer por Gianni De Rico »

$21$ chicos y $21$ chicas participaron en una olimpíada matemática.
  • Cada participante resolvió a lo sumo $6$ problemas.
  • Para cada chico y para cada chica, hubo al menos un problema que fue resuelto por ambos.
Demostrar que hubo al menos un problema que fue resuelto por al menos $3$ chicos y al menos $3$ chicas.
1  
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
...

OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años
Mensajes: 7
Registrado: Vie 01 Oct, 2021 3:35 pm
Medallas: 3

Re: IMO 2001 - P3

Mensaje sin leer por ... »

No es mi solución, la vi en algún lado.
Spoiler: mostrar
Consideramos a uno de los chicos. Por el enunciado, resolvió como mucho 6 problemas, y con cada una de las chicas comparte al menos un problema resuelto en común. Por Palomar, es fácil ver que hay al menos 11 chicas que resolvieron un problema (de los resueltos por el chico) que fue resuelto por un mínimo de 3 chicas (no necesariamente el mismo). Si fuesen 10 (supongamos que el chico resolvió 6 problemas, y las 10 chicas resolvieron el sexto), entonces hay 11 tales que su problema resuelto lo comparten como mucho con una chica. Eso quiere decir que si las agrupamos en parejas nos quedan 5 grupos (uno para cada uno de los primeros 5 problemas) y una libre, que tiene que haber resuelto el sexto problema. Pero el sexto problema lo habían resuelto las otras 10, entonces, el mínimo es 11. Si reducimos el número de problemas resueltos por el chico obtenemos mínimos aun mayores, pero eso no nos interesa. Esta conclusión aplica para todas las chicas cada vez que consideremos a un chico particular, así como para todos los chicos cada vez que consideremos una chica particular. (1)
Ahora viene la parte interesante: pensemos un tablero de $21\times21$ casilleros, donde cada fila corresponda a un chico y cada columna a una chica. En la intersección entre una fila y una columna corresponde el problema que fue resuelto por ese chico y esa chica (puede ser más de uno). Si tal problema fue resuelto por tres o más chicos escribiremos una $A$ en ese casillero, y si fue resuelto por tres o más chicas, escribiremos una $B$. Ahora bien, por (1) sabemos que hay al menos $11$ $A$ en cada columna y $11$ $B$ en cada fila, es decir, un mínimo de $21\times11$ $A$ y $21\times11$ $B$ en el tablero. Por Palomar, existe al menos una casilla con una $A$ y una $B$ superpuestos, ya que de no ser así deberíamos tener $2\times11\times21$ casillas, o sea, el tablero debería ser como mínimo de $22\times21$.
Por lo tanto, queda demostrado que existe al menos un problema resuelto por $3$ o más chicas y $3$ o más chicos.
Responder