2004 Pan African MO Problems/Problem 5
Problem
Each of the digits , , and occurs at least once in the decimal representation of some positive integers. Prove that one can permute the digits of this integer such that the resulting integer is divisible by .
Solution
There are two cases to consider — one where the additional digits are either none or only zeroes, and one where the additional digits has at least one non-zero digit.
Case 1: Extra digits (if any) are only zeroes
Essentially, we want a permutation of digits that is divisible by 7. That way, we can "insert the zeroes" between said permutation and 7 to also get a number divisible by 7 because if , then . After trial and error, we find that is divisible by 7, so we can let the permutation of a number with extra zeroes be .
Case 2: Extra digits include at least one non-zero digit
Let , where is a permutation of and, since has at least one extra non-zero digit, .
Note that , and by substituting each residue, we find that can be congruent to any residue modulo depending on the value of . Thus, we need to find at least one value of that is congruent to each of because for each value of from to , results in a different residue modulo 7.
There are only 24 permutations, so we can test out each permutation by staying organized. After some lengthy trial-and-error, we find that
Since we can find a permutation of that is congruent to any residue modulo 7, we can find a permutation of that is divisible by 7.
Therefore, from both cases, one can permute the digits of an integer that contains at least one of each digit such that the resulting integer is divisible by .
See Also
2004 Pan African MO (Problems) | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All Pan African MO Problems and Solutions |