Czech-Polish-Slovak Mathematical Match

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$