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 20: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 $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 N(p,1)=i=0p1(pi)N(pi,0)=i=0p1(pi)=i=0p(pi)(pp)=2p1.

For $q = 2$ and $p \geq q$, we get N(p,2)=i=0p2(pi)N(pi,1)=i=0p2(pi)(2pi1)=i=0p(pi)(2pi1)i=p1p(pi)(2pi1)=i=0p((pi)1i2pi(pi)1i1pi)p=(1+2)p(1+1)pp=3p2pp.

For $q = 3$ and $p \geq q$, we get N(p,3)=i=0p3(pi)N(pi,2)=i=0p3(pi)(3pi2pi(pi))=i=0p(pi)(3pi2pi(pi))i=p2p(pi)(3pi2pi(pi))=i=0p((pi)1i3pi(pi)1i2pi(pi)(pi))32p(p1)=(1+3)p(1+2)pd(1+x)pdx|x=132p(p1)=4p3p2p1p32p(p1).

For $q = 4$ and $p = 5$, we get N(5,4)=i=01(5i)N(5i,3)=N(5,3)+5N(4,3)=(E) 1296.

~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)