Problem (Combinatorics):
Let $m$ be a positive integer. Consider a $4 m \times 4 m$ 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 $m$ $4 \times 4$ 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 \mathrm{~m}$.

Fix such a configuration and let $m_{1}^{r}$ be the number of blue cells in rows containing exactly one such, let $m_{2}^{r}$ be the number of blue cells in rows containing exactly two such, and let $m_{3}^{r}$ be the number of blue cells in rows containing at least three such; the numbers $m_{1}^{c}, m_{2}^{c}$ and $m_{3}^{c}$ are defined similarly.

Begin by noticing that $m_{3}^{c} \geq m_{1}^{r}$ and, similarly, $m_{3}^{r} \geq m_{1}^{c}$. 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 \mathrm{~m}$. We will show that $m_{1}^{r}>m_{3}^{r}$ and $m_{1}^{c}>m_{3}^{c}$, and reach a contradiction by the preceding: $m_{1}^{r}>m_{3}^{r} \geq m_{1}^{c}>m_{3}^{c} \geq m_{1}^{r}$.

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 $8 m>6 m$ blue cells, which is a contradiction. Next, count rows to get $m_{1}^{r}+m_{2}^{r} / 2+m_{3}^{r} / 3 \geq 4 m$, and count blue cells to get $m_{1}^{r}+m_{2}^{r}+m_{3}^{r}<6 m$. Subtraction of the latter from the former multiplied by $3 / 2$ yields $m_{1}^{r}-m_{3}^{r}>m_{2}^{r} / 2 \geq 0$, and the conclusion follows.

To prove that a minimal configuration of blue cells satisfying the condition in the statement has cardinality at least $6 m$, consider a bipartite graph whose vertex parts are the rows and the columns of the array, respectively, a row and a column being joined by an edge if and only if the two cross at a blue cell. Clearly, the number of blue cells is equal to the number of edges of this graph, and the relationship condition in the statement reads: for every row $r$ and every column $c, \operatorname{deg} r+\operatorname{deg} c-\epsilon(r, c) \geq 2$, where $\epsilon(r, c)=2$ if $r$ and $c$ are joined by an edge, and $\epsilon(r, c)=0$ otherwise.

Notice that there are no empty rows/columns, so the graph has no isolated vertices. By the preceding, the cardinality of every connected component of the graph is at least 4 , so there are at most $2 \cdot 4 m / 4=2 m$ such and, consequently, the graph has at least $8 m-2 m=6 m$ edges. This completes the proof.

Final answer: $6m$