XI Torneo de las ciudades Otoño 2018 Norte-Nivel Juvenil Problema 4

[Sandy]

Un tablero de $7\times7$ puede estar vacío o contener una pieza cuadrada invisible de $2\times2$ que cubra exactamente $4$ casillas del tablero. En cada casilla del tablero se puede colocar un chip que al encenderse indica si esa casilla está o no cubierta por la pieza. Todos los chips colocados sobre el tablero se encienden en el mismo instante. Determinar el menor número de chips que se necesita para saber con certeza si la pieza está presente en el tablero y, de estarlo, cuál es su ubicación exacta.

[Matiasmk]

Creo que la distribución mas eficiente es la siguiente
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
o=vacio
x=chip
A lo mejor hay una mejor demostracion que solo el separar los tal que ninguno tenga otro chip adyacente o en sus esquinas

[Matías V5]

Creo que la distribución mas eficiente es la siguiente
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
oxoxoxo
ooooooo
o=vacio
x=chip
A lo mejor hay una mejor demostracion que solo el separar los tal que ninguno tenga otro chip adyacente o en sus esquinas

Esa distribución no funciona: si se enciende el primer chip (el de arriba a la izquierda), hay $4$ posibles posiciones de la pieza cuadrada (los cuatro cuadrados de $2\times2$ que contienen la casilla donde está el chip). La idea es poner chips para poder determinar con certeza la posición de la pieza cuadrada.
Tené en cuenta además que como el problema pide hallar el mínimo número de chips, no solamente hay que encontrar una distribución que funcione sino también justificar por qué con menos chips es imposible cumplir el objetivo.

[Gianni De Rico]

Una pista

Spoiler: mostrar

Mirar este problema.
¿Cómo se relacionan los problemas? ¿Podemos llevarlos a los dos a un mismo tipo de enunciado?
¿La respuesta del anterior alcanza para saber en dónde está la pieza?

[Kechi]

Spoiler: mostrar

Notemos que en un tablero de $2\times3$ se necesitan al menos $2$ chips para poder determinar la ubicación exacta de la pieza invisible: con un solo chip o bien existe una posición de la pieza en la que no se prende y no podemos saber si está o no o bien se prende en dos posiciones distintas de la pieza y no podemos determinar la ubicación exacta; si no hay chips no podemos saber si está o no la pieza en el tablero.

Ahora dividamos el tablero de $7\times7$ en $8$ tableritos de $2\times3$ y la casilla central, como en la figura.

Tablerito.png

Esto nos asegura que necesitamos al menos $2\times8=16$ chips. Con el siguiente ejemplo vemos que son suficientes. $\bigstar$
$$
\begin{array}{|c|c|c|c|c|c|c|} \hline
~~~& & & & & &~~~ \\ \hline
& \blacksquare & \blacksquare & & \blacksquare & \blacksquare & \\ \hline
& \blacksquare & & \blacksquare & & \blacksquare & \\ \hline
& & \blacksquare & & \blacksquare & & \\ \hline
& \blacksquare & & \blacksquare & & \blacksquare & \\ \hline
& \blacksquare & \blacksquare & & \blacksquare & \blacksquare & \\ \hline
& & & & & \\ \hline
\end{array}
$$