2016 European Girls' Mathematical Olympiad

The required minimum is $6m$ and is achieved by a diagonal string of $m\times 4$ blocks of the form below (bullets mark centers of blue cells):

In particular, this configuration shows that the required minimum does not exceed $6m$.

We now show that any configuration of blue cells satisfying the condition in the statement has cardinality at least $6m$. 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\ge m_1^r$ and, similarly, $m_3^r\ge 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 $6m$. 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\ge m_1^c>m_3^c\ge 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 $8m>6m$ blue cells, which is a contradiction. Next, count rows to get $m_1^r+m_2^r/2+m_3^r/3\ge 4m$, and count blue cells to get $m_1^r+m_2^r+m_3^r<6m$. Subtraction of the latter from the former multiplied by $3/2$ yields $m_1^r-m_3^r>m_2^r/2\ge 0$, and the conclusion follows.

---

Alternative solution.

To prove that a minimal configuration of blue cells satisfying the condition in the statement has cardinality at least $6m$, 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$, $\mathrm{deg}r+\mathrm{deg}c-\epsilon (r,c)\ge 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 4m/4=2m$ such and, consequently, the graph has at least $8m-2m=6m$ edges. This completes the proof.