49 students solve a set of 3 problems. Each problem is marked from 0 to 7. Show that there are two students A and B such that A scores at least as many as B for each problem.
Solution
We denote a set of scores by (a, b, c), where a is the score on the first problem, b the score on the second problem, and c the score on the third problem. Let Xi be set of (a, b, c) with a + b + c = i. Obviously we cannot have two distinct triples (a, b, c) and (a', b', c') both in Xi with a ≥ a', b ≥ b' and c ≥ c'. But it is easy to check that X10 has 48 elements. So the result is false for 48 students (because each could have a different triple in X10).
************************ incomplete ******************
© John Scholes
jscholes@kalva.demon.co.uk
30 Dec 2002
Last corrected/updated 30 Dec 02