IMO 2002/A1 solution

IMO 2002

Problem A1

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' ≤ h, k' ≤ 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.

Solution

Let a_i be the number of blue members (h, k) in S with h = i, and let b_i be the number of blue members (h, k) with k = i. It is sufficient to show that b₀, b₁, ... , b_n-1 is a rearrangement of a₀, a₁, ... , a_n-1 (because the number of type 1 subsets is the product of the a_i and the number of type 2 subsets is the product of the b_i).

Let c_i be the largest k such that (i, k) is red. If (i, k) is blue for all k then we put c_i = -1. Note that if i < j, then c_i ≥ c_j, since if (j, c_i ) is red, then so is (i, c_i ). Note also that (i, k) is red for k ≤ c_i, so the sequence c₀, c₁, ... , c_n-1 completely defines the coloring of S.

Let S_i be the set with the sequence c₀, c₁, ... , c_i, -1, ... , -1, so that S_n-1 = S. We also take S_-1 as the set with the sequence -1, -1, ... , -1, so that all its members are blue. We show that the rearrangement result is true for S_-1 and that if it is true for S_i then it is true for S_i+1. It is obvious for S_-1, because both a_i and b_i are n, n-1, ... , 2, 1. So suppose it is true for S_i (where i < n-1). The only difference between the a_j for S_i and for S_i+1 is that a_i+1 = n-i-1 for S_i and (n-i-1)-(c_i+1+1) for S_i+1. In other words, the number n-i-1 is replaced by the number n-i-c-2, where c = c_i+1. The difference in the b_j is that 1 is deducted from each of b₀, b₁, ... , b_c. But these numbers are just n-i-1, n-i-1, n-i-2, ... , n-i-c-1. So the effect of deducting 1 from each is to replace n-i-1 by n-i-c-2, which is the same change as was made to the a_j. So the rearrangement result also holds for S_i+1. Hence it holds for S.

43rd IMO 2002