Sea [math]m un entero positivo. Se considera un tablero de [math]4m\times 4m 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.
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)$.
