EGMO 2019 - P2

[Gianni De Rico]

Sea $n$ un entero positivo. En un tablero de $2n\times 2n$ casillas se colocan dominós de manera que cada casilla del tablero sea adyacente a exactamente una casilla cubierta por un dominó.
Para cada $n$, determinar la mayor cantidad de dominós que se pueden poner de esa manera.

Nota:
Un dominó es una ficha de $1\times 2$ o $2\times 1$ cuadrados unitarios. Los dominós son colocados en el tablero de manera que cada dominó cubre exactamente dos casillas del tablero y los dominós no se superponen. Decimos que dos casillas son adyacentes si son diferentes y tienen un lado en común.

[Turko Arias]

No hay mejor manera de empezar el año en el foro que al grito de "que viva la combinatoria"

Spoiler: mostrar

Definimos como un superdominó a la siguiente ficha, formada por exáctamente $8$ casillas del tablero:

superdomino.jpg

Ahora, reescribimos nuestro problema de la siguiente manera:

Sea $n$ un entero positivo. En un tablero de $2n\times 2n$ casillas se colocan superdominós de manera que cada casilla sea cubierta por exáctamente un superdominó, y de manera tal que ningún superdominó tenga más de tres casillas sobresaliendo del tablero.
Para cada $n$, determinar la mayor cantidad de superdominós que se pueden poner de esa manera.

Lo que hacemos ahora es colorear “coronas” del tablero de manera intercalada. Este es el ejemplo de cómo se colorea para $n=6$:

cason6.jpg

Notamos que no importa de qué manera coloquemos el superdominó, siempre va a cubrir exactamente $4$ casillas coloreadas.
Sea $R_n$ la cantidad de casillas que hay en el borde de un tablero de $2n \times 2n$. Es claro que $R_n=8n-4$. Por otro lado, notamos que si $n$ es par, la cantidad total de casillas pintadas va a ser
$$R_n+R_{n-2}+…+R_2=\sum_{i=1}^{\frac{n}{2}} (16i-4)=4 \sum_{i=1}^{\frac{n}{2}} (4i-1)=16 \sum_{i=1}^{\frac{n}{2}} i - 4 \sum_{i=1}^{\frac{n}{2}} 1=$$
$$16 \times \frac{\frac{n}{2} \left( \frac{n}{2}+1 \right) }{2}-4 \times \frac{n}{2}=2n(n+2)-2n=2n(n+1)$$

Y si $n$ es impar, la cantidad total de casillas pintadas va a ser
$$R_n+R_{n-2}+…+R_1=\sum_{i=0}^{\frac{n-1}{2}} (16i+4)=4 \sum_{i=0}^{\frac{n-1}{2}} (4i+1)=16 \sum_{i=0}^{\frac{n-1}{2}} i + 4 \sum_{i=0}^{\frac{n-1}{2}} 1=$$
$$16 \times \frac{\frac{n-1}{2} \left( \frac{n-1}{2}+1 \right) }{2}+4 \times \left( \frac{n-1}{2}+1 \right) =2(n-1)(n+1)+2n+2=2n(n+1)$$

Tenemos entonces que siempre la cantidad de casillas pintadas va a ser $2n(n+1)$, pero como cada superdominó cubre exáctamente cuatro casillas pintadas, podemos colocar como máximo $\frac{2n(n+1)}{4}=\frac{n(n+1)}{2}$ superdominós y, por ende, como máximo $\frac{n(n+1)}{2}$ dominós.

Para terminar, notemos que en cada corona $R_n$, podemos colocar exáctamente $\frac{R_n}{4}$ dominós, lo que nos asegura colocar en total $\frac{n(n+1)}{2}$. Mostramos un ejemplo para $n$ par y uno para $n$ impar, que se generalizan fácilmente:

Caso $n=4$:

coronade4.jpg

Caso $n=5$:

coronade5.jpg

Y mostramos como quedan ambos casos totalmente completos:

Caso $n=4$:

n4completo.jpg

Caso $n=5$:

n5completo.jpg

Luego, como mostramos que no podemos usar más de $\frac{n(n+1)}{2}$ dominós y dimos una manera de colocar esa cantidad, el problema queda terminado $\blacksquare$