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

Revision as of 04:32, 15 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$ .)

$\textbf{(A)} \, 500 \qquad\textbf{(B)} \, 625 \qquad\textbf{(C)} \, 1089 \qquad\textbf{(D)} \, 1199 \qquad\textbf{(E)} \, 1296$

Solution (Recursive equations approach)

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)

Solution 2 (Cheese)

Let the set of all valid sequences be $S$ . Notice that for any sequence $\{a_1,a_2,a_3,a_4,a_5\}$ in $S$ , the sequences $\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*}$ must also belong in $S$ . However, one must consider the edge case all 5 elements are the same (only $\{0,0,0,0,0\}$ ), in which case all sequences listed are equivalent. Then $\lvert S \rvert \equiv 1 \pmod 5$ , which yields $\boxed{\textbf{(E) 1296}}$ by inspection.

~Tau

Solution using parking functions

For some $n$ , let there be $n+1$ parking spaces counterclockwise in a circle. Consider a string of $n$ integers $c_1c_2 \cdots c_n$ each between $0$ and $n$ , and let $n$ cars come into this circle so that the $i$ th car tries to park at spot $c_i$ , 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 $n$ numbers between $0$ and $n-1$ that contain at least $k$ integers $<k$ for $1 \leq k \leq n+1$ are exactly the set of strings that leave spot $n$ empty. Also note for any string $c_1c_2 \cdots c_n$ , we can add $1$ to each $c_i$ (mod $n+1$ ) to shift the empty spot counterclockwise, meaning for each string there exists exactly one $j$ with $0 \leq j \leq n$ so that $(c_1+j)(c_2+j) \cdots (c_n+j)$ leaves spot $n$ empty. This gives there are $\frac{(n+1)^{n}}{n+1} = (n+1)^{n-1}$ such strings.

Plugging in $n = 5$ gives 1296 such strings.

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

@@ Line 93: / Line 93: @@
 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.
+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 \boxed{1296} such strings.
+Plugging in <math>n = 5</math> gives 1296 such strings.
 ==Video Solution==

2022 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 23	Followed by Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

2022 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 23	Followed by Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search