Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2022 AMC 12A Problems/Problem 24"

(→‎Solution)
(→‎Solution)
Line 19: Line 19:
  
 
By solving this recursive equation, for <math>q = 1</math> and <math>p \geq q</math>, we get
 
By solving this recursive equation, for <math>q = 1</math> and <math>p \geq q</math>, we get
 +
<cmath>
 
\begin{align*}
 
\begin{align*}
 
N \left( p , 1 \right)
 
N \left( p , 1 \right)
Line 26: Line 27:
 
& = 2^p - 1 .
 
& = 2^p - 1 .
 
\end{align*}
 
\end{align*}
 +
</cmath>
  
 
For <math>q = 2</math> and <math>p \geq q</math>, we get
 
For <math>q = 2</math> and <math>p \geq q</math>, we get
 +
<cmath>
 
\begin{align*}
 
\begin{align*}
 
N \left( p , 2 \right)
 
N \left( p , 2 \right)
Line 39: Line 42:
 
& = 3^p - 2^p - p .
 
& = 3^p - 2^p - p .
 
\end{align*}
 
\end{align*}
 +
</cmath>
  
 
For <math>q = 3</math> and <math>p \geq q</math>, we get
 
For <math>q = 3</math> and <math>p \geq q</math>, we get
 +
<cmath>
 
\begin{align*}
 
\begin{align*}
 
N \left( p , 3 \right)
 
N \left( p , 3 \right)
Line 55: Line 60:
 
& = 4^p - 3^p - 2^{p-1} p - \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*}
 
\end{align*}
 +
</cmath>
  
 
For <math>q = 4</math> and <math>p = 5</math>, we get
 
For <math>q = 4</math> and <math>p = 5</math>, we get
 +
<cmath>
 
\begin{align*}
 
\begin{align*}
 
N \left( 5 , 4 \right)
 
N \left( 5 , 4 \right)
Line 63: Line 70:
 
& = \boxed{\textbf{(E) 1296}}  .
 
& = \boxed{\textbf{(E) 1296}}  .
 
\end{align*}
 
\end{align*}
 +
</cmath>
  
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Revision as of 20:43, 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 $j \in \{1,2,3,4\}$, at least $j$ of the digits are less than $j$? (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 $N \left( p, q \right)$ the number of $p$-digit strings formed by using numbers $0, 1, \cdots, q$, where for each $j \in \{1,2, \cdots , q\}$, at least $j$ of the digits are less than $j$.

We have the following recursive equation: \[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\] and the boundary condition $N \left( p, 0 \right) = 1$ for any $p \geq 0$.

By solving this recursive equation, for $q = 1$ and $p \geq q$, 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 $q = 2$ and $p \geq q$, 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 $q = 3$ and $p \geq q$, 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 $q = 4$ and $p = 5$, 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

https://youtu.be/mj78e_LnkX0

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_12A_Problems/Problem_24&oldid=180719"