4
$\begingroup$

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<c$ 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$?

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

Your argument is correct.

Lets see if recursion helps.

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.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy