Problem: Let $m$ be a positive integer. Consider a $4m \times 4m$ array of square unit cells.
Two different cells are \emph{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 colored blue, such that every cell is
related to at least two blue cells.
Determine the minimum number of blue cells.

Solution: We'll prove that the answer is at least $6m$.
The construction is to take
diagonal copies of the matrix
\[ \begin{bmatrix}
  & 1 & 1 & 1 \\
  1 &&& \\
  1 &&& \\
  1 &&&
 \end{bmatrix}. \]

We present two proofs this is optimal.

\paragraph{Bipartite graph (Kevin Sun).}
Consider the bipartite subgraph
\[ H \subseteq K_{4m,4m} \]
with vertices being rows/columns,
and edges corresponding blue squares.

Assume for contradiction the are fewer than $6m$ edges.
Then there are at least $|V(H)|-|E(H)|=8m-6m=2m$
connected components in $H$,
so some connected component has at most three vertices.

We consider two cases:
\begin{itemize}
\ii Note that if there are any isolated vertices $v$
(connected components with no edges),
then it follows $H$ needs at least $8m$ edges,
because every vertex on the opposite shore from $v$ has
blue-degree at least $2$.

\ii Thus assume no isolated vertices exist.
On the other hand, every blue edge
is incident to at least two more blue edges,
so no connected component can have fewer than three edges.
As the connected components are bipartite,
it follows each connected component has at least four vertices,
which is impossible.
\end{itemize}

\paragraph{Brute force (mine).}
%I'll admit that unlike P1 and P2 (which I solved in about five minutes each),
%there is \emph{no way} I would have gotten this problem under time pressure:
%I had to stay up all night (despite a sore throat) to solve it.
%Also, this solution (linear programming after optimization)
%seems too silly to be true.
We prove that for a general $n \times n$ board,
a good configuration has at least $\frac32n$ blue squares.
Consider any minimal good configuration
with $k$ squares, and assume $k \le \frac 32 n$
(and we will prove $k \ge \frac32n$).
We observe that no column and row can be empty in a good
configuration with $k \le 2n$ squares.

Now, assume there are $x_i$ columns with exactly $i$ blue squares,
and $a_i$ rows with exactly $i$ blue squares (for $i = 1,\dots,n$.)
Permute the board to arrive at the following:
\[
 \begin{array}{r|c|c|c|}
  \multicolumn{1}{c}{\ }
   & \multicolumn{1}{c}{x_1\text{ cols}}
   & \multicolumn{1}{c}{x_2\text{ cols}}
   & \multicolumn{1}{c}{x_3+x_4+\dots+x_n\text{ cols}} \\\cline{2-4}
  a_1 \text{ rows} & 0 & 0 & a_1 \\ \cline{2-4}
  a_2 \text{ rows} & 0 & P & Q \\ \cline{2-4}
  &&& \\[1em]
  a_3+\dots+a_n & x_1 & R & S \\
  \text{rows} &&& \\[1em]\cline{2-4}
 \end{array}
\]
In each subgrid, the letter denotes the number of blue squares in that region.
Consequently, we have $P+Q=2a_2$, $P+R=2x_2$,
and $a_1+Q+S = 3x_3+4x_4+\dots+nx_n$.
We also know that $n = \sum a_i = \sum x_i$ and $k = \sum ia_i = \sum ix_i$.

Without loss of generality we assume that $a_1 \le x_1$.
Then, it would suffice to prove that
\[ \sum ia_i \ge \frac32 \sum a_i \iff a_1 \le a_2 + 3a_3 + 5a_4 + \dots. \]
We observe that
\begin{align*}
 0 &\le S = 3x_3 + \dots + nx_n - a_1 - Q \\
 &= \left( a_1+2a_2+\dots+na_n \right) - (x_1+2x_2) - (a_1-Q) \\
 \implies x_1 &\le (3a_3+4a_4+\dots+na_n) - (Q - 2a_2 + 2x_2) \\
 &= (3a_3+4a_4+\dots+na_n) - R \\
 &\le 3a_3 + 4a_4 + \dots + na_n \\
 &\le a_2 + 3a_3 + 5a_4 + \dots + (2n-3)a_n.
\end{align*}
Since we assumed $a_1 \le x_1$, we are done.
% http://aops.com/community/c6t30365f6h1226675_related_blue_squares_in_4m_by_4m_board