imo.wolfram.com
header_a.gif Wolfram Research  
mainscorescontestantscompetition problemsaboutphotoIMO Facts


42nd International Mathematical Olympiad


IMO 2001 Problems and Solutions

Washinton, DC, USA
July 1-14, 2001



Problem 3

Twenty-one girls and twenty-one boys took part in a mathematical contest.

  • Each contestant solved at most six problems.

  • For each girl and each boy, at least one problem was solved by both of them.

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.