2023 AMC 12B Problem 8

Question

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.

256

136

108

144

156

If the least element is

m,

then

B

has exactly

m

elements, all at least

m

Choose the other

m-1

elements from the

12-m

integers greater than

m:

this gives

\binom{12-m}{m-1}

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.

Problem 8 in other years