42nd International Mathematical OlympiadIMO 2001 Problems and SolutionsWashinton, DC, USAJuly 1-14, 2001 Problem 3Twenty-one girls and twenty-one boys took part in a mathematical contest.
Prove that there was a problem that was solved by at least three girls and at least three boys. Solution 1 We introduce the following symbols: G is the set of girls at the competition and B is the set of boys, P is the set of problems, P(g) is the set of problems solved by g G, and P(b) is the set of problems solved by b B. Finally, G(p) is the set of girls that solve p P and B(p) is the set of boys that solve p. In terms of this notation, we have that for all g G and b B,
We wish to prove that some p P satisfies |G(p)| >= 3 and |B(p)|>=3. To do this, we shall assume the contrary and reach a contradiction by counting (two ways) all ordered triples (p, q, r) such that p P(g) P(b). With T = {(p, g, b) : p P(g) P(b)}, condition (b) yields
Assume that no p P satisfies |G(p)| >= 3 and |B(p)| >= 3. We begin by noting that
(Note. The equality in (2) is obtained by a standard double-counting technique: Let (g, p) = 1 if g solves p and (g, p) = 0 otherwise, and interchange the orders of summation in _{pP} _{gG} (g, p).) Let
Claim. _{pP-} |G(p)| >= |G| thus _{pP+} |G(p)| <= 5 |G|. Also _{pP+} |B(p)| >= |B| thus _{pP-} |B(b)| <= 5 |B|. Proof. Let g G be arbitrary. By the Pigeonhole Principle, conditions (a) and (b) imply that g solves some problem p that is solved by at least 21/6 = 4 boys. By assumption, |B(p)| >= 4 implies that p P_{-}, so every girl solves at least one problem in P_{-}. Thus
In view of (2) and (3) we have
Also, each boy solves a problem that is solved by at least four girls, so each boy solves a problem p P_{+}. Thus _{pP+} |B(p)| >= |B|, and the calculation proceeds as before using (2). Using the claim just established, we find
This contradicts (1), so the proof is complete. Solution 2 Let us use some of the notation given in the first solution. Suppose that for every p P either |G(p)| <= 2 or |B(p)| <= 2. For each p P, color p red if |G(p)| <= 2 and otherwise color it black. In this way, if p is red then |G(p)| <= 2 and if p is black then |B(p)| <= 2. Consider a chessboard with 21 rows, each representing one of the girls, and 21 columns, each representing one of the boys. For each g G and b B, color the square corresponding to (g, b) as follows: pick p P(g) P(b) and assign p's color to that square. (By condition (b), there is always an available choice.) By the Pigeonhole Principle, one of the two colors is assigned to at least 441/2 = 221 squares, and thus some row has at least 221/21 = 11 black squares or some column has at least 11 red squares. Suppose the row corresponding to g G has at least 11 black squares. Then for each of 11 squares, the black problem that was chosen in assigning the color was solved by at most 2 boys. Thus we account for at least 11/2 = 6 distinct problems solved by g. In view of condition (a), g solves only these problems. But then at most 12 boys solve a problem also solved by g, in violation of condition (b). In exactly the same way, a contradiction is reached if we suppose that some column has at least 11 red squares. Hence some p P satisfies |G(p)| >= 3 and |B(p)| >= 3. |