Nacional 2006 - N1 P2

Problemas que aparecen en el Archivo de Enunciados.
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 261
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
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-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 261
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
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