2004 Pan African MO Problems/Problem 5

Revision as of 19:32, 25 March 2020 by Rockmanex3 (talk | contribs) (Solution to Problem 5 -- trial and error!)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Each of the digits $1$, $3$, $7$ and $9$ 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 $7$.

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 $1, 3, 9$ 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 $n \equiv 0 \pmod{7}$, then $10^k \cdot n \equiv 0 \pmod{7}$. After trial and error, we find that $931$ is divisible by 7, so we can let the permutation of a number with $k$ extra zeroes be $931\underbrace{00 \cdots 0}_{k \text{ zeroes}}7$.

Case 2: Extra digits include at least one non-zero digit

Let $n = A \cdot 10^4 + B$, where $B$ is a permutation of $1,3,7,9$ and, since $n$ has at least one extra non-zero digit, $A > 0$.


Note that $10^4 \equiv 4 \pmod{7}$, and by substituting each residue, we find that $10^4 \cdot A$ can be congruent to any residue modulo $7$ depending on the value of $A$. Thus, we need to find at least one value of $B$ that is congruent to each of $0,1,2, \cdots 6$ because for each value of $j$ from $0$ to $6$, $7-j$ 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 \begin{align*} 1379 &\equiv 0 \pmod{7} \\ 1793 &\equiv 1 \pmod{7} \\ 3719 &\equiv 2 \pmod{7} \\ 1739 &\equiv 3 \pmod{7} \\ 1397 &\equiv 4 \pmod{7} \\ 1937 &\equiv 5 \pmod{7} \\ 1973 &\equiv 6 \pmod{7}. \end{align*} Since we can find a permutation of $1,3,7,9$ that is congruent to any residue modulo 7, we can find a permutation of $n$ 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 $1,3,7,9$ such that the resulting integer is divisible by $7$.

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