Putnam 1996, Problem B-1

Define a **selfish** set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of \( \{1,2,\ldots,n\} \) which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish.

Solution:
Let \([n]\) denote the set \(\{1, 2, \ldots, n\}\), and let \(f_n\) denote the number of minimal selfish subsets of \([n]\). Then the number of minimal selfish subsets of \([n]\) not containing \(n\) is equal to \(f_{n-1}\). On the other hand, for any minimal selfish subset of \([n]\) containing \(n\), by subtracting 1 from each element, and then taking away the element \(n - 1\) from the set, we obtain a minimal selfish subset of \([n - 2]\) (since 1 and \(n\) cannot both occur in a selfish set). Conversely, any minimal selfish subset of \([n - 2]\) gives rise to a minimal selfish subset of \([n]\) containing \(n\) by the inverse procedure. Hence the number of minimal selfish subsets of \([n]\) containing \(n\) is \(f_{n-2}\). Thus we obtain \(f_n = f_{n-1} + f_{n-2}\). Since \(f_1 = f_2 = 1\), we have \(f_n = F_n\), where \(F_n\) denotes the \(n\)th term of the Fibonacci sequence.