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$.
Problem
Source: Pan African 2004
Tags: PAMO, 2004
tµtµ
04.10.2005 12:04
Number is greater than 10000, a permutation of it can be written $10^4*A + B$ where B is build with some permutation of 1,3,7,9, and $A \geq 0$ Mod 7, $r = 10^4*A$ is one of $0 ... 6$. If r = 6 then take B = 1793 If r = 5 then take B = 3719 If r = 4 then take B = 1739 If r = 3 then take B = 1397 If r = 2 then take B = 1937 If r = 1 then take B = 1973 If r = 0 then take B = 1379
gavinwkc
12.03.2006 06:55
Is there a faster way rather than guess and check for the combinations of 1379 for each of the possible r (0,1,2,3,4,5,6) ?
t0rajir0u
12.03.2006 08:20
$1, 3, 7, 9 \equiv 1, 3, 0, 2 \bmod 7$. These numbers make up the first half of the residue class $\bmod 7$, and note also that $10^0 \equiv 1 \bmod 7$ $10^1 \equiv 3 \bmod 7$ $10^2 \equiv 2 \bmod 7$ $10^3 \equiv 1 \bmod 7$ If I knew why it was so, I could say that a linear combination of these two residue classes should produce the entire residue class $\bmod 7$ (it makes sense to me), but I don't know why.
RockmanEX3
25.03.2020 00:59
There are two cases to consider based on the number of extra digits in the number we want to permute.
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 be $9317$ and keep inserting zeroes between the $1$ and $7$.
Case 2: Extra digits (if any) include at least one non-zero digit
Extra digits can be used to form a number greater than 0. Then proceed like in the solution from tµtµ.