I am guessing the minimum to be $8m$. Can someone verify this? (Construction for $8m$ is kind of trivial)

I can confirm the minimum is not $8m$. I'm fairly certain that the real answer should be $6m$, which you can achieve by making a construction for $m = 1$ and then repeating it diagonally.

Wait, what is the construction for $m=1$ which gives $6$? Sorry, if this is trivial

You have a $4\times4$ square, and colour in blue the left column and the line from the bottom, without the square from the buttom-left. You'll see that this satisfies.

I think this following works:

Here is my terrible solution. 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 to silly to be true. The answer is $6m$ as mentioned above, achieved by taking diagonal copies of the $4 \times 4$ matrix \[ \begin{bmatrix} & 1 & 1 & 1 \\ 1 &&& \\ 1 &&& \\ 1 &&& \end{bmatrix}. \] Now we prove the result that for a general $n \times n$ board, a good configuration has at least $\frac32n$ blue squares. Now consider any minimal good configuration (thus with $\frac32 n$ blue squares). We prove it has $k \ge \frac32n$ blue squares, implying the conclusion. 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$, done. EDIT 4/13: Originally I tried to prove one could reduce to the case where $a_4 = a_5 = \dots = 0$, but pi37 correctly points out this is not easy to do. So here is a solution with $2n+4$ variables instead of the earlier $11$.

We'll prove that the answer is at least $6m$. If some row or column is empty, we clearly need at least $8m$ blue squares. Otherwise. consider the bipartite graph with vertices being rows/columns, and edges the blue squares. Since every row or column has at least one blue square, every connected component has at least $1$ edge. By the condition, each edge is adjacent to at least two other edges, so each connected component has at least $3$ edges. Since triangles are not bipartite, the number of vertices in such a connected component is at least $4$. In a connected component with $V$ vertices, and $E$ edges, $E \ge V-1 \ge \frac{V-1}{V} \cdot V \ge \frac{3}{4}V$. Then Summing over all connected components gets us the desired result.

