IMO 2004 SL C6

For an n imes n matrix A, let Xi be the set of entries in row

imoshortlistmathematicsolympiadcombinatorics

IMO 2004 SL C6

Origin: IRN | Category: Combinatorics

Problem

For an n \times n matrix A, let Xi be the set of entries in row i, and Yj the set of entries in column j, 1 \leqi, j \leqn. We say that A is golden if X1, . . . , Xn, Y1, . . . , Yn are distinct sets. Find the least integer n such that there exists a 2004 \times 2004 golden matrix with entries in the set {1, 2, . . ., n}.

Solution

Since Xi, Yi, i = 1, . . . , 2004, are 4008 distinct subsets of the set Sn = {1, 2, . . ., n}, it follows that 2n \geq4008, i.e. n \geq12. Suppose n = 12. Let X = {X1, . . . , X2004}, Y = {Y1, . . . , Y2004}, A = X \cupY. Exactly 212 −4008 = 88 subsets of Sn do not occur in A. Since each row intersects each column, we have Xi \capYj ̸= \emptysetfor all i, j. Suppose |Xi|, |Yj| \leq3 for some indices i, j. Since then |Xi \cupYj| \leq5, any of at least 27 > 88 subsets of Sn \ (Xi \capYj) can occur in neither X nor Y, which is impossible. Hence either in X or in Y all subsets are of size at least 4. Suppose w.l.o.g. that k = |Xl| = mini |Xi| \geq4. There are nk = 12 −k  + 12 −k 

  • \cdot \cdot \cdot + 12 −k k −1  subsets of S \ Xl with fewer than k elements, and none of them can be either in X (because |Xl| is minimal in X) or in Y. Hence we must have nk \leq88. Since n4 = 93 and n5 = 99, it follows that k \geq6. But then none of the 12 
  • \cdot \cdot \cdot + 12  = 1586 subsets of Sn is in X, hence at least 1586−88 = 1498 of them are in Y. The 1498 complements of these subsets

also do not occur in X, which adds to 3084 subsets of Sn not occurring in X. This is clearly a contradiction. Now we construct a golden matrix for n = 13. Let A1 =

1 1 2 3

and Am =

Am−1 Am−1 Am−1 Bm−1

for m = 2, 3, . . . , where Bm−1 is the 2m−1 \times 2m−1 matrix with all entries equal to m + 2. It can be easily proved by induction that each of the matrices Am is golden. Moreover, every upper-left square submatrix of Am of size greater than 2m−1 is also golden. Since 210 < 2004 < 211, we thus obtain a golden matrix of size 2004 with entries in S13.