Difference between revisions of "2022 AMC 12A Problems/Problem 24"
(Created page with "==Problem== How many strings of length 5 formed from the digits 0, 1, 2, 3, 4 are there such that for each <math>j \in \{1,2,3,4\}</math>, at least <math>j</math> of the digi...") |
(→Solution) |
||
Line 12: | Line 12: | ||
We have the following recursive equation: | We have the following recursive equation: | ||
− | + | <cmath> | |
N \left( p, q \right) | N \left( p, q \right) | ||
= \sum_{i = 0}^{p - q} \binom{p}{i} N \left( p - i, q - 1 \right) , \ \forall \ p \geq q \mbox{ and } q \geq 1 | = \sum_{i = 0}^{p - q} \binom{p}{i} N \left( p - i, q - 1 \right) , \ \forall \ p \geq q \mbox{ and } q \geq 1 | ||
− | + | </cmath> | |
and the boundary condition <math>N \left( p, 0 \right) = 1</math> for any <math>p \geq 0</math>. | and the boundary condition <math>N \left( p, 0 \right) = 1</math> for any <math>p \geq 0</math>. | ||
Revision as of 21:41, 11 November 2022
Problem
How many strings of length 5 formed from the digits 0, 1, 2, 3, 4 are there such that for each , at least
of the digits are less than
? (For example, 02214 satisfies this condition
because it contains at least 1 digit less than 1, at least 2 digits less than 2, at least 3 digits less
than 3, and at least 4 digits less than 4. The string 23404 does not satisfy the condition because it
does not contain at least 2 digits less than 2.)
Solution
Denote by the number of
-digit strings formed by using numbers
, where for each
, at least
of the digits are less than
.
We have the following recursive equation:
and the boundary condition
for any
.
By solving this recursive equation, for and
, we get
\begin{align*}
N \left( p , 1 \right)
& = \sum_{i = 0}^{p - 1} \binom{p}{i} N \left( p - i, 0 \right) \\
& = \sum_{i = 0}^{p - 1} \binom{p}{i} \\
& = \sum_{i = 0}^p \binom{p}{i} - \binom{p}{p} \\
& = 2^p - 1 .
\end{align*}
For and
, we get
\begin{align*}
N \left( p , 2 \right)
& = \sum_{i = 0}^{p - 2} \binom{p}{i} N \left( p - i, 1 \right) \\
& = \sum_{i = 0}^{p - 2} \binom{p}{i} \left( 2^{p - i} - 1 \right) \\
& = \sum_{i = 0}^p \binom{p}{i} \left( 2^{p - i} - 1 \right)
- \sum_{i = p - 1}^p \binom{p}{i} \left( 2^{p - i} - 1 \right) \\
& = \sum_{i = 0}^p \left( \binom{p}{i} 1^i 2^{p - i} - \binom{p}{i} 1^i 1^{p - i} \right)
- p \\
& = \left( 1 + 2 \right)^p - \left( 1 + 1 \right)^p - p \\
& = 3^p - 2^p - p .
\end{align*}
For and
, we get
\begin{align*}
N \left( p , 3 \right)
& = \sum_{i = 0}^{p - 3} \binom{p}{i} N \left( p - i, 2 \right) \\
& = \sum_{i = 0}^{p - 3} \binom{p}{i} \left( 3^{p - i} - 2^{p - i} - \left( p - i \right) \right) \\
& = \sum_{i = 0}^p \binom{p}{i} \left( 3^{p - i} - 2^{p - i} - \left( p - i \right) \right)
- \sum_{i = p - 2}^p \binom{p}{i} \left( 3^{p - i} - 2^{p - i} - \left( p - i \right) \right) \\
& = \sum_{i = 0}^p \left( \binom{p}{i} 1^i 3^{p - i} - \binom{p}{i} 1^i 2^{p - i}
- \binom{p}{i} \left( p - i \right) \right)
- \frac{3}{2} p \left( p - 1 \right) \\
& = \left( 1 + 3 \right)^p - \left( 1 + 2 \right)^p
- \frac{d \left( 1 + x \right)^p}{dx} \bigg|_{x = 1}
- \frac{3}{2} p \left( p - 1 \right) \\
& = 4^p - 3^p - 2^{p-1} p - \frac{3}{2} p \left( p - 1 \right) .
\end{align*}
For and
, we get
\begin{align*}
N \left( 5 , 4 \right)
& = \sum_{i = 0}^1 \binom{5}{i} N \left( 5 - i , 3 \right) \\
& = N \left( 5 , 3 \right) + 5 N \left( 4 , 3 \right) \\
& = \boxed{\textbf{(E) 1296}} .
\end{align*}
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)