IMO 2012 Shortlist C3

Category: Combinatorics

Problem

In a 999 × 999 square table some cells are white and the remaining ones are red. Let T be the number of triples (C1,C2,C3) of cells, the first two in the same row and the last two in the same column, with C1 and C3 white and C2 red. Find the maximum value T can attain. Solution. We prove that in an n × n square table there are at most 4n4 such triples. Let row i and column j contain ai and bj white cells respectively, and let R be the set of red cells. For every red cell (i,j) there are aibj admissible triples (C1,C2,C3) with C2 = (i,j), therefore T = X (i,j)∈R aibj. We use the inequality 2ab ≤ a2

• b2 to obtain T ≤ X (i,j)∈R (a2 i + b2 j) = n X i=1 (n − ai)a2 i + n X j=1 (n − bj)b2 j. This is because there are n − ai red cells in row i and n − bj red cells in column j. Now we maximize the right-hand side. By the AM-GM inequality we have (n − x)x2 = (2n − 2x) · x · x ≤  2n 3 = 4n3 , with equality if and only if x = 2n . By putting everything together, we get T ≤ n 4n3

n 4n3

4n4 . If n = 999 then any coloring of the square table with x = 2n = 666 white cells in each row and column attains the maximum as all inequalities in the previous argument become equalities. For example color a cell (i,j) white if i − j ≡ 1,2,...,666 (mod 999), and red otherwise. Therefore the maximum value T can attain is T = 4·9994 . Comment. One can obtain a better preliminary estimate with the Cauchy-Schwarz inequality: T = X (i,j)∈R aibj ≤   X (i,j)∈R a2 i   ·   X (i,j)∈R b2 j  

n X i=1 (n − ai)a2 i !1 ·   n X j=1 (n − bj)b2 j   . It can be used to reach the same conclusion.22