For a set $S$, let $s$ denote the number of elements it has for simplicity. If a row or column is empty, then we are obviously done (we actually will need $8m$ squares in this case!) Let $R, C$ denote the sets of rows, columns that have exactly one blue square. Let $R'$ denote the rows that some blue square in the columns in $C$ is in. Define $C'$ similarly. Note that $R \cap R' = C \cap C' = \emptyset$. Otherwise, there will be some square that is in a column with one blue square and a row with one blue square, so obviously this is bad. I claim that for all rows in $R'$, they have at least $3$ blue squares. This is clear, as that row has a blue square who is the only square in its column, so it must have 2 other blue squares in its row. Given these claims, we simply count everything. Let's first count in the rows. The rows in $R$ contribute $r$ blue squares. The rows in neither $R$ not $R'$ contribute $2(4m - r - r')$ squares, since they don't by $1$ square in them by definition, and don't have 0 as assumed. The rows in $R'$ contribute at least $3r'$ squares, as each row has at least 3 squares. Note that they also must contribute at least $c$ squares, as all the squares that are in the columns $C$ lie in the rows $R'$. This means that among the rows, we need at least $r + 2(4m - r - r') + \max(3r', c) = \max(8m - r + r', 8m - r - 2r' + c).$ Among the columns, we get the similar $\max(8m - c + c', 8m - c - 2c' + r).$ I claim that at least one of these 4 quantities mentioned is at least $6m$. Assume all are less than $6m$. Then \[ r - r' > 2m, r + 2r' - c > 2m, c - c' > 2m, c + 2c' - r > 2m.\]Adding the second and fourth inequalities gives that $r' + c' > 2m.$ Adding the first and third equations gives that $r + c > 4m + (r' + c') > 6m.$ So $r + c + r' + c' > 8m$, and obviously contradiction because $r' + r \le 4m, c + c' \le 4m$ by disjointness of $R, R'$ and $C, C'.$ For the construction, use v_Enhance's construction. This can also be motivated because the equality cases in the above inequalities are $c = 3r' = r = 3c' = 3m.$

Suppose we let squares be associated with themselves, then if the grid is $3n\times 3n$ do we get the minimum number of blue squares is $4n$? I think we do, with the same construction as pi37's, only changing $3\times1$ and $1\times 3$ with $2\times1$ and $1\times 2$. (I think the solution by Ksun48 does the trick) Does anyone know if this version of the problem has been asked before)?

The answer is $6m$ with the construction given in pi37's post. Think of the grid as $K_{4m,4m}$, we want to pick a set $S$ of edges such that any edge is adjacent to at least $2$ edges in $S$. Consider the graph $G$ induced by the set $S$. Let the bipartition of $K_{4m,4m}$ be $(R,C)$ corresponding to rows and columns. We can make some observations: 1. There can be no vertex of degree $0$ in $G$ Suppose a vertex in $r \in R$ has degree $0$. Then for any $c \in C$, the edge $\{r,c\}$ is incident to at least $2$ edges in $S$, so $c$ has degree at least $2$. This holds for any $c \in C$ so we have at least $8m$ edges. 2. Every vertex of degree $1$ is connected to a vertex of degree at least $3$ Suppose $r \in R$ is joined to $c \in C$ such that $\deg(c)\le 2$. Then if we pick the edge $\{r,c\}$, it is only adjacent to at most one other edge incident with $c$ since edges aren't considered adjacent to themselves. Using these observations, if we consider the vertices of degree $1$ and their neighbours, the average degree among these vertices is at least $\frac{3}{2}$, with equality iff there are a bunch of vertices of degree $3$ connected to $3$ vertices of degree $1$. The average degree among the remaining vertices is at least $2$, hence the average degree in $G$ is at least $\frac{3}{2}$, so there are at least $\frac{3}{4}(8m) = 6m$ edges in $S$, as desired. Note: the construction follows directly from the equality case given @Gamamal If we just change observation 2 to "every vertex of degree $1$ is connected to a vertex of degree at least $2$" with identical reasoning, then we get the average degree is at least $\frac{4}{3}$, which gives $4m$ for $K_{3m,3m}$, and the construction is as you stated.

The answer is $6m$, which can be obtained by placing copies of the $4 \times 4$ matrix \[ \begin{bmatrix} & 1 & 1 & 1 \\ 1 &&& \\ 1 &&& \\ 1 &&& \end{bmatrix} \]down the diagonal of the $4m \times 4m$ array. Now, suppose by way of contradiction that there exists a valid array with less than $6m$ blue cells. If there is a column with no blue cells, then each row must contain at least $2$ blue cells, yielding at least $8m$ blue cells in the array, absurd. Hence, each column contains at least $1$ blue cell. Call a blue cell a single, double, or multi if it belongs to a row with $1, 2$, or $\ge 3$ blue cells, respectively. Let $a, b, c$ denote the number of rows with one single, two doubles, several multis, respectively, so that $a + b + c = 4m$ and $a + 2b + 3c < 6m. \; (\star)$ For a column with $n$ blue cells, define the redundancy of the column to be $n - 1.$ Denote by $\mathcal{R}$ the total redundancy of the array, i.e. the sum of the redundancies of each column. Note that $\mathcal{R} < 6m - 4m = 2m.$ We claim that for a column $\mathcal{C}$ with $\alpha$ singles, $\beta$ doubles, and $\gamma$ multis, the redundancy of $\mathcal{C}$ is at least $\tfrac{2\alpha}{3}+ \tfrac{\beta}{2}.$ Indeed, we must show that $\tfrac{\alpha}{3} + \tfrac{\beta}{2} + \gamma \ge 1.$ If $\gamma \ge 1$, this inequality holds trivially. Otherwise, $\gamma = 0$, and by considering the number of cells related to the blue cells in $\mathcal{C}$, it's easy to see that $\mathcal{C}$ must have at least two doubles or at least three blue cells. In either case, the required inequality holds, as desired. Summing over all columns, it follows that $\tfrac{2a}{3} + b \le \mathcal{R} < 2m.$ Multiplying this inequality by $3$ and summing with $(\star)$, we obtain $3a + 5b + 3c < 12m.$ But then $a + b + c = 4m$ yields a contradiction, as desired. $\square$

More generally, for an $n \times n$ grid where there must be at least $k$ related cells, the minimum number is bounded by (if I'm not mistaken): $$k = 2x \rightarrow \frac{x^2+2x}{x+1} \cdot n, 2x+2 \mid n$$$$k = 2x+1 \rightarrow \frac{2x^2+6x+3}{2x+3} \cdot n, 4x+6 \mid n$$

Consider a set $\mathbb{R}$ of rows and $\mathbb{C}$ of columns. Define a combinatorial rectangle to be the intersection of $\mathbb{R}$ and $\mathbb{C}$. We identify this combinatorial rectangle as the ordered pair $(\mathbb{R}, \mathbb{C})$. If, for some pair of blue cells $(c_i, c_j)$, there exists a sequence $\{c_{i_0}, c_{i_1}, \dots, c_{i_n}\}$ of blue cells where $c_{i_0} = c_i$ and $c_{i_n} = c_j$ such that $c_{i_q}$ and $c_{i_{q+1}}$ are relatives for all $q \in \{0,\dots,n-1\}$, then call $c_i$ and $c_j$ $\textit{cousins}$. Note that the cousin relation is transitive. Call a set of blue cells a component if all of the cells are cousins with each other. Call a set of blue cells a maximal component if none of the blue cells are cousins with any cells outside of the component. Note that the set of blue cells on a grid satisfying the problem condition can be uniquely partitioned into maximal components $C_1, \dots, C_k$. Let $\mathbb{R}_i$ and $\mathbb{C}_i$ be the set of rows and columns, respectively, which cells in component $C_i$ are contained in. Let $R_i$ be the combinatorial rectangle $(\mathbb{R}_i, \mathbb{C}_i)$. Lemma 1: The $\mathbb{R}_i$ are disjoint (and likewise for the $\mathbb{C}_i$). Proof: Suppose row $r$ is in both $\mathbb{R}_i$ and $\mathbb{R}_j$. Then there is some cell $c_1 \in C_i$ and some $c_2 \in C_j$ such that both $c_1$ and $c_2$ are in row $r$; then $c_1$ and $c_2$ are relatives in different maximal components, contradicting the definition of a maximal component. Lemma 2: A combinatorial rectangle $(\mathbb{R}, \mathbb{C})$ associated with a component $C$ has at least $|\mathbb{R}| + |\mathbb{C}| - 1$ blue cells. Proof: Consider the following procedure: first, initialize an empty set $S$ and pick an arbitrary blue cell in $C$. Initialize variables $r = c = 1$, which count the number of rows and columns represented by cells in $S$. In each step, while some cell in $S$ has a relative in $C$ that is not in $S$, add the relative to $S$ and update $r$ or $c$ (or neither) accordingly. Note that when the procedure terminates, $C = S$, and $r = |\mathbb{R}|$ and $c=|\mathbb{C}|$. However, at each step, by definition of relative, $S$ gains at most one new row or column, so $r+c$ can only increase by at most $1$. Thus, $r+c-|S|$ is nonincreasing; since its initial value is $1+1-1=1$, $|S| \ge r + c - 1 = |\mathbb{R}| + |\mathbb{C}| - 1$, as desired. With these two lemmas, we can show that at least $6m$ blue cells must be used. First, if some row or column has no blue cells, it is clear that at least $8m$ blue cells must be used. Otherwise, the $\mathbb{R}_i$ form a partition of all the rows; likewise for the columns. Then by lemma $2$ there are at least $\sum (|\mathbb{R}_i| + |\mathbb{C}_i| - 1)$ blue cells. Note that, for all $i$, $(|\mathbb{R}_i| + |\mathbb{C}_i|) \ge 4$; if this sum is $3$, then some maximal component $C_i$ contains only two blue cells, which is impossible since then each of these blue cells would have only one blue relative. The number of blue cells is thus minimized when each $(|\mathbb{R}_i| + |\mathbb{C}_i|)$ is minimized (as this maximizes the total number of these sums). From $(|\mathbb{R}_i| + |\mathbb{C}_i|) \ge 4$ and from $\sum |\mathbb{R}_i| = \sum |\mathbb{C}_i| = 4m$, we find that the number of blue cells is at least $8m - \frac{8m}{4} = 6m$. The construction is noted in above posts.

[asy][asy] //code adapted from v_Enhance's EGMO diagram last year since idk how to use asy size(4cm); for (int i=0; i<=4; ++i) { draw((0,i)--(4,i), black+1); draw((i,0)--(i,4), black+1); } void bluesquare(int a, int b){ filldraw((a,b)--(a,b+1)--(a+1,b+1)--(a+1,b)--cycle,blue); } bluesquare(0,0); bluesquare(1,1); bluesquare(2,2); bluesquare(3,3); [/asy][/asy] Why we can not coloured $4\times4$ block like above?

because cells aren't related to themselves

At least $6m$ blue cells are needed, and this has been shown to be achievable by others in this thread. First, if an entire row or column does not have any blue cells, then $8m$ blue cells are needed. Let's do better by assuming that every row and every column has at least one blue cell. We place $4m$ blue cells such that there is exactly one per row. Now we split the columns into four groups based on the number of blue cells in that column: 3+, 2, 1, 0. Let the number of columns in each group be $a, b, c, d$, respectively. Then, $a+b+c+d = 4m$ and $3a+2b+c\le 4m$. Now we need to add some number of blue cells so that each of these $4m$ blue cells is related to two others. One lower bound is $d$, because each column must have at least one blue cell. Another lower bound is $\frac{b+2c+d}{2}$ because we need to add at least one blue cell for each column with two blue cells, two blue cells for each column with one blue cell, and one blue cell for each column with no blue cells, and then divide by 2 because each added blue cell is related to the other blue cells in its column and exactly one other original blue cell. From our equation and inequality above, \begin{align*} 3(a+b+c+d)-(3a+2b+c)&\ge 12m - 4m\\ \implies b+2c+3d&\ge 8m\\ \implies \frac{b+2c+d}{2}&\ge 4m-d \end{align*}Combining the two lower bounds shows that at least $2m$ blue cells must be added. All together, at least $6m$ blue cells are needed.

colinhy wrote: More generally, for an $n \times n$ grid where there must be at least $k$ related cells, the minimum number is bounded by (if I'm not mistaken): $$k = 2x \rightarrow \frac{x^2+2x}{x+1} \cdot n, 2x+2 \mid n$$$$k = 2x+1 \rightarrow \frac{2x^2+6x+3}{2x+3} \cdot n, 4x+6 \mid n$$ How did u get these about K & n?

Please verify this solution.

I saw this in a different context a while ago (uncited) and then stumbled across it again today (where it was cited). wacky. We claim that the answer is $6m$. To construct this, place $m$ of the following $4\times 4$ grids along the diagonal. \[\begin{bmatrix} 0 & B & B & B \\ B & 0 & 0 & 0 \\ B & 0 & 0 & 0 \\ B & 0 & 0 & 0 \end{bmatrix} \]which clearly works. Firstly, note that if a row is empty, we clearly need at least two blue cells in each column, for a total of $8m$. Similarly, if a column is empty, we also need $8m>6m$. Henceforth, assume that all rows/columns are nonempty. To prove optimality, consider the subgraph of $K_{4m\times 4m}$ where an edge $(i,j)$ exists if and only if the cell at position $(i,j)$ is blue. Then, note that the condition of each row/column being nonempty corresponds to the condition that every vertex in the graph has an edge. Additionally, the main construct from the problem statement, every cell being related to at least two blue cells, corresponds to the condition that every edge in the subgraph must be incident at a common vertex with at least two other edges. Taken together, we may consider the connected components of the subgraph and deduce the following: (1) the components cover the $8m$ vertices and (2) every connected component has at least 3 edges. However, note that for all connected components \[\frac{E}{V}\geq \frac{E}{E+1} \geq \frac34\]where the first inequality comes from the fact that the components are connected, and the second from $E\geq 3$. Thus, \[E_{\text{total}} = \sum_{\text{each connected component}} E \geq \sum_{\text{each connected component}} \frac34 V = \frac34 \cdot 8m = 6m\]and since the total number of edges is the number of blue cells, we have shown that there are at least $6m$ blue cells and we are done. $\blacksquare$.

Good problem