
Problem 4. A $5 \times 100$ table is divided into 500 unit square cells, where $n$ of them are coloured black and the rest are coloured white. Two unit square cells are called adjacent if they share a common side. Each of the unit square cells has at most two adjacent black unit square cells. Find the largest possible value of $n$.


Solution. 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_fe2687448771fc19bd4eg-5.jpg?height=320&width=493&top_left_y=629&top_left_x=816)

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_fe2687448771fc19bd4eg-5.jpg?height=317&width=737&top_left_y=1132&top_left_x=694)

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$.
