IMO 2002 SL C1

Origin: COL | Category: Combinatorics

Problem

Let n be a positive integer. Each point (x, y) in the plane, where x and y are nonnegative integers with x + y \leqn, is colored red or blue, subject to the following condition: If a point (x, y) is red, then so are all points (x′, y′) with x′ \leqx and y′ \leqy. Let A be the number of ways to choose n blue points with distinct x-coordinates, and let B be the number of ways to choose n blue points with distinct y-coordinates. Prove that A = B.

Solution

Let ai be the number of blue points with x-coordinate i, and bi the number of blue points with y-coordinate i. Our task is to show that a0a1 \cdot \cdot \cdot an−1 = b0b1 \cdot \cdot \cdot bn−1. Moreover, we claim that a0, . . . , an−1 is a permutation of b0, . . . , bn−1, and to show this we use induction on the number of red points. The result is trivial if all the points are blue. So, choose a red point (x, y) with x+y maximal: clearly ax = by = n−x−y−1. If we change this point to blue, ax and by will decrease by 1. Then by the induction hypothesis, a0, . . . , an−1 with ax decreased by 1 is a permutation of b0, . . . , bn−1 with by decreased by 1. However, ax = by, and the claim follows. Remark. One can also use induction on n: it is not more difficult.