Nacional 2001 N2 P3

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

OFO - Medalla de Bronce OFO - Jurado
Mensajes: 90
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 4
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Nacional 2001 N2 P3

Mensaje sin leer por AgusBarreto » Dom 02 Nov, 2014 3:31 pm

Carlos coloreó cada casilla de un tablero de [math] x [math] con uno de cuatro colores de modo que haya exactamente [math] casillas de cada color en cada fila y en cada columna. Demostrar que en el tablero hay dos filas y dos columnas tales que las cuatro casillas de las intersecciones de esas filas y columnas son una de cada color.

Avatar de Usuario
BrunoDS

OFO - Medalla de Plata
Mensajes: 63
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 1
Nivel: 2
Ubicación: Martínez

Re: Nacional 2001 N2 P3

Mensaje sin leer por BrunoDS » Vie 12 Ene, 2018 10:42 am

Spoiler: mostrar
Supongamos que no existen dos filas y dos columnas tales que sus cuatro intersecciones sean de distinto color.

Dada una fila, contaremos los pares de casillas de distinto color. Hay $\binom{4}{2}=6$ formas de elegir $2$ de los $4$ colores y hay $25$ casillas de cada color por fila. Luego, hay por fila: $6\times 25\times 25=3750$ pares de casillas de distinto color y hay entre las $100$ filas: $100\times3750=375000$ pares.

Ahora, cada par de casillas que contamos se encuentra sobre un par de columnas. En total hay $\binom{100}{2}=4950$ pares de columnas, por lo que, por el principio del palomar, hay un par de columnas con al menos:
$\frac{375000}{4950}=75,7575...>75$
$75$ pares de casillas de distinto color.

Ahora, miremos este par de columnas con más de $75$ pares de casillas en la misma fila de distinto color.

Sean $A$, $B$, $C$ y $D$ los cuatro colores. Sin pérdida de generalidad, supongamos que un par está pintado $A,B$. Como hay a lo sumo $50 A$ entre las dos columnas y hay más de $75$ pares de casillas, entonces habrá un par que no esté pintado con el color $A$. Este par debe estar pintado $B,C$ (sin pérdida de generalidad), ya que debe compartir un color con $A,B$. Análogamente, hay un par que no está pintado con el color $B$, por lo que debe ser $A,C$, ya que debe compartir un color con $A,B$ y con $B,C$.

Luego, como hay un par $A,B$, un par $A,C$ y un par $B,C$, no puede haber ningún par con $D$. Como hay más de $75$ pares, hay más de $150$ casillas, pero en total hay a lo sumo $50A+50B+50C=150$ casillas (ya que no puede haber un $D$). Luego, llegamos a una contradicción, por lo que existen dos filas y dos columnas tales que las cuatro casillas de las intersecciones de esas filas y columnas son una de cada color.

$B > \frac{1}{n} \sum\limits_{i=1}^n x_i$

Responder