Mateclubes 2019 - Nivel 4 Problema 2

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla FOFO 9 años - Medalla Especial
Mensajes: 201
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Mateclubes 2019 - Nivel 4 Problema 2

Mensaje sin leer por BrunZo » Dom 01 Dic, 2019 11:11 am

Betty coloca fichas de dominó en un tablero de $8\times 9$ casillas. Las fichas no pueden sobresalir del tablero, ni pueden superponerse. ¿Cuál es la máxima cantidad de dominós que puede ubicar en el tablero si ya colocó las primeras seis fichas como se ve en le figura?
$$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
\quad\!& & & & & & & &\quad\! \\ \hline
& & & & & & \blacksquare & \blacksquare & \\ \hline
& & & & & \blacksquare & \blacksquare & & \\ \hline
& & & & \blacksquare & \blacksquare & & & \\ \hline
& & & \blacksquare & \blacksquare & & & & \\ \hline
& & \blacksquare & \blacksquare & & & & & \\ \hline
& \blacksquare & \blacksquare & & & & & & \\ \hline
& & & & & & & & \\ \hline
\end{array}$$

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla FOFO 9 años - Medalla Especial
Mensajes: 201
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Re: Mateclubes 2019 - Nivel 4 Problema 2

Mensaje sin leer por BrunZo » Dom 01 Dic, 2019 7:21 pm

Solución:
Spoiler: mostrar
Yo digo que como mucho se pueden poner $28$ dominós. Por ejemplo, de la siguiente forma:
Mateclubes II.PNG

Voy a probar que, no importa como coloquemos los dominós, siempre va a haber como mucho $28$ colocados. Para eso, coloreemos el tablero como ajedrez:
Mateclubes I.PNG
Veamos que las X nos dividen al tablero en dos partes con forma de "escalera" con $29$ casillas cada una, de las cuales $16$ son de un color y $13$ del otro (en la parte de la izquierda hay $16$ negras y $13$ blancas y en la de la derecha, al revés.)
Supongamos que primero se colocan los dominós que cubren alguna casilla con X (si hay alguno), y después el resto. (en verdad, el orden no cambia, así que podemos asumir esto tranquilamente.) Notemos que, luego de colocar estos (o no colocarlos), no se pueden colocar dominós que no estén enteramente contenidos en alguna de las dos escaleras, ya que si no estuviesen contenidos enteramente, una de sus partes estaría sobre una X y entonces el dominó ya habría sido puesto (dijimos que poníamos los que estaban sobre las X primero que nada). Es decir, que podemos considerar que tenemos ahora dos tableros separados.
Tomemos, por ejemplo, el tablero de la izquierda. Notemos que, como esta parte tiene a lo sumo $13$ casillas blancas (digo "a lo sumo" ya que si en la casilla con X inferior yo pusiese un dominó que cubra también la casilla de su izquierda, entonces habría $12$ casillas blancas disponibles), entonces, como cada dominó ocupa exactamente una casilla blanca, nunca podré colocar más de $13$ dominós. Un razonamiento análogo nos dice que nunca podremos colocar más de $13$ dominós en la parte derecha. Más aún, sabemos que los dominós colocados de antemano (los que están sobre alguna de las X), no pueden ser más de $2$, ya que si no habría dos que se superponen sobre la casilla con X, por lo que en total yo no pude haber usado más de $13+13+2=28$ dominós, que es lo que queríamos probar.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.

Responder