Let S be a set with 1000 elements. Find a, b, c, the number of subsets R of S such that |R| = 0, 1, 2 (mod 3) respectively. Find a, b, c if |S| = 1001.
Solution
Answer: [21000/3], [21000/3], [21000/3] + 1; [21001/3] + 1, [21001/3], [21001/3] + 1.
Let f0(n), f1(n), f2(n) be the number of subsets of a set with n elements whose size is = 0, 1, 2 (mod 3) respectively.
Let S be a set with n elements and X another element not in S, so that S' = S ∪ {X} has n+1 elements. Then the subsets of S' are just the subsets of S and the subsets of S with X adjoined. So f0(n+1) = f0(n) + f2(n). Similarly, f1(n+1) = f1(n) + f0(n) and f2(n+1) = f2(n) + f1(n).
These recurrence relations and the obvious initial values f0(1) = f1(1) = 1, f2(1) = 0 are sufficient to determine f0, f1 and f2. By looking at low values of n we quickly conjecture that fi(n) = [2n/3] for n = 2i+2, 2i+3, 2i+4 (mod 6) and [2n/3] + 1 for n = 2i-1, 2i, 2i+1 (mod 6). Proving that is an easy (but slightly monotonous) induction. The required answer then follows at once.
© John Scholes
jscholes@kalva.demon.co.uk
18 Aug 2001