Nacional 2006 - N1 P2

Problemas que aparecen en el Archivo de Enunciados.
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: 223
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Nacional 2006 - N1 P2

Mensaje sin leer por BrunZo » Dom 08 Sep, 2019 6:36 pm

En las casillas de un tablero de $8 \times 8$ hay que colocar fichas de modo que cada dos casillas consecutivas de una misma fila o de una misma columna haya al menos una que tenga una ficha y cada $7$ casillas consecutivas de una misma fila o de una misma columna haya al menos dos casillas consecutivas que tengan una ficha cada una. Determinar el número mínimo de fichas que hay que colocar en el tablero.
1  

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: 223
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Re: Nacional 2006 - N1 P2

Mensaje sin leer por BrunZo » Lun 23 Dic, 2019 1:34 pm

Esbozo de solución:
Spoiler: mostrar
Hay ejemplo con $37$:
$$\begin{array}{ |c|c|c|c|c|c|c|c| }
\hline
& \blacksquare & & \blacksquare & \blacksquare & & \blacksquare & \\ \hline
\blacksquare & & \blacksquare & \blacksquare & & \blacksquare & & \blacksquare \\ \hline
\blacksquare & \blacksquare & \blacksquare & & \blacksquare & & \blacksquare & \\ \hline
& \blacksquare & & \blacksquare & & \blacksquare & \blacksquare & \blacksquare \\ \hline
\blacksquare & & \blacksquare & & \blacksquare & \blacksquare & & \blacksquare \\ \hline
& \blacksquare & & \blacksquare & \blacksquare & & \blacksquare & \\ \hline
\blacksquare & & \blacksquare & \blacksquare & & \blacksquare & & \blacksquare \\ \hline
& \blacksquare & \blacksquare & & \blacksquare & & \blacksquare & \\ \hline
\hline
\end{array}$$

Para probar que no se puede con $36$ o menos, yo hice los siguientes pasos:
1. Asumir que se cumple con exactamente $36$ fichas, ya que si se cumpliese con menos, podés poner algunas fichas más donde quieras para llegar.
2. Partir el tablero en cuatro franjas horizontales de $2\times 8$ y probar que en cada franja hay, como mínimo, $9$ fichas.
3. Por Palomar, alguna de sus dos filas tiene, al menos $5$ fichas. Entonces, partir esta fila en cuatro dominós horizontales: Por Palomar, al menos un dominó tiene dos fichas en sus casillas.
4. Realizando un razonamiento análogo en las otras franjas, concluimos que hay cuatro dominós como los que obtuvimos en 3. con dos fichas. Además, hay sólo cuatro franjas verticales de estos dominós (están los dominós que ocupan las columnas $1$ y $2$, los que ocupan $3$ y $4$, etc.)
5. Concluir las siguientes dos cosas:
a. No puede haber dos dominós con dos fichas cada uno en la misma franja vertical.
b. No puede haber un dominó con dos fichas ni en la primera ni en la última franja vertical.
Luego, el absurdo se concluye por Palomar.

Responder