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


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