EGMO 2016 - Problema 3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
Mensajes: 801
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 5

EGMO 2016 - Problema 3

Mensaje sin leer por Emerson Soriano »

Sea [math] un entero positivo. Se considera un tablero de [math] casillas cuadradas. Dos casillas diferentes están relacionadas si pertenecen ya sea a la misma fila o a la misma columna. Ninguna casilla está relacionada con ella misma. Algunas casillas se colorean de azul de tal manera que cada casilla del tablero esté relacionada con al menos dos casillas azules. Determine el mínimo número de casillas azules.

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
Mensajes: 235
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 6
Nivel: 3

Re: EGMO 2016 - Problema 3

Mensaje sin leer por Sandy »

Solución:
Spoiler: mostrar
Sean $M$ la cantidad de casillas azules, $M_i$ la cantidad de casillas azules en la fila $i$, $_iM$ la cantidad de casillas azules en la columna $i$.
Notemos primero que, si hay una fila (o análogamente columna) sin ninguna casilla azul, luego cada columna debería tener al menos dos casillas azules, luego $M\geq 8m$.
A partir de ahora asumiremos que no hay filas ni columnas sin casillas azules.
Es claro que $\sum_{(i,j) azul} \frac{1}{M_i}+\frac{1}{_jM}=8m$, pues estamos sumando, para cada fila y columna, $\frac{1}{\text{Casillas Azules}}$ tantas veces como casillas azules haya.
Ahora, si para algún $(i,j)$ azul, $M_i=1$, entonces $_jM\geq 3 \Longrightarrow \frac{1}{M_i}+\frac{1}{_jM}\leq \frac{4}{3}$.
Caso contrario, $M_i,_jM\geq 2\Longrightarrow \frac{1}{M_i}+\frac{1}{_jM}\leq 1$.
Luego, siempre que $(i,j)$ sea azul, $\frac{1}{M_i}+\frac{1}{_jM}\leq \frac{4}{3}$.
Pero entonces $8m=\sum_{(i,j) azul} \frac{1}{M_i}+\frac{1}{_jM}\leq \frac{4}{3}M\Longrightarrow M\geq 6m$.
La construcción es poniendo en la diagonal principal cuadrados $4\times 4$ con la primera fila y la primera columna azules, excepto el $(1,1)$.
Fallo inapelable.

Responder