Bloqueo de líneas de longitud $5$ en un $7 \times 8$ matriz; ¿cómo podemos saber que las soluciones tienen una forma específica?

Question

Un amigo compartió conmigo el siguiente rompecabezas que encontró en un concurso de matemáticas chino:

En un $7 \times 8$ matriz, colocamos fichas de manera que cualquier línea recta de longitud $5$ (horizontal, vertical o en cualquiera de las diagonales) se cruza con al menos una ficha. ¿Cuál es el menor número de fichas necesario?

No estoy pidiendo una solución a este problema. Conozco la solución, quiero saber lo siguiente:

Q : He encontrado, por cálculo, que las posibles soluciones tienen todas una forma particular (las enumero a continuación). ¿Podemos demostrarlo? (De una forma que no sea "he probado todas las demás posibilidades").

Para ilustrar el problema,

• Este arreglo no funciona $$\begin{array}{|ccccccc|} \hline \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \bullet & \cdot & \cdot \\ \bullet & \bullet & \bullet & \bullet & \cdot & \bullet & \bullet & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \hline \end{array}$$ ya que, por ejemplo, existe la línea $$\begin{array}{|ccccccc|} \hline \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \square & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \square & \bullet & \bullet & \cdot & \cdot \\ \bullet & \bullet & \bullet & \bullet & \square & \bullet & \bullet & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \square & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \square & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \hline \end{array}.$$

• Esta disposición funciona $$\begin{array}{|ccccccc|} \hline \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \hline \end{array}$$ y utiliza $14$ tokens (que no es el mínimo).

Las soluciones son ( alerta de spoiler ):

Requiere $11$ fichas, realizadas por estas matrices: $\begin{array}{cc} \begin{array}{|ccccccc|} \hline \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \hline \end{array} & \begin{array}{|ccccccc|} \hline \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \hline \end{array} \\ \begin{array}{|ccccccc|} \hline \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \hline \end{array} & \begin{array}{|ccccccc|} \hline \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \hline \end{array} \\ \begin{array}{|ccccccc|} \hline \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \hline \end{array} & \begin{array}{|ccccccc|} \hline \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \hline \end{array} \\ \begin{array}{|ccccccc|} \hline \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \hline \end{array} & \begin{array}{|ccccccc|} \hline \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\ \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\ \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\ \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\ \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\ \hline \end{array} \\ \end{array}$

Answer 1

Parte 1.

Demostrar que es imposible colocar $10$ fichas .

Intentemos construir con $10$ fichas.

En primer lugar, tenga en cuenta que en cada columna/fila debe haber al menos $1$ de la ficha.

Llamemos a la columna con el token en $1$ celda como columna $a$ y fila con ficha en $2$ nd celda como columna $b$ .

Columna $a$ y la columna $b$ debe tener al menos $2$ fichas.

Columna $a$ debe tener células $1,6$ con fichas; columna $b$ debe tener células $2,7$ con tokens. (Si no, necesitaremos tener una tercera columna con múltiples tokens: más entonces $10$ fichas en total).

Si queremos utilizar sólo $10$ tokens, y luego las columnas $a$ y $b$ deben colocarse como $4$ y $5$ columnas (de lo contrario, rojo $5$ -Las filas deben tener al menos $1$ token, que deriva otra columna $a'$ o $b'$ ).

Entonces tenemos que colocar $6$ fichas en dos $3\times 3$ cuadrados verdes:

Cada $3\times 3$ cuadrado debe tener $3$ fichas en diferentes filas/columnas. Sólo hay $6$ tales colocaciones para cada casilla. Ninguno de ellos tiene fichas en las diagonales "principales" (ver diagonales violetas para el cuadrado de la izquierda):

$10$ fichas son demasiado escasas para esa construcción.

Ejemplos con $11$ Las fichas son mostradas por el autor de la pregunta.

---

Segunda parte. (gracias a Gerry Myerson para los comentarios útiles)

Demostrar que sólo hay ocho colocaciones de $11$ fichas (todos ellos se muestran en el spoiler (ver texto de la pregunta).

Si usamos $11$ fichas, entonces hay $3$ formas:

• para utilizar columnas con $1,1,1,1,1,1,1,4$ fichas;
• para utilizar columnas con $1,1,1,1,1,1,2,3$ fichas;
• para utilizar columnas con $1,1,1,1,1,2,2,2$ fichas.

Los dos primeros casos requieren colocar columnas "ricas" en el centro de $7\times 8$ (como en el caso anterior), y tendremos que colocar $7$ fichas en la zona verde ancha (como en la parte $1$ ). Es imposible (algunas de las cuatro diagonales "principales" estarán vacías).

Tercer caso: puede haber
$\qquad$ - $3$ columnas "largas" (como $a$ , $b$ con distancia entre fichas $=5$ );
$\qquad$ - o $2$ "larga" y una columna "corta" (con distancia $\le 4$ entre fichas).
Si una de las columnas es "corta", entonces $2$ Las columnas "largas" deben estar en el centro (como en el caso anterior), y algunas de las cuatro diagonales "principales" volverán a estar vacías.

Así, consideraremos el tercer caso con $3$ columnas "largas". Entonces el tercer caso requiere colocar una de $2$ -columnas de fichas en el centro ( $4$ o $5$ columna). WLOG, que es la columna $b$ como $4$ columna. Otras posibilidades son simétricas a ésta (reflejo izquierda-derecha, reflejo arriba-abajo, y ambas).

Sólo hay $9$ tales variantes (donde tenemos que colocar $5$ fichas en la zona verde):

estos $3$ casos son imposibles:
$\quad$ $\quad$

estos $3$ casos también son imposibles:
$\quad$ $\quad$

este es imposible (al menos $3$ rd o $5$ La segunda columna debe tener dos fichas):

y estos $2$ casos son posibles:
$\qquad$

Estos casos sólo generan $2$ posibles colocaciones (con la columna $b$ en el $4$ lugar). Aplicando simetrías, tendremos todos $8$ posibles colocaciones (indicadas por el autor).