EGMO 2018 - P4

Avatar de Usuario
Violeta

OFO - Mención FOFO 7 años - Medalla Especial OFO - Medalla de Bronce
Mensajes: 389
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 3
Ubicación: Puerto Rico

EGMO 2018 - P4

Mensaje sin leer por Violeta » Vie 13 Abr, 2018 9:46 pm

Un domino es una ficha de $2 \times 1$ o de $1 \times 2$.

Sea $n\geq 3$ un entero. Se ponen dominos en un tablero $n \times n$ tal que cada domino ocupa exactamente dos casillas y los dominos no caen unos encimas de otros.

El valor de una fila o columna es la cantidad de dominos que ocupan por lo menos una casilla de esa fila o columna. Una configuracion esta balanceada si existe un entero $k \geq 1$ tal que cada fila y cada columna tiene valor de $k$.

Probar que para cada $n \geq 3$, existe una configuracion balanceada y encontrar la cantidad minima de dominos necesarios para tal configuracion.
Para todo [math], existen [math] primos en sucesión aritmética.

Avatar de Usuario
Emerson Soriano

OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 786
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 4

Re: EGMO 2018 - P4

Mensaje sin leer por Emerson Soriano » Sab 14 Abr, 2018 12:02 am

Spoiler: mostrar
Primero mostraremos una configuración balanceada para cada entero $n\geqslant 3$.

Cuando $n$ es múltiplo de $3$, tenemos las siguientes configuraciones balanceadas, donde $X$ representa al tablero $X$ de $3\times 3$.

Imagen

Además, notemos que en el tablero de $n\times n$ hay $\frac{n}{3}$ tableros $X$, y como cada tablero $X$ contiene dos dominós, entonces en el tablero de $n\times n$ hay $\frac{2n}{3}$ dominós.

Antes de continuar, enunciaremos y demostraremos el siguiente Lema.

Lema. Los números $4$, $5$, $8$, $9$, $10$ y todos los enteros positivos mayores o iguales que $12$ se pueden representar de la forma $4a+5b$, donde $a$ y $b$ son enteros no negativos.

Prueba. Diremos que un entero positivo que se puede representar de la forma $4a+5b$, con $a$, $b\geqslant 0$, es llamado representable. Es fácil verificar que los números $4$, $5$, $8$, $9$, $10$, $12$, $13$, $14$ y $15$ son representables.

Ahora, demostraremos por inducción sobre $n$ que todo entero $n\geqslant 15$ es representable. En efecto, supongamos que $n\geqslant 15$ es representable, entonces existen enteros no negativos $a$ y $b$ tales que $n=4a+5b$. Presentamos dos casos:

1) Si $a\geqslant 1$, entonces $n+1$ se puede expresar de la forma $n+1=4(a-1)+5(b+1)$, luego, como $a-1$ y $b+1$ son enteros no negativos, se concluye que $n+1$ es representable.

2) Si $a=0$, entonces $n=5b$, pero como $n\geqslant 15$, entonces $b\geqslant 3$. Notemos que $n+1=4\times 4+5(b-3)$, por lo tanto, $n+1$ es representable.

La inducción ha quedado completa y el Lema demostrado.$\blacksquare $


Continuando con el problema, veamos una configuración balanceada para $n=4$ y $n=5$:
Imagen

Supongamos que $n>3$ es representable, entonces por el Lema existen enteros no negativos $a$ y $b$ tales que $n=4a+5b$. Ahora, coloquemos dominós en un tablero de $n\times n$ de la siguiente manera:
Imagen

donde $Y$ representa al tablero $Y$ de $4\times 4$, $Z$ representa al tablero $Z$ de $5\times 5$, y además se han usado $a$ tableros $Y$ y $b$ tableros $Z$. Esta configuración es balanceada, pues las filas y las columnas tienen valor $3$. Como cada tablero $Y$ contiene $8$ dominós y cada tablero $Z$ contiene $10$ dominós, entonces en el ejemplo se han usado $8a+10b=2n$ dominós.

Vamos a demostrar que si $n>3$ es coprimo con $3$, entonces existe una configuración balanceada para $n$. En efecto, si $n>12$, entonces por el Lema tenemos que $n$ es representable, en consecuencia, existe una configuración balanceada para $n$. Si $n\leqslant 12$, entonces $n=4$, $5$, $7$, $8$, $10$ o $11$, pero $4$, $5$, $8$ y $10$ son representables, por lo tanto, existe una configuración balanceada para $n=4$, $5$, $8$ y $10$. Ahora, mostraremos una configuración balanceada para $n=7$ y $n=11$:
Imagen

donde $Y$ denota al tablero $Y$ de $4\times 4$. Es claro que ambas configuraciones son balanceadas, pues en ambos tableros las filas y las columnas tienen valor $3$.

Estos argumentos han demostrado que para cada $n\geqslant 3$ existe una configuración balanceada, además, notemos que si $n$ es múltiplo de $3$ se ha conseguido una configuración balanceada usando $\frac{2n}{3}$ dominós, y si $n$ es coprimo con $3$ se ha conseguido una configuración balanceada usando $2n$ dominós. Vamos a demostrar que estas son las cantidades mínimas de dominós que se necesitan para conseguir una configuración balanceada de $n$.

En efecto, diremos que un dominó \emph{toca} a una fila o una columna si cubre al menos una casilla de esta fila o columna.

Analicemos dos casos:

1) Cuando $n$ es múltiplo de $3$. Ya sabemos que existe una configuración balanceada para $n$, así que tomemos una de tales configuraciones y sea $k\geqslant 1$ el valor de cada fila y cada columna. Si para cada fila y cada columna contamos la cantidad de dominós que cubren al menos una de sus casillas obtenemos como resultado $2kn$. Note que cada dominó del tablero aparece exactamente tres veces en dicho conteo, pues siempre toca dos filas y una columna, o dos columnas y una fila. Por lo tanto, la cantidad exacta de dominós en el tablero es $\frac{2kn}{3}$. Como $k\geqslant 1$ y $\frac{2n}{3}$ es un entero positivo, entonces la cantidad de dominós en el tablero es mayor o igual que $\frac{2n}{3}$.

2) Cuando $n$ es coprimo con $3$. También sabemos que existe una configuración balanceada para los números $n$ de este caso, así que tomemos una de tales configuraciones y sea $k$ el valor de cada fila y cada columna. Por lo dicho en el inciso anterior, la cantidad exacta de dominós en el tablero es $\frac{2kn}{3}$, pero como $2n$ es coprimo con $3$, entonces $k$ es múltiplo de $3$, así, $\frac{k}{3}$ es un entero mayor o igual que $1$, por lo tanto, la cantidad de dominós en el tablero es mayor o igual que $2n$.

De esta manera se ha demostrado que existe una configuración balanceada para cada $n\geqslant 3$, y que si $n$ es múltiplo de $3$ se necesitan $\frac{2n}{3}$ dominós como mínimo para conseguir una configuración balanceada, y si $n$ es coprimo con $3$ se necesitan al menos $2n$ dominós.















Responder