# 'selfish' set to be a set which has its own cardinality (number of elements) as an element

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.

My Attempt: Assume $$\textbf{A}$$ to be a selfish set. If the cardinality of $$\textbf{A}$$ is $$c$$, then can $$\textbf{A}$$ contain $$1,2,3....c-1$$. Definitely answer is no. because if it contains $$k then deleting $$c-k$$ elements except $$k$$ from $$\textbf{A}$$ gives a subset of k elements contradicting the fact that $$\textbf{A}$$ is minimal selfish. Thus $$\textbf{A}$$ must contain elements greater than or equal to $$c$$. But how do I find the minimal selfish sets with order $$c$$?

• Reference note: This question, including the terminology, was problem B1 on the 1996 Putnam. – jmerry Dec 8 '18 at 7:51

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.
Your logic so far is fine. So what you know is that, since $$c$$ is in the set, then the other $$c-1$$ elements must all be at least $$c+1$$. There are $$\binom{n-c}{c-1}$$ ways to choose them.
Summing over these gives you the total count. It turns out that this gives you the $$n^{th}$$ Fibonacci number, which you can prove by induction (hint: use Pascal’s identity).