Consider a positive integer $n$ and $A = \{ 1,2,...,n \}$. Call a subset $X \subseteq A$ perfect if $|X| \in X$. Call a perfect subset $X$ minimal if it doesn't contain another perfect subset. Find the number of minimal subsets of $A$.
Problem
Source: Moldova TST Problem 8
Tags: combinatorics, counting, Subsets
01.04.2015 21:34
Tsarik wrote: Consider a positive integer $n$ and $A = \{ 1,2,...,n \}$. Call a subset $X \subseteq A$ perfect if $|X| \in X$. Call a perfect subset $X$ minimal if it doesn't contain another perfect subset. Find the number of minimal subsets of $A$. Let $E$ a minimal subset. Let $m(E)=\min_{x\in E}x$ : we have $m(E)=|E|$ and $x\ge m(E)$ $\forall x\in E$ So $n-m(E)\ge m(E)-1$ which is $m(E)\le\left\lfloor\frac{n+1}2\right\rfloor$ The number of minimal subsets whose cardinal is $p\le\frac{n+1}2$ is $\binom{n-p}{p-1}$ Hence the answer : $\boxed{\sum_{k=1}^{\left\lfloor\frac{n+1}2\right\rfloor}\binom{n-k}{k-1}}$
01.04.2015 21:42
Which is also a Fibonacci number. This is also Putnam 1996 B1: http://www.artofproblemsolving.com/community/q2h592546p3512920 http://www.artofproblemsolving.com/community/c6h485483p2719827 http://www.artofproblemsolving.com/community/c6h319148p1715096
04.12.2018 13:50
Very nice and interesting problem! Thanks for all!