1st Irish 1988 Problem 5 Let X = {1, 2, 3, 4, 5, 6, 7}. How many 7-tuples (X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 ) are there such that each X i is a different subset of X with three elements and the union of the X i is X?
7! x 6184400 Solution Denote the binomial coefficient by mCn. There are 7C3 = 35 subsets of X with 3 elements. Suppose X 1 = {x, y, z} and X - X 1 = {a, b, c, d}. There are N = 34·33·32·31·30·29 possible choices for the remaining six subsets such that they are all different, but some of these choices will not cover all of {a, b, c, d}. Since 4C3 = 4 < 7, they must cover at least two of them. There are 5C3 = 10 sets not covering a or b. So N 2 = 9·8·7·6·5·4 choices for (X 2 , X 3 , ... , X 7 ) which do not cover a or b. Similarly, since 6C3 = 20, there are N 1 = 19·18·17·16·15·14 choices which do not cover b (some of these may not cover a either). Thus by the principle of inclusion and exclusion, there are 35(N - 4N 1 + 6N 2 ) = 7! x 6184400 possible arrangements. This seems kludgy. Does anyone have a neater solution? 1st Irish 1988 © John Scholes jscholes@kalva.demon.co.uk 11 June 2003 Last updated/corrected 11 Jun 03