Czech-Polish-Slovak Mathematical Match competition problems

Let us index the unit squares of the board by pairs of integers $(a, b)$ with $1 \le a, b \le 2n$. We prove that the largest possible number of pretty sets is $n^4$.

For the upper bound, consider coloring all the unit squares $(a, b)$ with $a, b \le n$ or $a, b \ge n+1$ blue, and all the other unit squares red. It is straightforward to verify that this coloring yields $n^4$ pretty sets. Thus we are left with proving that no coloring yields more pretty sets.

Call an unordered pair of distinct unit squares $\{A, B\}$ mixed if $A$ and $B$ are in the same row and $A$ and $B$ have different colors. Clearly, if a row contains $a$ blue squares and $b$ red squares ($a + b = 2n$), then it contains $ab \le n^2$ mixed pairs. Therefore, there are at most $2n^3$ mixed pairs in total.

Let every mixed pair $\{A, B\}$ charge the unordered pair $\{i, j\}$ of distinct columns such that $A$ is in column $i$ and $B$ is in column $j$. Denote by $\text{charge}(i, j)$ the number of times the pair of columns $\{i, j\}$ is charged.

Obviously, every pair of columns is charged at most $2n$ times, i.e., $\text{charge}(i, j) \le 2n$. Moreover, since there are at most $2n^3$ mixed pairs in total, we have $\sum_{\{i,j\}} \text{charge}(i, j) \le 2n^3$ where the summation is over pairs of distinct columns $\{i, j\}$.

Observe that if a pair of distinct columns $\{i, j\}$ is charged $k = \text{charge}(i, j)$ times, then there are at most $\frac{k^2}{4}$ pretty sets with squares contained in these columns. This is because for some $a, b$ with $a + b = k$ there are $a$ red-blue and $b$ blue-red mixed pairs within these columns, yielding $ab \le \frac{k^2}{4}$ pretty sets. Therefore, the total number of pretty sets is at most
$$\frac{1}{4} \sum_{\{i,j\}} \text{charge}(i,j)^2 \le \frac{n}{2} \cdot \sum_{\{i,j\}} \text{charge}(i,j) \le n^4,$$
where again the summation is over unordered pairs of distinct columns. This concludes the proof. $\square$