S is a finite set. P is the set of all subsets of S. Show that we can label the elements of P as Ai, such that A1 = ∅ and for each n >= 1, either An-1 ⊂ An and |An - An-1| = 1, or An-1 ⊃ An and |An-1 - An| = 1.
Solution
Let N = 2n and let A1, ... , AN be a solution for n with AN = {n}. Now take AN+m = A2N+1-m union {n+1} for m = N+1, ... , 2N. This gives a solution for n+1.
© John Scholes
jscholes@kalva.demon.co.uk
14 Jan 2002