A ten digit number is formed by using the numbers between $0$ and $9$ without repetition. If the number formed is divisible by $11111$. Find the greatest and smallest such number.
I tried very hard but couldn't device any way to solve this problem. Please help.
The only thing I could conclude is that the sum of digits of the the number formed will be $45$. It is a factor of $9$. So the number will be divisible by $9$. As we know that if any number $N$ is divisible by $a$ and $b$ and if $a$ and $b$ are co-primes, then the number is divisible by $a\cdot{b}$. So the factor of that number is $99999$. How to proceed further?
Best Answer
An interesting observation is that 100000 = 9 * 11111 + 1 which is to say that 100000 is congruent to 1 modulo 11111. This means that you can always switch the first and second half of your number without changing its divisibility by 11111. You can sum both its part and check if that is divisible by 11111. A good idea is to look at a simpler case, let's say your number has 4 different digits from 0 to 3, and you want the bigger and smaller one that you can divide by 11. Then the sum of your two 2 digits number has to be 11, 22, 33, 44, 55, 66, or 77. Among those numbers, you can only achieve 33. The highest and lowest number associated with that are 3201 and 0132 respectively. I will try to generalize to higher dimension and edit this answer.
Edit : Intuition makes me think that the lowest and highest number are 0123498765 and 9876501234 respectively.
Edit 2 : Ok, I thought of a way to prove this. If a number that obeys the rule is higher than 9876501234, it has to have the same five first digits, therefore, we can only look at the 5 last digit. 5 + 0, 1, 2, 3 or 4 gives you 5, 6, 7, 8 or 9, which means the multiple of 11111 we're looking for (by summing the first and last part) must ends with one of those numbers. Those multiple of 11111 always have all digits equal except maybe the last one and first one. As a result, let's call $x_0, ... , x_4$ those last five digits, we have $x_0 + 9- \epsilon [10] = x_1 + 8 [10] = ... = x_4 + 5 - \epsilon [10]$ where $\epsilon$ is either 0 or 1. The only possibility there is that $x_i$=9-i. This is enough to prove that 9876501234 is the highest number with such a property. The same reasoning works for the smallest number as well.
Edit 3 : Some Clarifications. To think more clearly of this, when you sum the first part and the second part of your number, you get a number between 99999 and 139999. Which means the only multiple of 11111 you have to check for are 99999, 111110, 122221, 133332. From there, we just need to check that only 99999 can be attained.
Edit 4 : We can check that by computing 11111 * i - 98765 for i in range(9, 13)(13 exluded), this gives 01234, 12345, 23456, 34567 and only the first one can be made using only digits from 0 to 4.