Problem

Source: Stars of Mathematics 2012, Seniors, Problem 4

Tags: combinatorics



The cells of some rectangular $M \times n$ array are colored, each by one of two colors, so that for any two columns the number of pairs of cells situated on a same row and bearing the same color is less than the number of pairs of cells situated on a same row and bearing different colors. i) Prove that if $M=2011$ then $n \leq 2012$ (a model for the extremal case $n=2012$ does indeed exist, but you are not asked to exhibit one). ii) Prove that if $M=2011=n$, each of the colors appears at most $1006\cdot 2011$ times, and at least $1005\cdot 2011$ times. iii) Prove that if however $M=2012$ then $n \leq 1007$. (Dan Schwarz)