Problem:
How many strings of length formed from the digits are there such that for each , at least of the digits are less than ? (For example, satisfies this condition because it contains at least digit less than , at least digits less than , at least digits less than , and at least digits less than . The string does not satisfy the condition because it does not contain at least digits less than .)
Answer Choices:
A.
B.
C.
D.
E.
Solution:
From the definition, any permutation of an acceptable string (a string satisfying the conditions of the problem) is acceptable. The following lists show the acceptable strings with the digits listed in nondecreasing order, based on the pattern of repeated digits. For example, pattern means that one digit occurs 3 times and each of two other digits appears once.
The number of different permutations of numbers in each list can be computed with multinomial coefficients.
Finally, the number of strings with a given pattern that meet the conditions is obtained by multiplying the number of instances of that pattern by the number of different permutations for that pattern. Thus there are
strings in all.
Replace 5 with a general value of , and think of the problem as asking for the number of base nonnegative integers, with leading zeros allowed, that meet the given condition-that for each , at least of the digits are less than . Temporarily extend the numbers to base , and consider all -digit numbers. These numbers can be divided into teams of size such that every set of -digit numbers of the form
forms a team, where addition of digits is done modulo . Imagine testing whether each team member meets the stated condition as follows. Starting with the first digit and continuing through the th digit, place the digits on a -hour clock face so that digit goes on hour if hour is empty. Otherwise digit goes on the next empty hour clockwise after . All digits fit, and one hour will be left empty. The teams are constructed so that the empty hour for each team member is one greater, modulo , than that of its predecessor, so exactly one team member will leave hour empty. The team member that leaves hour empty meets the stated condition because in order not to use hour it must have at least digits less than for each , and it must not contain digit . Team members that fill hour do so because for some they fail to meet the stated condition. They fail to have digits less than , that is, they have digits greater than or equal to . These digits fill hours through .
Each team has exactly one number that meets the stated condition, so the number of such numbers is
For the number is .
Note: This problem is related to the subject of parking functions. See sequence A000272 in the On-Line Encyclopedia of Integer Sequences. The idea of the second solution is attributed to Henry O. Pollak.
The problems on this page are the property of the MAA's American Mathematics Competitions