A lemma: note that $(a+1)a+(b+1)b-(a+2)(a+1)-b(b-1)=2(b-a-1)$. If $b>a+1$, then $2(b-a-1)>0$ so $(a+1)a+(b+1)b>(a+2)(a+1)+b(b-1)$. This implies that, given a sum of the form \[ \sum_{i=1}^n{a_i(a_i-1)} \] with $a_1, a_2, ..., a_n$ variable nonnegative integers with fixed $a_1+a_2+...+a_n$, the given sum is minimized when there are no two $a_i$ that differ by $2$ or more. Now, in the board, since there are $121$ squares, there must be $41$ of the same color. Let $a_i$ for each $i=1, 2, ..., 11$ be the number of squares of that color on the ith row. Then $a_1+...+a_n=41$, and the sum of the terms $\dfrac{a_i(a_i-1)}{2}$ is minimized when there are no two $a_i$ that differ by $2$ or more, i.e., when there are $8$ of them equal to $4$ and $3$ of them equal to $3$. In other words, the number of pairs of squares of that color in the same row is at least $\dfrac{8 \times 4 \times 3}{2}+\dfrac{3 \times 3 \times 2}{2}=48+9=57$. Since there are $\dfrac{11 \times 10}{2}=55$ pairs of columns, there must be two of those pairs of squares belonging to the same pair of columns, and these two pairs will form a rectangle.

The proof generalizes verbatim to a $(n^2 + n -1) \times (n^2 + n -1)$ table colored in $n > 1$ colors, and indeed it was used as an ulterior contest problem.