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\ge 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 $(\genfrac{}{}{0ex}{}{n^2+n-1}{2})$, hence the maximum number of monochromatic pairs $n\cdot (\genfrac{}{}{0ex}{}{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(\genfrac{}{}{0ex}{}{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

$$(\genfrac{}{}{0ex}{}{n}{2})+(n-1)(\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{n^2+n-1}{2})$$

monochromatic pairs.

Since we have equality, each color $i$ must contribute the same number (i.e. $(\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{n^2+n-1}{2})$$

which is a contradiction. $◻$