Problem:
There are eight-digit positive integers that use each of the digits exactly once. Let be the number of these integers that are divisible by . Find the difference between and .
Solution:
We begin with an -digit number
which uses each of the digits exactly once. For to be divisible by , it must be divisible by both and .
Since divisibility by requires that the last digit is even, we know that
Next, we consider the divisibility by . The rule for tells us that
must be a multiple of . Noting that the total sum of the digits through is , the only possibility is that both sums are equal—that is,
In other words, the digits placed in the odd positions must add up to and so must those in the even positions. It turns out that there are exactly ways to split the set into two groups of digits each that sum to . Moreover, in each such partition, each group contains exactly even digits—a fact that becomes important when arranging the digits.
Once we have chosen a partition, the digits destined for the odd positions can be arranged in ways. For the even positions, while the digits can initially be arranged in ways, we must ensure that the last digit (position ) is even. Since each even-position group has even digits, we have choices for the digit in position , and the remaining digits can be arranged in ways. This gives us arrangements for the even positions.
Multiplying these together, each valid partition produces valid numbers. Since there are such partitions, the total number of -digit numbers divisible by is
Finally, the problem asks for the difference between this number and . Calculating,
Thus, the answer is .
The problems on this page are the property of the MAA's American Mathematics Competitions