HMMT-Nov 2016 guts, Problem 11

How many subsets $S$ of the set $\{1,2, \ldots, 10\}$ satisfy the property that, for all $i \in[1,9]$, either $i$ or $i+1$ (or both) is in $S$ ?

Solution: We do casework on the number of $i$ 's not in $S$. Notice that these $i$ 's that are not in $S$ cannot be consecutive, otherwise there exists an index $i$ such that both $i$ and $i+1$ are both not in $S$. Hence if\\ there are $k i$ 's not in $S$, we want to arrange $k$ black balls and $10-k$ white balls such that no two black balls are consecutive. Take out $k-1$ white balls to insert back between black balls later, then we want to arrange $k$ black balls and $11-2 k$ white balls arbitrarily, which can be done in $\left(\begin{array}{c}11-k \\ k\end{array}\right)$ ways. Hence we want to find the sum $\left(\begin{array}{c}11 \\ 0\end{array}\right)+\left(\begin{array}{c}10 \\ 1\end{array}\right)+\left(\begin{array}{l}9 \\ 2\end{array}\right)+\left(\begin{array}{l}8 \\ 3\end{array}\right)+\left(\begin{array}{l}7 \\ 4\end{array}\right)+\left(\begin{array}{l}6 \\ 5\end{array}\right)$, which is equal to 144 ways. $\fbox{144}$.

Answer: 144