In a $5 \times 100$ table we have coloured black $n$ of its cells. Each of the 500 cells has at most two adjacent (by side) cells coloured black. Find the largest possible value of $n$.

In a $5 \times 100$ table we have coloured black $n$ of its cells. Each of the 500 cells has at most two adjacent (by side) cells coloured black. Find the largest possible value of $n$.
If we colour all the cells along all edges of the board together with the entire middle row except the second and the last-but-one cell, the condition is satisfied and there are 302 black cells. The figure below exhibits this colouring for the $5 \times 8$ case.

![](https://cdn.mathpix.com/cropped/2024_06_05_c9c11143859c7d8820d7g-20.jpg?height=320&width=494&top_left_y=554&top_left_x=787)

We can cover the table by one fragment like the first one on the figure below, 24 fragments like the middle one, and one fragment like the third one.

![](https://cdn.mathpix.com/cropped/2024_06_05_c9c11143859c7d8820d7g-20.jpg?height=320&width=740&top_left_y=1071&top_left_x=658)

In each fragment, among the cells with the same letter, there are at most two coloured black, so the total number of coloured cells is at most $(5+24 \cdot 6+1) \cdot 2+2=302$.

Alternative Solution by PSC. Consider the cells adjacent to all cells of the second and fourth row. Counting multiplicity, each cell in the first and fifth row is counted once, each cell in the third row twice, while each cell in the second and fourth row is also counted twice apart from their first and last cells which are counted only once.

So there are 204 cells counted once and 296 cells counted twice. Those cells contain, counting multiplicity, at most 400 black cells. Suppose $a$ of the cells have multiplicity one and $b$ of them have multiplicity 2. Then $a+2 b \leqslant 400$ and $a \leqslant 204$. Thus

$$
2 a+2 b \leqslant 400+a \leqslant 604
$$

and so $a+b \leqslant 302$ as required.

Remark by PSC. The alternative solution shows that if we have equality, then all cells in the perimeter of the table except perhaps the two cells of the third row must be coloured black. No other cell in the second or fourth row can be coloured black as this will give a cell in the first or fifth row with at least three neighbouring black cells. For similar reasons we cannot colour black the second and last-but-one cell of the third row. So we must colour black all other cells of the third row and therefore the colouring is unique.