2023 AMC 12B Problems/Problem 8

Problem

How many nonempty subsets B of ${0, 1, 2, 3, \cdots, 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.

$\textbf{(A) } 256 \qquad\textbf{(B) } 136 \qquad\textbf{(C) } 108 \qquad\textbf{(D) } 144 \qquad\textbf{(E) } 156$

Solution 1

There is no way to have a set with 0. If a set is to have its lowest element as 1, it must have only 1 element: 1. If a set is to have its lowest element as 2, it must have 2, and the other element will be chosen from the natural numbers between 3 and 12, inclusive. To calculate this, we do $\binom{10}{1}$ . If the set is the have its lowest element as 3, the other 2 elements will be chosen from the natural numbers between 4 and 12, inclusive. To calculate this, we do $\binom{9}{2}$ . We can see a pattern emerge, where the top is decreasing by 1 and the bottom is increasing by 1. In other words, we have to add $1 + \binom{10}{1} + \binom{9}{2} + \binom{8}{3} + \binom{7}{4} + \binom{6}{5}$ . This is $1+10+36+56+35+6 = \boxed{144}$ .

~lprado

Page

Toolbox

Search

2023 AMC 12B Problems/Problem 8

Problem

Solution 1