0
$\begingroup$

If $10$ digit numbers are formed using all the digits $ 0,1,2,...,9$ such that they are divisible by $11111$ then the question is to find number of such numbers possible and the digit in the $10000^{th}$ place of largest number of such numbers.

I have not been taught number theory in school and have no idea on how to approach this problem.i tried by some hit and trial during exam but was not successful I would appreciate if someone could help me with this.Thanks.

$\endgroup$
  • 2
    $\begingroup$ Hint: try proving that any ten-digit number divisible by $11111$ of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ must have $a_i+b_i=9$ for each $i$. $\endgroup$ – JMoravitz May 9 '17 at 16:28
2
$\begingroup$

All numbers will be of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ where $a_i+b_i=9$ for all $i$ using each digit exactly once and each number of that form will satisfy your conditions. Proof below.

As such, by choosing $a_1$, the choice of $b_1$ is forced. Similarly choosing $a_2,a_3,a_4,a_5$ will force the choice for $b_2,b_3,b_4,b_5$.

Applying multiplication principle, and remembering that leading zeroes do not contribute to the number of digits of a number (e.g. $012349876$ does not count as a ten-digit number) we have $9$ options for $a_1$, $8$ options for $a_2$, $6$ options for $a_3$, $4$ options for $a_4$, and $2$ options for $a_5$.

There are then $9\cdot 8\cdot 6\cdot 4\cdot 2=3456$ ten digit numbers satisfying all of the desired properties.

The largest number of which is formed with the largest selections available for $a_1,a_2,\dots$ respectively and is then $9876501234$, the $10000$'s place being the $5$.



Lemma: Any ten digit number of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ is divisible by $11111$ if and only if $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ is divisible by $11111$.

$a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5\equiv (9\cdot 11111)a_1a_2a_3a_4a_5+a_1a_2a_3a_4a_5 + b_1b_2b_3b_4b_5$

$\equiv 10^5a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5\equiv a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5\pmod{11111}$


Claim: In the set of ten digits numbers using all digits $0$-$9$ the number is divisible by $11111$ if and only if it is of the form $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ where $a_i+b_i=9$ for all $i$.

$\Leftarrow)~~$ Suppose that $a_i+b_i=9$ for all $i$. Then $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5=99999$ is divisible by $11111$. Then by the lemma, so too is $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$.

$\Rightarrow)~~$ Suppose that $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ is a ten-digit number using all digits exactly once which is divisible by $11111$.

By the lemma, we know then that $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5=n\cdot 11111$ for some $n$.

As all digits are used exactly once, the sum of the digits is $1+2+\dots+9=\frac{9\cdot 10}{2}=45$. As this is divisible by $9$ both $a_1a_2a_3a_4a_5b_1b_2b_3b_4b_5$ and $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ must also be divisible by $9$. (see sum of digits of a number is equivalent modulo 9 to the number itself proof elsewhere).

As the digits are distinct $16047= 13579+02468\leq a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5\leq 97531+86420=183951$ as those selected numbers minimize and maximize the sums of the respective digit positions respectively. From this, we know then that $1\cdot 11111<a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5<17\cdot 11111$ so we know that $n\in \{2,3,\dots,16\}$.

As $11111$ is coprime to $9$, by chinese remainder theorem, we know then that $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ must be divisible by $9\cdot 11111=99999$. The only value then for $n$ which satisfies this is $n=9$ and therefore $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5=99999$

Now... if $a_i+b_i\neq 9$ for some $i$ then there must be some $a_j+b_j>9$ for some $j$ due to law of averages. The largest value of which is $9+8=17$, and the largest carryover for a specific digit place is $1$, which would result in a digit of $a_1a_2a_3a_4a_5+b_1b_2b_3b_4b_5$ being strictly less than $9$. It follows then that it must be that $a_i+b_i=9$ for all $i$.

$\endgroup$
  • $\begingroup$ Thanks for your answer.I will have to study elementary number theory to have a full grasp of your proof :) $\endgroup$ – Navin May 9 '17 at 18:54
0
$\begingroup$

Trick is tor realize adding or subtracting $11111$ will raise or lower $5$ consecutive digits. And to realize that $11111*11 = 122221$ and $11111*111 = 1233321$ etc. So...

consider $11111^2 = 123454321$.

Then notice that $11111^2 + 11111 = 123465432$

and $11111^2 + k*11111 = 1234(5+k)(4+k)(3+k)(2+k)(1+k)$.

So $11111^2 + 4*11111 = 123498765$

and so $10(11111^2 + 4*11111) = 1234987650$.

So $1234987650 = 11111*111150$

That's one answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.