How many $10-$digit numbers are divided by $11.111$ and all the digits are different

algebra-precalculuscontest-mathnatural numbersproblem solving

The Problem:

How many $10-$digit numbers are divided by $11.111$ and all the digits are different?

A) $3250$

B) $3456$

C) $3624$

D) $3842$

E) $4020$

The Problematic point is, "all digits must be different".

I could find only all $10-$ digit numbers.

$$999990000+11.111k≤9.999.999.999$$

$$1≤k≤810.009$$

The problem is, I have no method how can I calculate "all digits are different numbers."

Best Answer

If all digits are different, they must be all ten digits. In particular, the digit sum is $45$ and hence our number is a multiple of $9$. Thus we are in fact looking for certain multiples of $99999$. This reduces your $k$ range down to about $90000$ possibilities - still unfeasible do work out by hand.

If the ten digit number is $abcdefghij$, then after subtracting $99999\cdot abcde$ we still have a multiple of $99999$, namely $fghij+abcde$. As this sum is certainly $>0$ and $<99999+99999$, we conclude that $$fghij+abcde=99999.$$ In particular, $j+e=9$ without carry. Then also $i+d=9$ without carry, and so on. Thus the digit pairs $\{a,f\},\{b,g\},\{c,h\},\{d,i\},\{e,j\}$ must be the pairs $\{0,9\},\{1,8\},\{2,7\},\{3,6\},\{4,5\}$ in some order. There are $5!$ such permutations and then for each pair there are $2$ ways to match. This gives us $2^5\cdot 5!$ numbers of the desired form. However, among these are $2^4\cdot 4!$ where we attempt to set $a=0$ (and $f=9$), i.e., that are not really ten-digit numbers. Hence the final answer is $$2^5\cdot 5!-2^4\cdot 4! = 3456. $$