8th Chinese 1993 Problem B2 S = {1, 2, ... , 30}. A 1 , A 2 , ... , A 10 are subsets of S each containing 3 elements. A i and A j have at least one element in common. Let n i be the number of A j to which i belongs. What is the smallest possible value of max n i ? Solution
: 5. Take each of the following subsets and the starred ones twice. It is easy to check that every pair of subsets has at least one element in common. 1 occurs in three subsets, 2, 4 and 6 each occur in four subsets and 3, 5, 7 each occur in five subsets. 123 145 167 246 257* 347* 356* Take any subset X. Each of the other 9 subsets shares an element with X, so one of the elements of X must be in at least 3 of the other subsets and hence in a total of 4 subsets. So the answer is 4 or 5. Suppose it is 4. Now any subset contains three elements. Each can occur in at most three other subsets, but there are nine other subsets, so each must occur in exactly three other subsets and hence in exactly 4 subsets in all. But the 10 subsets contain 30 elements in total and 30 is not divisible by 4. Contradiction. Hence the answer is 5. 8th Chinese 1993 © John Scholes jscholes@kalva.demon.co.uk 25 June 2002