Putnam 1996 Problem B1 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
: 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 u n = |S n |. Clearly S n ⊆ S n+1 . Indeed if n+1 ∉ A ∈ S n+1 , then A ∈ S n+1 . Suppose now that n+1 ∈ A ∈ S n+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 S n-1 , and it is clearly (1, 1). We show that is also onto. Suppose B ∈ S n-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 ∈ S n+1 and f(A) = B, so f is onto. So S n+1 = S n ∪ S n-1 , and hence u n+1 = u n + u n-1 . Clearly u 2 = 1, u 3 = 2, so u n is the Fibonacci sequence. Putnam 1996 © John Scholes jscholes@kalva.demon.co.uk 12 Dec 1998