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)
Problem
Source: Stars of Mathematics 2012, Seniors, Problem 4
Tags: combinatorics
13.03.2015 02:22
Let the two colors be denoted by $ 1, -1 $. We have the column vectors $ v_1,v_2, \cdots, v_n $ $ \in \{ 1, -1 \}^{2011} $ with the usual inner product as the dot product. The problem statement then says that $ \langle v_i, v_j \rangle $ is negative whenever $ i \neq j $. Thus, in part (i) , we have $ \langle v_i, v_j \rangle \le -1 $ for $ i \neq j $ and hence, \[ 0 \le \langle \sum_{i=1}^{n} v_i, \sum_{i=1}^{n} v_i \rangle = \sum_{i=1}^{n} \langle v_i, \sum_{i=1}^{n} v_i \rangle \le \sum_{i=1}^{n} 2011 -1(n-1) = \sum_{i=1}^{n} 2012-n = n(2012-n) \implies n \le 2012 \] In part (iii), due to a parity argument, $ \langle v_i, v_j \rangle $ is even and hence, $ \langle v_i, v_j \rangle \le -2 $. Carrying out a similar computation gives $ 0 \le n(2014-2n) \implies n \le 1007 $ I'll try part (ii) later since I'm short of sleep. For part (ii), if the colors are yellow and blue, it suffices to show that $ | Y - B | \le 2011 $, where $ Y $ and $ B $ are the number of yellow and blue squares respectively on the board. In row $ i $, let there be $ y_i $ squares colored yellow and $ b_i $ squares colored blue. We then have \[ \sum_{i=1}^{2011} \binom{y_i}{2}+\binom{b_i}{2}-y_ib_i \le - \binom{2011}{2} \implies \sum_{i=1}^{2011} (y_i-b_i)^2 \le 2011 \] But, \[ \sum_{i=1}^{2011} (y_i-b_i)^2 \ge \frac{(\sum_{i=1}^{2011} |y_i-b_i|)^2}{2011} \ge \frac{|Y-B|^2}{2011} \implies |Y-B| \le 2011 \] Combining with $ Y+B = 2011^2 $, we get \[ 2011^2-2011 \le 2Y, 2B \le 2011^2 + 2011 \implies 2011 \cdot 1005 \le Y,B \le 2011 \cdot 1006 \]