Difference between revisions of "2023 AMC 12B Problems/Problem 8"

m (Problem)
 
Line 1: Line 1:
 
==Problem==
 
==Problem==
How many nonempty subsets <math>B</math> of <math>{0, 1, 2, 3, \cdots, 12}</math> have the property that the number of elements in <math>B</math> is equal to the least element of <math>B</math>? For example, <math>B = {4, 6, 8, 11}</math> satisfies the condition.
+
How many nonempty subsets <math>B</math> of <math>\{0, 1, 2, 3, \cdots, 12\}</math> have the property that the number of elements in <math>B</math> is equal to the least element of <math>B</math>? For example, <math>B = \{4, 6, 8, 11\}</math> satisfies the condition.
  
 
<math>\textbf{(A) } 256 \qquad\textbf{(B) } 136 \qquad\textbf{(C) } 108 \qquad\textbf{(D) } 144 \qquad\textbf{(E) } 156</math>
 
<math>\textbf{(A) } 256 \qquad\textbf{(B) } 136 \qquad\textbf{(C) } 108 \qquad\textbf{(D) } 144 \qquad\textbf{(E) } 156</math>

Latest revision as of 18:51, 13 April 2024

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{\textbf{(D) 144}}$.

~lprado

Note:

In general, i.e. when the number is not $13$, the answer is $F_{n-1}$. -Mr Sharkman

Video Solution

https://youtu.be/r9HCzaxLNlc

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)


See Also

2023 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 7
Followed by
Problem 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png