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

(Solution 2 (Cheese))
(Redirected page to 2022 AMC 10A Problems/Problem 24)
(Tag: New redirect)
 
(32 intermediate revisions by 7 users not shown)
Line 1: Line 1:
==Problem==
+
#redirect [[2022 AMC 10A Problems/Problem 24]]
 
 
How many strings of length <math>5</math> formed from the digits <math>0</math>, <math>1</math>, <math>2</math>, <math>3</math>, <math>4</math> are there such that for each <math>j \in \{1,2,3,4\}</math>, at least <math>j</math> of the digits are less than <math>j</math>? (For example, <math>02214</math> satisfies this condition
 
because it contains at least <math>1</math> digit less than <math>1</math>, at least <math>2</math> digits less than <math>2</math>, at least <math>3</math> digits less
 
than <math>3</math>, and at least <math>4</math> digits less than <math>4</math>. The string <math>23404</math> does not satisfy the condition because it
 
does not contain at least <math>2</math> digits less than <math>2</math>.)
 
 
 
<math>\textbf{(A)} \, 500 \qquad\textbf{(B)} \, 625 \qquad\textbf{(C)} \, 1089 \qquad\textbf{(D)} \, 1199  \qquad\textbf{(E)} \, 1296 </math>
 
 
 
==Solution==
 
 
 
Denote by <math>N \left( p, q \right)</math> the number of <math>p</math>-digit strings formed by using numbers <math>0, 1, \cdots, q</math>, where for each <math>j \in \{1,2, \cdots , q\}</math>, at least <math>j</math> of the digits are less than <math>j</math>.
 
 
 
We have the following recursive equation:
 
<cmath>
 
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
 
</cmath>
 
and the boundary condition <math>N \left( p, 0 \right) = 1</math> for any <math>p \geq 0</math>.
 
 
 
By solving this recursive equation, for <math>q = 1</math> and <math>p \geq q</math>, we get
 
<cmath>
 
\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*}
 
</cmath>
 
 
 
For <math>q = 2</math> and <math>p \geq q</math>, we get
 
<cmath>
 
\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*}
 
</cmath>
 
 
 
For <math>q = 3</math> and <math>p \geq q</math>, we get
 
<cmath>
 
\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*}
 
</cmath>
 
 
 
For <math>q = 4</math> and <math>p = 5</math>, we get
 
<cmath>
 
\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*}
 
</cmath>
 
 
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
 
 
==Solution 2 (Cheese)==
 
Let the set of all valid sequences be <math>S</math>.
 
Notice that for any sequence <math>\{a,b,c,d,e\}</math> in <math>S</math>, the sequences
 
<cmath>
 
\begin{align*}
 
\{b,c,d,e,a\}\\
 
\{c,d,e,a,b\}\\
 
\{d,e,a,b,c\}\\
 
\{e,a,b,c,d\}
 
\end{align*}
 
</cmath>
 
must also belong in <math>S</math>. The only exception is when all 5 elements are the same, i.e. <math>\{0,0,0,0,0\}</math>. Then <math>\lvert S \rvert \equiv 1  \pmod 5</math>, which by inspection of the answer choices yields <math>\boxed{(E) 1296}</math>.
 
 
 
~Tau
 
 
 
== Video Solution By ThePuzzlr ==
 
https://youtu.be/qWIYzgqgCNg
 
 
 
~ MathIsChess
 
 
 
==Video Solution==
 
 
 
https://youtu.be/mj78e_LnkX0
 
 
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
 
 
== Video Solution By OmegaLearn using Complementary Counting ==
 
 
 
https://youtu.be/jWoxFT8hRn8
 
 
 
~ pi_is_3.14
 
 
 
== See Also ==
 
 
 
{{AMC12 box|year=2022|ab=A|num-b=23|num-a=25}}
 
{{AMC10 box|year=2022|ab=A|num-b=23|num-a=25}}
 
{{MAA Notice}}
 

Latest revision as of 09:52, 5 December 2022