Divisible by 99 ?

The first thing we note is that 1 + 2 + ... + 9 = 45 and as the sum of the digits is divisible by 9 then any arrangement of those digits will produce a number that is divisible by 9. So our challenge reduces to finding the smallest number that is divisible by 11.

To test if a number is divisible by 11 we find a, the sum of digits in the odd positions, and b, the sum of digits in the even positions.

For number 123456789, the first set,1, 3, 5, 7, 9, has sum 25 and the second set, 2, 4, 6, 8, has sum 20. As the difference is 5 we know that the number is not divisible by 11.

However, for the difference to increase from 5 to 11 we need to increase the sum of the first set by 3 and decrease the sum of the second set by 3. This can be achieved by swapping 1 and 4, 3 and 6, or 5 and 8.

Checking the combinations 123475869 is the smallest number divisible by 99.

My Way We need to use Diophantine equation to solve this problem and finally logical thinking is required on the final steps First, we make equations ABCDEFGHI is the number containing all 1 and 9 and distinct each other This number is automatically divisible by 9, so we have to analyse the divisibility of 11

${11}|{ABCDEFGHI} \Longrightarrow {11}| {((A + C + E + G +I) - (B + D + F +H))}$ or $(A + C + E + G + I) - (B + D + F + H) = 11k$

Suppose $A + C + E + G + I = P$ and $B + D + F + H = Q$

We know that

$P + Q = 45 \longrightarrow P = 45 - Q ... \boxed{1}$

We can also rewrite

$(A + C + E + G + I) - (B + D + F + H) = 11k \Longrightarrow P - Q = 11k \boxed{2}$

Substitute $\boxed{1} \rightarrow \boxed{2}$ $P - Q = 11k \Longrightarrow 45 - 2Q = 11k$

$\Longrightarrow 2Q + 11k = 45 \boxed{3}$

by modding both sides by 11, we get $2Q \equiv 1 (mod 11)$

$2Q \equiv 12 (mod 11)$

$Q \equiv 6 (mod 11) \Longrightarrow Q = 11u + 6 \boxed{4}$

Now substitute $\boxed{4}$ and $\boxed{1}$

$P = 45 - Q \Longrightarrow P = 45 - (11u + 6) = 45 - 11u -6$

$P = 39 - 11u$

Now, we play logic here! since we have $P + Q = 45$

$Q = 11u + 6$

$P = 39 - 11u$

It is easy to investigate the minimum value of $ABCDEFGHI$

case 1: $u = 0$ We get Q = 6 and P = 39

Look:

$Q = B + D + F +H$

$P = A + C + E + G + I$

We know the minimum value of Q is 10, since all of those numbers are differed each other and the maximum of Q is 30. We also know that the minimum and the maximum value of P is 15 and 35. This case is impossible since the value Q < 10 and P > 35. Hence, this case are crossed out

case 2: $u = 1$ We get Q = 17 and P = 28

Look again the case 0 description. This case fulls the condition, 17 is more than 10 but less than 30, and so does the P Now, we play logic

Since this is the smalles number, A must be 1, B must be 2, C must be 3 and D must be 4

After we find the value of A, B, C and D, let's evaluate the remaining P and Q so we can provide E, F, G, H and I

$Q = 2 + 4 + F + H = 17 \Longrightarrow F + H = 11$

$P = 1 + 3 + E + G + I = 28 \Longrightarrow E + G + I = 24$

We will find F and H first. The possible value for (F, H) is (2, 9) (3, 8) (4, 7) (5, 6) (6, 5) (7, 4) (8, 3) and (9,2). However, 1, 2, 3 and 4 have been used, so the only possible pairs are only (5, 6) and (6, 5). Since F < H, we will take (5, 6) : F = 5 and H = 6

We have found A = 1, B = 2, C = 3, D = 4, F = 5 and H = 6 The rest one for E, G and I are 7, 8 and 9. Since $7 + 8 + 9 = 24$ , there exist the E, G and I. Since E < G < I, E = 7, G = 8, I = 9

We order the number we've found: A = 1 B = 2 C = 3 D = 4 E = 7 F = 5 G = 8 H = 6 I = 9

We bond them and $ABCDEFGHI = 123475869$

I just wrote a C program to find all permutation and the first permutation which was divisible by 99 was the answer! :P

from itertools import *; S=list(permutations('123456789')); for s in S: if int(''.join(list(s)))%99 == 0: print s; break ;