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 , at least of the digits are less than ? (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 the number of -digit strings formed by using numbers , where for each , at least of the digits are less than .
We have the following recursive equation: and the boundary condition for any .
By solving this recursive equation, for and , we get
For and , we get
For and , we get
For and , we get
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)