2023 AMC 12B Problem 8

Problem 8 of 25EasierCounting & Probability

How many nonempty subsets

B

of

\{0,1,2,3,\ldots,12\}

have the property that the number of elements in

B

is equal to the least element of

B?

For example,

B=\{4,6,8,11\}

satisfies the condition.

Show solution

Solution

If the least element is

m\ (m\ge 1),

then

|B|=m

and the remaining

m-1

elements come from

\{m+1,\ldots,12\},

a set of size

12-m.

The count is

\begin{aligned} \sum_{m\ge 1}\binom{12-m}{m-1} &=\binom{11}{0} \\ &\quad {}+\binom{10}{1} \\ &\quad {}+\binom{9}{2} \\ &\quad {}+\binom{8}{3} \\ &\quad {}+\binom{7}{4} \\ &\quad {}+\binom{6}{5}, \end{aligned}

which equals

1+10+36+56+35+6

=144.

Thus, the correct answer is D.

More practice

Concepts: combinations · casework

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.