Let N be the set {1, 2, 3, ... , n}. X is selfish if |X| ∈ X. How many subsets of N are selfish and have no proper selfish subsets.
Solution
Answer: Fibonacci sequence.
Easy if you spot the pattern. A routine computation with binomial coefficients if not.
Observe first that X is a minimal selfish set iff |X| is the smallest element of X. Let be the collection of selfish subsets of {1, 2, ... , n} and let un = |Sn|. Clearly Sn ⊆ Sn+1. Indeed if n+1 ∉ A ∈ Sn+1, then A ∈ Sn+1. Suppose now that n+1 ∈ A ∈ Sn+1. Define f(A) as follows: remove n+1 and reduce the other elements by 1. No element of f(A) can exceed n-1, so f is a map to Sn-1, and it is clearly (1, 1). We show that is also onto. Suppose B ∈ Sn-1. Form A by increasing each element by 1 and adjoining n+1. A is a minimal selfish set because |B| is the smallest element of B, so |A| = |B|+1 is the smallest element of A. Hence A ∈ Sn+1 and f(A) = B, so f is onto. So Sn+1 = Sn ∪ Sn-1, and hence un+1 = un + un-1. Clearly u2 = 1, u3 = 2, so un is the Fibonacci sequence.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998