2022 AMC 12A Problems/Problem 24
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)