A friend shared with me the following puzzle he encountered in a Chinese math competition:
In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, or on either diagonal) intersects at least one token. What is the smallest number of tokens required?
I'm not asking for a solution to this problem. I know the solution, I want to know the following:
Q: I found, by computation, the possible solutions all have a particular form (I list them below). Can we prove this? (In a way other than "I tried all the other possibilities".)
To illustrate the problem,
This arrangement doesn't work $$\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}$$ since e.g. there is the line $$\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}.$$
This arrangement works $$\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}$$ and uses $14$ tokens (which is not the minimum).
The solutions are (spoiler alert):
It requires $11$ tokens, realized by these 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}$
Part 1.
Prove that it is impossible to place $10$ tokens.
Let's try to build with $10$ tokens.
First, note that in each column/row must be at least $1$ token.
Lets call column with token in $1$st cell as column $a$; and row with token in $2$nd cell as column $b$.
Column $a$ and column $b$ must have at least $2$ tokens.
Column $a$ must have cells $1,6$ with tokens; column $b$ must have cells $2,7$ with tokens. (otherwise we'll need to have third column with multiple tokens: more then $10$ tokens at total).
If we want to use only $10$ tokens, then columns $a$ and $b$ need to be placed as $4$th and $5$th columns (otherwise red $5$-rows need to have at least $1$ token, that derives other column $a'$ or $b'$).
Then we have to place $6$ tokens in two $3\times 3$ green squares:
Each $3\times 3$ square must have $3$ tokens in different rows/columns. There are only $6$ such placements for each square. No one of them has tokens on "main" diagonals (see violet diagonals for the left square):
$10$ tokens are too few for such constructing.
Examples with $11$ tokens are shown by author of question.
Part 2. (thanks to Gerry Myerson for helpful comments)
Prove that there are only eight placements of $11$ tokens (all they are shown in the spoiler (see question text).
If we'll use $11$ tokens, then there are $3$ ways:
First two cases require to place "rich" columns on the center of $7\times 8$ table (as above), and we'll need to place $7$ tokens in wide green area (as in part $1$). It is impossible (some of four "main" diagonals will be empty).
Third case: there can be
$\qquad$- $3$ "long" columns (like $a$, $b$: with distance between tokens $=5$);
$\qquad$- or $2$ "long" and one "short" column (with distance $\le 4$ between tokens).
If one of columns is "short", then $2$ "long" columns must be on the center (as above), and some of four "main" diagonals will be empty again.
So, we'll consider third case with $3$ "long" columns. Then third case requires to place one of $2$-token columns on the center ($4$th or $5$th column). WLOG, let it is column $b$ as $4$th column. Other possibilities are symmetric to this one (left-right mirroring, up-down mirroring, and both).
There are only $9$ such variants (where we need to place $5$ tokens in the green area):
these $3$ cases are impossible:
$\quad$
$\quad$
these $3$ cases are impossible too:
$\quad$
$\quad$
this one is impossible (at least $3$rd or $5$th column must have two tokens):
and these $2$ cases are possible:
$\qquad$
These cases generate only $2$ possible placements (with column $b$ on the $4$th place). Applying symmetries, we'll have all $8$ possible placements (shown by author).