Problem 1024

Probably the easiest way to do this problem is to count how many non-empty subsets of $\{1,2, \ldots, n\}$ have $k$ elements and do contain the element $k$ for some $k$. The element $k$ must have $k-1$ other elements with it to be in a subset of $k$ elements, so there are $\binom{n-1}{k-1}$ such subsets. Now $\sum_{k=1}^{n}\binom{n-1}{k-1}=(1+1)^{n-1}=2^{n-1}$, so that is how many non-empty sets contain some $k$ and have $k$ elements. The set $\{1,2, \ldots, n\}$ has $2^{n}$ subsets (each element either is or is not in a particular subset), one of which is the empty set, so the number of non-empty subsets of $\{1,2,3,4,5,6,7,8\}$ have exactly $k$ elements and do not contain the element $k$ for some $k$ is $2^{n}-2^{n-1}-1=2^{n-1}-1$. In the case $n=8$, this yields $\mathbf{127}$.