Maths Olympiad Prep

Library / /54 of 120

Combinatorics Difficulty 5.5 AIME, harder Prove it Croatia

Prove that the sum of all three-digit numbers whose decimal representation consists of three different digits different from zero has at least three different prime divisors.

Solution

Let us consider all three-digit numbers whose digits are all different and nonzero. Each such number can be written as 100a+10b+c100a + 10b + c, where aa, bb, cc are digits from 11 to 99, all different.

The total number of such numbers is 9×8×7=5049 \times 8 \times 7 = 504.

Let SS be the sum of all such numbers.

Let us fix the digits aa, bb, cc in all possible orders. For each digit, it appears in each position (hundreds, tens, units) the same number of times, because the digits are permuted among the three positions.

For each digit dd (1d91 \leq d \leq 9), the number of ways to choose the other two digits is 8×7=568 \times 7 = 56, and for each such choice, dd appears in each position exactly 2!=22! = 2 times (since there are 3!=63! = 6 permutations, and for each position, 22 permutations place dd there).

So, for each digit dd, it appears 56×2=11256 \times 2 = 112 times in each position.

Therefore, the total sum is:

S=d=19112(100d+10d+d)=d=19112111d=112111d=19d S = \sum_{d=1}^9 112 \cdot (100d + 10d + d) = \sum_{d=1}^9 112 \cdot 111d = 112 \cdot 111 \cdot \sum_{d=1}^9 d

But d=19d=45\sum_{d=1}^9 d = 45.

So,
S=11211145 S = 112 \cdot 111 \cdot 45

Let us factor this number:

112=16×7=24×7112 = 16 \times 7 = 2^4 \times 7

111=3×37111 = 3 \times 37

45=5×9=5×3245 = 5 \times 9 = 5 \times 3^2

So,
S=(24×7)×(3×37)×(5×32) S = (2^4 \times 7) \times (3 \times 37) \times (5 \times 3^2)

Multiply the 33's:

3×32=333 \times 3^2 = 3^3

So,
S=24×33×5×7×37 S = 2^4 \times 3^3 \times 5 \times 7 \times 37

Thus, the prime divisors of SS are 22, 33, 55, 77, and 3737.

Therefore, the sum SS has at least three different prime divisors (in fact, it has five).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.