Let be a positive integer. Consider a array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column. No cell is related to itself. Some cells are coloured blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.
Solution
The required minimum is 6 m and is achieved by a diagonal string of blocks of the form below (bullets mark centres of blue cells):
In particular, this configuration shows that the required minimum does not exceed 6 m.
We now show that any configuration of blue cells satisfying the condition in the statement has cardinality at least 6 m.
Fix such a configuration and let be the number of blue cells in rows containing exactly one such, let be the number of blue cells in rows containing exactly two such, and let be the number of blue cells in rows containing at least three such; the numbers and are defined similarly.
Begin by noticing that and, similarly, . Indeed, if a blue cell is alone in its row, respectively column, then there are at least two other blue cells in its column, respectively row, and the claim follows.
Suppose now, if possible, the total number of blue cells is less than 6 m. We will show that and , and reach a contradiction by the preceding: .
We prove the first inequality; the other one is dealt with similarly. To this end, notice that there are no empty rows - otherwise, each column would contain at least two blue cells, whence a total of at least blue cells, which is a contradiction. Next, count rows to get ,
and count blue cells to get , and the conclusion follows.