Since there are $2n \cdot 2n = 4n^2$ tiles coloured with $n$ colours, there exists a colour $k$ used on at least $4n$ tiles. Consider all the $4n$ tiles with this colour. For each index $1 \leq i \leq 2n$, let $f(i)$ be the number of tiles with colour $k$ at row $i$. Then, we have $\sum_{i = 1}^{2n} f(i) = 4n$ and $f(i) \leq 2n$ for each $1 \leq i \leq 2n$. In particular: 1. There exists at least two indices $i$ such that $f(i) \geq 2$. Indeed, otherwise $4n = \sum_{i = 1}^{2n} f(i) \leq (2n) + 1 \cdot (2n - 1) = 4n - 1$, a contradiction. 2. Consider the set $S$ of all indices $i$ such that $f(i) \geq 2$. Then, $\sum_{i \in S} f(i) > 2n$. This has the same proof as above. By definition of $S$, $\sum_{i \not\in S} f(i) \leq \sum_{i \not\in S} 1 = 2n - |S| \leq 2n - 2 < 2n$ due to the previous observation, so \[ \sum_{i \in S} f(i) = 4n - \sum_{i \not\in S} f(i) > 2n. \] Now, consider the set $T$ of all tiles with coordinate $(i, j)$ of colour $k$ with $i \in S$. These correspond to all the tiles with colour $k$ who has another tile within the same row with colour $k$ as well. The number of such pairs (or tiles) is $\sum_{i \in S} f(i) > 2n$, so by the pigeonhole principle, there exist two distinct tiles in $T$ in the same column, say $(i_1, j)$ and $(i_2, j)$. Consider two tiles $(i_1, j'), (i_2, j'') \in T$ with $j', j'' \neq j$; they exist by our construction and previous argument. If $j' = j''$, we can swap two random tiles other than those four tiles we mentioned. If $j' \neq j''$, we swap $(i_2, j')$ and $(i_2, j'')$ and we are done.

Take the color which dominates the most cell, let it be color $C$, which has at least $4n$ squares. Denote the bipartite graph $G, G'$ where $G$ consists of vertices of row and $G'$ consists of vertices of column. Connect two vertex $v \in G$ and $v' \in G'$ if and only if the intersection of row $v$ and column $v'$ contain the square of color $C$. Now, notice that this graph is not a tree, as the number of edge $\ge 4n =$ the number of vertices. Therefore, this graph has a cycle. Notice that this bipartite graph can't contain a triangle, thus, it contain a path of length $4$ (since the previous cycle must be at least of length $4$), we are done.

A good induction problem. Solution. We'll prove a generalization Quote: $2n$ tiles of a $n \times n$ tiles are colored, the rest $n^2 -2n$ aren't colored. Prove that there exist two tiles such that switching those two, then there exists a rectangle with all four corners are colored. Note that this implies the problem since a $2n\times 2n$ colored by $n$ colors must have at least $\frac{4n^2}{n}=4n$ tiles with the same color. The base case, $n=2$ is trivial. There are two cases in the inductive step: a. Assume that it's true for $n = 2,\dots,2k$ where $k\ge 1$. We'll show that it's true for $n=2k+1$. Note that if every row has at least $2$ squares, then there exists at least $\frac{2n}{n}= 2$ rows such that they each have a colored tile, such that the (at least) two colored tiles lie in a common column. Switching the other tiles gives a rectangle (See the picture). Otherwise, there's a row with at most $1$ colored tile. By symmetry, there must exist a column with at most $1$ colored tile otherwise the previous argument works. Now removing the specific $1$ row and the specific $1$ column, we are left with $2k \times 2k$ with at least $4k+2 - 2 \ge 2 (2k)$ colored tiles which works. $\blacksquare$. b. Assume that it's true for $n=3,\dots,2k+1$ where $k\ge 1$. We'll show that it's true for $n=2k+2$. The same previous argument works. $\blacksquare$

We are going to prove the following which is must stronger.(but easier to prove). Quote: $a+b$ tiles of a $a \times b$ tiles are colored, the rest $ab -a-b$ aren't colored. Prove that there exist two tiles such that switching those two, then there exists a rectangle with all four corners are colored.(with $a,b>1$) We induct at $a+b$. The base case $a+b=4$ is obviously. Suppose that it is true for $a+b=n$ we are going to prov that is also true for $a+b=n+1$. If there is a row with at most one colouring cell then we can ignore and by introducing we are done. The sane for the columns. Now if every row, column has at least two black cell then it is easy to see that we are done. Remark:if every row, column has at least two black cell then $a=b$ and every row-column has exactly two.