IMO 1988 SL 21

Origin: POL

Problem

Forty-nine students solve a set of three problems. The score for each problem is a whole number of points from 0 to 7. Prove that there exist two students A and B such that for each problem, A will score at least as many points as B.

Solution

Let X be the set of all ordered triples a = (a1, a2, a3) for ai \in{0, 1, . . ., 7}. Write a ≺b if ai \leqbi for i = 1, 2, 3 and a ̸= b. Call a subset Y \subsetX independent if there are no a, b \inY with a ≺b. We shall prove that an independent set contains at most 48 elements. For j = 0, 1, . . ., 21 let Xj = {(a1, a2, a3) \inX | a1 +a2 +a3 = j}. If x ≺y and x \inXj, y \inXj+1 for some j, then we say that y is a successor of x, and x a predecessor of y. Lemma. If A is an m-element subset of Xj and j \leq10, then there are at least m distinct successors of the elements of A. Proof. For k = 0, 1, 2, 3 let Xj,k = {(a1, a2, a3) \inXj | min(a1, a2, a3, 7 − a1, 7 −a2, 7 −a3) = k}. It is easy to verify that every element of Xj,k has at least two successors in Xj+1,k and every element of Xj+1,k has at most two predecessors in Xj,k. Therefore the number of elements of A \capXj,k is not greater than the number of their successors. Since Xj is a disjoint union of Xj,k, k = 0, 1, 2, 3, the lemma follows. Similarly, elements of an m-element subset of Xj, j \geq11, have at least m predecessors. Let Y be an independent set, and let p, q be integers such that p < 10 < q. We can transform Y by replacing all the elements of Y \capXp with their successors, and all the elements of Y \capXq with their predecessors. After this transformation Y will still be independent, and by the lemma its size will not be reduced. Every independent set can be eventually transformed in this way into a subset of X10, and X10 has exactly 48 elements.