9.5 On a board of $20 \times 15$ cells, some cells contain chips (no more than one chip per cell). Two chips are called "connected" if they are in the same column or row, and there are no other chips between them. What is the maximum number of chips that can be placed on the board so that each has no more than two "connected" chips?
Answer: 35.

Solution. Let $x_{1}, x_{2}, \ldots, x_{20}$ be the number of chips in rows $1,2, \ldots, 20$, and $y_{1}, y_{2}, \ldots, y_{15}$ be the number of chips in columns $1,2, \ldots, 15$. Then the total number of chips $S=x_{1}+x_{2}+\ldots+x_{20}=y_{1}+y_{2}+\ldots+y_{15}$. The number of "connectivities" $k \geq\left(2 x_{1}-2\right)+\left(2 x_{2}-2\right)+\ldots+\left(2 x_{20}-2\right)+\left(2 y_{1}-2\right)+\left(2 y_{2}-2\right)+\ldots+\left(2 y_{15}-2\right)=4 S-70$. Since each chip has no more than two connected chips, $2 S \geqslant k \geqslant 4 S-70$, which means $S \leqslant 35$. It is possible to place 35 chips on the board by filling the bottom row and the left column, and placing one more chip in the top right corner.

Comments. Only the correct answer - $\underline{0 \text { points. Correct justified estimate }-\underline{4} \text { points. }}$.

Correct example - 3 points.