AMM problem 12449

This is AMM problem 12449 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

Let $n$ be a positive integer with $n \geq 2$. The squares of an $(n^2 + n - 1)$-by-$(n^2 + n - 1)$ grid are colored with up to $n$ colors. Prove that there exist two rows and two columns whose four squares of intersection have the same color.

Solution -

Define a monochromatic $i$-pair as an unordered pair of row indices of squares in the same column with the same color $i$.

Note that if the same $i$-pair appears in two distinct columns, we have found a monochromatic rectangle. If not, each column must contribute distinct $i$-pairs, making the maximum number of possible $i$-pairs $\binom{n^2 + n - 1}{2}$, hence the maximum number of monochromatic pairs $n\cdot\binom{n^2 + n - 1}{2}$.

But if the $k$-th column contains $k_i$ squares of color $i$, then it contributes

$$\sum_{i = 1}^n \binom{k_i}{2}$$

monochromatic pairs, which is minimized when one $k_i$ is $n$ and the remaining $n - 1$ many $k_i$ are $n + 1$.

Thus, the $k$-th column contributes at least

$$\binom{n}{2} + (n - 1)\binom{n + 1}{2} = \frac{n\cdot (n^2 + n - 2)}{2}$$

monochromatic pairs, giving a total of at least

$$\frac{(n^2 + n - 1)\cdot n \cdot (n^2 + n - 2)}{2} = n \cdot \binom{n^2 + n - 1}{2}$$

monochromatic pairs.

Since we have equality, each color $i$ must contribute the same number (i.e. $\binom{n^2 + n - 1}{2}$) of $i$-pairs, while simultaneously all $k_i \in \{n, n + 1\}$. The latter means that each color $i$ must contribute a multiple of $n$ many $i$-pairs, whereas

$$n \nmid \binom{n^2 + n - 1}{2}$$

which is a contradiction. $\square$