IMO 2002 · Problem 1

\(S\) is the set of all \((h,k)\) with \(h,k\) non-negative integers such that \(h+k<n\). Each element of \(S\) is colored red or blue, so that if \((h,k)\) is red and \(h'\le h,k'\le k\), then \((h',k')\) is also red. A type 1 subset of \(S\) has \(n\) blue elements with different first member and a type 2 subset of \(S\) has \(n\) blue elements with different second member. Show that there are the same number of type 1 and type 2 subsets.

Official text of the problem. Official problem paper (PDF)

Solution

Let \(c_h\) denote the number of blue points whose first coordinate is \(h\), and let \(r_k\) denote the number of blue points whose second coordinate is \(k\).

There are exactly \(n\) possible values of either coordinate, namely \(0,1,\ldots,n-1\). Thus a type 1 subset chooses exactly one blue point for each first coordinate, while a type 2 subset chooses exactly one blue point for each second coordinate. Consequently, their respective numbers are \[ \prod_{h=0}^{n-1}c_h \qquad\text{and}\qquad \prod_{k=0}^{n-1}r_k. \] We will prove that the two lists \((c_h)\) and \((r_k)\) have the same entries with the same multiplicities.

Start with every point blue. Then both lists are \[ n,n-1,\ldots,1. \] Now recolor precisely the points that are red in the given coloring, one at a time, in nondecreasing order of \(h+k\), breaking ties arbitrarily.

Consider the moment just before a point \((h,k)\) is recolored red. Every point \[ (h,0),(h,1),\ldots,(h,k-1) \] is red in the given coloring, by the hypothesis. Each has smaller coordinate sum than \((h,k)\), so each has already been recolored. Every point \((h,j)\) with \(j>k\) is still blue: if it is to be recolored at all, its larger coordinate sum places it later. Therefore the blue points with first coordinate \(h\) are exactly \[ (h,k),(h,k+1),\ldots,(h,n-h-1), \] and their number is \(n-h-k\).

The identical argument with the coordinates interchanged shows that the number of blue points with second coordinate \(k\) is also \(n-h-k\).

Thus this recoloring replaces one entry \(n-h-k\) by \(n-h-k-1\) in each of the two lists, leaving every other entry unchanged. Equality of the lists as multisets is therefore preserved at every step.

After all recolorings, the lists still have the same entries with the same multiplicities, so their products are equal. This proves the desired equality, including cases where a product is zero.

If \(n=0\) is allowed, \(S\) is empty and the empty subset is the unique subset of either type, so the conclusion also holds.

The solution was checked against Evan Chen's published IMO solution notes.