15th Chinese 2000 Problem B3 2000 students take a paper of five multiple-choice questions each with four possible answers. Each student chooses one answer per question. What is the smallest n such that the students could have answered the questions in such a way that given any n students we can find four every two of whom answered at least two questions differently.
25 Solution Solution by Johannes Tang We can represent a student's answers as a 5-tuple (a, b, c, d, e), where each of a, b, c, d, e is one of 1, 2, 3, 4. Note that more than one student may give the same 5-tuple. Let S be the set of 5-tuples (a, b, c, d, e) with a + b + c + d + e = 0 mod 4. We can choose a, b, c, d freely and then e is fixed, so S has 256 members. Take any 250 distinct members and suppose 8 students gave each of these 5-tuples. Then given any 25 (> 3·8;) students 4 must have different 5-tuples. But different 5-tuples must differ in at least 2 places, so the result holds for n = 25. It remains to show that it does not hold for n = 24. Let X be the set of all 4 5 = 1024 5-tuples. We can partition X into 256 subsets of 4 element each, so that two elements belong to the same subset iff they differ only in the first element. Since 2000 > 256·7; (= 1792 ) there must be 8 students A 1 , A 2 , ... , A 8 with 5-tuples in the same subset A. The same argument shows that there must be another 8 students B 1 , B 2 , ... , B 8 with 5-tuples in the same subset B. Similarly, there must be another 8 students C 1 , C 2 , ... , C 8 with 5-tuples in the same subset C. Now consider these 24 students. Take any four of them. There must be two with the same letter. So without loss of generality they are A i and A j . But their answers differ only on the first question. So the result does not hold for n = 24. 15th Chinese 2000 (C) John Scholes jscholes@kalva.demon.co.uk 5 Jan 2003 Last corrected/updated 5 Jan 2003