22nd APMC 1999 Problem 1 X is the set {1, 2, 3, ... , n}. How many ordered 6-tuples (A 1 , A 2 , ... , A 6 ) of subsets of X are there such that every element of X belongs to 0, 3 or 6 subsets in the 6-tuple?
22 n Solution For any element k of X, there is 1 way of putting it into none of the six subsets, 20 ways of putting it into three of them, and 1 way of putting it into all of them, so 22 possibilities in all. We can treat each element independently, and the subsets are uniquely determined by the treatment of all n elements. Hence there are 22 n possible ordered 6-tuples. 22nd APMC 1999 © John Scholes jscholes@kalva.demon.co.uk 28 Nov 2003 Last corrected/updated 28 Nov 03