Problem: How many non-empty subsets $S$ of $\{1,2,3, \ldots, 15\}$ have the following two properties? (1) No two consecutive integers belong to $S$. (2) If $S$ contains $k$ elements, then $S$ contains no number less than $k$. Solution: Notice that the greatest $k$ number of elements that $S$ can contain is $5$. If $k = 6$ then we'd have to pick $6$ nonconsecutive integers among $7,8,9,10,11,12,13,14,15$ which is impossible by the pigeonhole principle. We now ask, how many ways are there to select $m$ nonconsecutive elements from $n$ consecutive integers where $m \leq \left\lfloor \frac{n+1}{2} \right\rfloor$? This corresponds to the number of binary strings of length $n$ with $m$ $1$s such that there are no two consecutive $1$s. We can construct our strings as follows: start with our $m$ ones: $1111\dots 11$. Then, insert $m-1$ zeros between the ones. Now, we have $m+1$ bins to place the remaining $(n-m) -(m-1) = n-2m+1$ zeros in (before or after all ones or between two ones). Hence, the the number of ways to select $m$ nonconsecutive elements from $n$ consecutive integers where $m \leq \left\lfloor \frac{n+1}{2} \right\rfloor$ is $\binom{n-2m+1 + (m+1)-1}{(m+1)-1} = \binom{n-m+1}{m}$. Now, it's time for casework. When $k=1$, there are $15$ such $S$. When $k = 2$, there are $\binom{13}{2}$ such $S$. When $k = 3$, there are $\binom{11}{3}$ such $S$. When $k = 4$, there are $\binom{9}{4}$ such $S$. When $k = 5$, there are $\binom{7}{5}$ such $S$. In total, we get that there are $405$ such $S$.