IMO 2002 - P1

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 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
Mensajes: 1302
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

IMO 2002 - P1

Mensaje sin leer por Gianni De Rico » Jue 13 Dic, 2018 12:06 pm

$S$ es el conjunto de todos los pares $(h,k)$ con $h,k$ enteros no negativos tales que $h+k<n$. Cada elemento de $S$ se colorea de rojo o azul, de forma que si $(h,k)$ es rojo y $h'\leqslant h$, $k'\leqslant k$, entonces $(h',k')$ también es rojo. Un subconjunto de $S$ de tipo $1$ tiene $n$ elementos azules con el primer miembro distinto y un subconjunto de $S$ de tipo $2$ tiene $n$ elementos azules con el segundo miembro distinto. Demostrar que hay la misma cantidad de subconjuntos de tipo $1$ que de tipo $2$.
Queda Elegantemente Demostrado

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 356
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: IMO 2002 - P1

Mensaje sin leer por Joacoini » Dom 22 Dic, 2019 1:03 am

Spoiler: mostrar
Si $a_i$ es la cantidad de pares azules con el primer elemento igual a $i$ y $b_i$ es la cantidad de pares azules con el segundo elemento igual a $i$.
Queremos demostrar que $a_1\times a_2\times ...\times a_n=b_1\times b_2\times ...\times b_n$

Si encontramos una biyección entre los $a_i$ y los $b_j$ tal que $a_i=b_j$ estamos.

Ubicamos los puntos en un eje cartesiano y agregamos los puntos $(-1,k)$ con $0\leq k\leq n$ y $(h,-1)$ con $0\leq h \leq n$ y los pintamos de rojo y agregamos los puntos $(h,k)$ tales que $h+k=n$ y $h$ y $k$ son enteros no negativos y los pintamos de azul.

La cantidad de puntos azules en la columna $i$ es $a_i+1$ y la cantidad de puntos azules en la fila $j$ es $b_j+1$, si la columna $i$ y la fila $j$ tienen la misma cantidad de puntos azules entonces $a_i=b_j$

Si un punto azul tiene a la izquierda un punto rojo decimos que ese punto azul esta vivo y si un punto azul tiene abajo un punto rojo decimos que es punto azul esta muerto (un punto puede estar vivo y muerto al mismo tiempo).

Si el punto $(i,j)$ esta vivo entonces la fila $j$ tiene $n+1-j-i$ puntos azules, si el punto $(i,j)$ esta muerto entonces la columna $i$ tiene $n+1-i-j$ puntos azules.

Si el punto $(i,j)$ esta vivo y el punto $(a,b)$ esta muerto y $i+j=a+b$ entonces la fila $j$ y la columna $a$ tienen la misma cantidad de puntos azules por lo que si hago una biyección entre puntos vivos y puntos muertos de tal manera que si dos puntos están conectados entonces están en la misma diagonal de las que mantienen la suma constante terminaríamos el problema por lo que basta ver que en una diagonal hay la misma cantidad de puntos vivos que de muertos.

Miremos una de estas diagonales de suma constante $0\leq k<n-1$, tiene en sus extremos puntos rojos y cada segmento de puntos azules arranca con un punto vivo (ya que el anterior en la diagonal es rojo por lo que el de abajo de ese también es rojo y este esta a la izquierda del azul) y termina con uno muerto (ya que el siguiente en la diagonal es rojo por lo que el de la izquierda de ese también es rojo y este esta a abajo del azul). Ignorando estos puntos vivos de los comienzos y muertos de los finales de los segmentos, si un punto esta vivo a la izquierda tiene un rojo y este rojo arriba tiene un azul que esta muerto y si un punto esta muerto abajo tiene un rojo y este rojo a la derecha tiene un azul que esta vivo y ya tendríamos una biyección entre puntos vivos y muertos en la diagonal.

La diagonal de suma constante $n-1$ es igual que las anteriores solo que no tienen si o si extremos rojos pero si un extremo es azul este punto estará vivo o muerto depende de que extremo sea por lo que seria lo mismo que si agregáramos un punto rojo como extremo.

La diagonal de suma constante $n$ también es lo mismo solo que no contiene puntos rojos por lo que pasamos directamente a la parte en la que ignoramos los extremos de los segmentos.



Ejemplo $n=5$
IMG_20191222_010406.jpg
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
NO HAY ANÁLISIS.

Responder