Problem 9.4. Tokens are placed in some of the cells of a table of size $8 \times 8$ such that:

(1) there is at least one token in any rectangle of size $2 \times 1$ and $1 \times 2$;

(2) there are two neighboring tokens in any rectangle of size $7 \times 1$ and $1 \times 7$. Find the minimum possible number of tokens.

Peter Boyvalenkov
9.4. On the figure below it is shown how 37 tokens can be placed in a way to satisfy (1) and (2). Now we shall prove that 37 is the desired number.

Consider the columns of the table of size $6 \times 6$ obtained by cutting outmost rows and columns of the given table. It follows from (1) that there are at least 3 tokens in every such column. If there are 3 tokens in a column $6 \times 1$ with no neighbors we have a contradiction to (2). Therefore in a column with 3 tokens they are placed either in the second, third and fifth cell or in the second,

![](https://cdn.mathpix.com/cropped/2024_06_03_f8ccd71b4db367e7c2a9g-173.jpg?height=490&width=621&top_left_y=1014&top_left_x=1045)
forth and fifth cell.

Denote by $k$ the number of columns with 3 tokens each. There are at least 4 tokens in each of the remaining $6-k$ columns of a table $6 \times 6$ and the two outmost columns of the initial table. Note that by (1) there are 5 tokens in each column of the initial table with 3 tokens in the table $6 \times 6$.

Suppose that there are two neighboring columns having 3 tokens each. Then there exists a rectangle $2 \times 1$ without a token, a contradiction. Therefore there are at most 3 columns having 3 tokens each, i.e. $k \leq 3$.

Consider the two rectangles $6 \times 1$ above and under the table $6 \times 6$. There are two cases:

Case 1. There are at most 3 tokens in one of these rectangles. Now, there are at least 5 tokens in the outmost columns of the initial table and therefore there are at least

$$
5 k+2 \cdot 5+4(6-k)+2(3-k)=40-k \geq 37
$$

tokens on the table.

Case 2. There are at least 4 tokens in both rectangles. Then the total number of tokens is at least

$$
5 k+4(8-k)+2(4-k)=40-k \geq 37
$$

Hence the desired number is 37 .