|
|
| 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 1 (Parking Functions) ==
| |
| − | For some <math>n</math>, let there be <math>n+1</math> parking spaces counterclockwise in a circle. Consider a string of <math>n</math> integers <math>c_1c_2 \cdots c_n</math> each between <math>0</math> and <math>n</math>, and let <math>n</math> cars come into this circle so that the <math>i</math>th car tries to park at spot <math>c_i</math>, but if it is already taken then it instead keeps going counterclockwise and takes the next avaliable spot. After this process, exactly one spot will remain empty.
| |
| − | | |
| − | Then the strings of <math>n</math> numbers between <math>0</math> and <math>n-1</math> that contain at least <math>k</math> integers <math><k</math> for <math>1 \leq k \leq n+1</math> are exactly the set of strings that leave spot <math>n</math> empty. Also note for any string <math>c_1c_2 \cdots c_n</math>, we can add <math>1</math> to each <math>c_i</math> (mod <math>n+1</math>) to shift the empty spot counterclockwise, meaning for each string there exists exactly one <math>j</math> with <math>0 \leq j \leq n</math> so that <math>(c_1+j)(c_2+j) \cdots (c_n+j)</math> leaves spot <math>n</math> empty. This gives there are <math>\frac{(n+1)^{n}}{n+1} = (n+1)^{n-1}</math> such strings.
| |
| − | | |
| − | Plugging in <math>n = 5</math> gives <math>\boxed{\textbf{(E) }1296}</math> such strings.
| |
| − | | |
| − | ~oh54321
| |
| − | | |
| − | ==Solution 2 (Casework)==
| |
| − | | |
| − | Note that a valid string must have at least one <math>0.</math>
| |
| − | | |
| − | We perform casework on the number of different digits such strings can have. For each string, we list the digits in ascending order, then consider permutations:
| |
| − | <ol style="margin-left: 1.5em;">
| |
| − | <li>The string has <math>1</math> different digit.</li><p>
| |
| − | The only possibility is <math>00000.</math> <p>
| |
| − | <b>There is <math>\boldsymbol{1}</math> string in this case.</b>
| |
| − | <li>The string has <math>2</math> different digits.</li><p>
| |
| − | We have the following table:
| |
| − | <cmath>\begin{array}{c||c|c|c|c||c}
| |
| − | & & & & & \\ [-2.5ex]
| |
| − | \textbf{Digits} & \boldsymbol{01} & \boldsymbol{02} & \boldsymbol{03} & \boldsymbol{04} & \textbf{Row's Count} \\ [0.5ex]
| |
| − | \hline
| |
| − | & & & & & \\ [-1.5ex]
| |
| − | & 00001 & 00002 & 00003 & 00004 & \hspace{2mm}4\cdot\frac{5!}{4!1!}=20 \\ [2ex]
| |
| − | & 00011 & 00022 & 00033 & & \hspace{2mm}3\cdot\frac{5!}{3!2!}=30 \\ [2ex]
| |
| − | & 00111 & 00222 & & & \hspace{2mm}2\cdot\frac{5!}{2!3!}=20 \\ [2ex]
| |
| − | & 01111 & & & & 1\cdot\frac{5!}{1!4!}=5 \\ [0.75ex]
| |
| − | \end{array}</cmath>
| |
| − | <b>There are <math>\boldsymbol{20+30+20+5=75}</math> strings in this case.</b>
| |
| − | <li>The string has <math>3</math> different digits.</li><p>
| |
| − | We have the following table:
| |
| − | <cmath>\begin{array}{c||c|c|c|c|c|c||c}
| |
| − | & & & & & & & \\ [-2.5ex]
| |
| − | \textbf{Digits} & \boldsymbol{012} & \boldsymbol{013} & \boldsymbol{014} & \boldsymbol{023} & \boldsymbol{024} & \boldsymbol{034} & \textbf{Row's Count} \\ [0.5ex]
| |
| − | \hline
| |
| − | & & & & & & & \\ [-1.5ex]
| |
| − | & 00012 & 00013 & 00014 & 00023 & 00024 & 00034 & \hspace{2mm}6\cdot\frac{5!}{3!1!1!}=120 \\ [2ex]
| |
| − | & 00112 & 00113 & 00114 & 00223 & 00224 & & \hspace{2mm}5\cdot\frac{5!}{2!2!1!}=150 \\ [2ex]
| |
| − | & 00122 & 00133 & & 00233 & & & 3\cdot\frac{5!}{2!1!2!}=90 \\ [2ex]
| |
| − | & 01112 & 01113 & 01114 & & & & 3\cdot\frac{5!}{1!3!1!}=60 \\ [2ex]
| |
| − | & 01122 & 01133 & & & & & 2\cdot\frac{5!}{1!2!2!}=60 \\ [2ex]
| |
| − | & 01222 & & & & & & 1\cdot\frac{5!}{1!1!3!}=20 \\ [0.75ex]
| |
| − | \end{array}</cmath>
| |
| − | <b>There are <math>\boldsymbol{120+150+90+60+60+20=500}</math> strings in this case.</b>
| |
| − | <li>The string has <math>4</math> different digits.</li><p>
| |
| − | We have the following table:
| |
| − | <cmath>\begin{array}{c||c|c|c|c}
| |
| − | & & & & \\ [-2.5ex]
| |
| − | \textbf{Digits} & \boldsymbol{0123} & \boldsymbol{0124} & \boldsymbol{0134} & \boldsymbol{0234} \\ [0.5ex]
| |
| − | \hline
| |
| − | & & & & \\ [-1.5ex]
| |
| − | & 00123 & 00124 & 00134 & 00234 \\ [2ex]
| |
| − | & 01123 & 01124 & 01134 & \\ [2ex]
| |
| − | & 01223 & 01224 & & \\ [2ex]
| |
| − | & 01233 & & & \\ [0.75ex]
| |
| − | \end{array}</cmath>
| |
| − | <b>There are <math>\boldsymbol{10\cdot\frac{5!}{2!1!1!1!}=600}</math> strings in this case.</b>
| |
| − | <li>The string has <math>5</math> different digits.</li><p>
| |
| − | <b>There are <math>\boldsymbol{5!=120}</math> strings in this case.</b>
| |
| − | </ol>
| |
| − | Together, the answer is <math>1+75+500+600+120=\boxed{\textbf{(E) }1296}.</math>
| |
| − | | |
| − | ~MRENTHUSIASM
| |
| − | | |
| − | ==Solution 3 (Recursive Equations Approach)==
| |
| − | | |
| − | 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 4 (Answer Choices)==
| |
| − | Let the set of all valid sequences be <math>S</math>.
| |
| − | Notice that for any sequence <math>\{a_1,a_2,a_3,a_4,a_5\}</math> in <math>S</math>, the sequences
| |
| − | <cmath>
| |
| − | \begin{align*}
| |
| − | \{a_2,a_3,a_4,a_5,a_1\}\\
| |
| − | \{a_3,a_4,a_5,a_1,a_2\}\\
| |
| − | \{a_4,a_5,a_1,a_2,a_3\}\\
| |
| − | \{a_5,a_1,a_2,a_3,a_4\}
| |
| − | \end{align*}
| |
| − | </cmath>
| |
| − | must also belong in <math>S</math>. However, one must consider the edge case all 5 elements are the same (only <math>\{0,0,0,0,0\}</math>), in which case all sequences listed are equivalent. Then <math>\lvert S \rvert \equiv 1 \pmod 5</math>, which yields <math>\boxed{\textbf{(E) }1296}</math> by inspection.
| |
| − | | |
| − | ~Tau
| |
| − | | |
| − | ==Video Solution==
| |
| − | https://youtu.be/130OKAfG_-o
| |
| − | | |
| − | ~MathProblemSolvingSkills.com
| |
| − | | |
| − | ==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 ==
| |
| − | | |
| − | {{AMC10 box|year=2022|ab=A|num-b=23|num-a=25}}
| |
| − | {{AMC12 box|year=2022|ab=A|num-b=23|num-a=25}}
| |
| − | | |
| − | [[Category:Intermediate Combinatorics Problems]]
| |
| − | {{MAA Notice}}
| |
