20th APMC 1997 Problem 8 Let X be a set with n members. Find the largest number of subsets of X each with 3 members so that no two are disjoint.
All 3-element subsets for n ≤ 5. (n-1)(n-2)/2 for n ≥ 6. Solution The result is obvious for n  0 which is true since n > 6). So there is a set containing just one element of {1,2,3}. wlog it is {1,4,5}. If all sets contain 1, then we are home, since there are only (n-1)(n-2)/2 such sets. So assume there is a set not containing 1. It must overlap {1,2,3} and {1,4,5}, so wlog it contains 2 and 4. Suppose it also contains 6, so we have {2,4,6} Note that (n-1)(n-2)/2 - (n-2)(n-3)/2 = n-2. So if n-2 or less sets contain 7, then we are home by induction. So assume 7 belongs to at least n-1 sets. Now such a set must contain 1, 2, or 3. If it contains 1, then it must contain 2, 4 or 6, giving three possibilities, {1,2,7}, {1,4,7} and {1,6,7}. If it contains 2, then it must contain 1, 4, or 5, so we get two more possibilities, {2,4,7} and {2,5,7}. If it contains 3, then it must contain one of 1,4,5 and one of 2,4,6. Hence it must be {3,4,7}. So there are only 6 possible sets containing 7. So if n > 7 we are home. If n = 7, we consider what other sets can contain 6. Such a set must contain 1, 2 or 3. If it contains 1, then it must overlap {2,5,7} and {3,4,7}, so it must contain 7, but we have already got {1,6,7}. If it contains 2, then it must overlap {1,4,5} and {3,4,7}, so it must contain 4, but we have already got {2,4,6}. If it contains 3, then it must overlap {1,4,5} and {1,2,7}, so it must contain 1, but then it does not overlap {2,5,7}. so no further sets containing 6 are possible, so we have ≤ n-2 sets containing 6 and hence are home by induction. 20th APMC 1997 © John Scholes jscholes@kalva.demon.co.uk 28 Nov 2003 Last corrected/updated 28 Nov 03