Thursday 23 October 2014

problem solving - Divisibility Rule Proof about Special Numbers




A positive integer's known as a special number if the digits of the number produce a purely growing sequence. Alternatively, 5659 isn't a special number. Same goes for the number 5669. Show that there aren't any 5-digit special numbers that are divisible by 11.



To show that this, I focused on the last digits of the numbers and identified a cycle. My proof:



"To prove that there are no five-digit special numbers divisible by 11, we first need to find the first five-digit number divisible by 11.
11*910 = 10010
As seen above, the first five-digit number divisible by 11 is 10010. Now, we need to list all the possible last two digits of all the five-digit numbers divisible by 11 in order to find a repeating cycle of the last two digits:
enter image description here



Key: The yellow highlight represents the last two digits of the numbers. Sequences of digits that are circled in pink are numbers where the last two digits are increasing, but the digit before causes the number to not be increasing. Sequences of digits that are circled in purple are numbers where the last two digits cause the number to not be increasing as it repeats. Sequences of digits that are circled in green colour are there to show that the last two digits return to the beginning of the cycle and to show where all the possibilities of the last two digits terminate. Digits that are written in dark green are the third digits of the five-digit numbers divisible by 11. Sequences of digits that are left plain are numbers where the last two digits are not increasing, resulting in the entire number not being increasing.




In the picture above, it is seen that plain sequences of digits (ones without circles) prevent the five-digit number divisible by 11 from being a special number as the last two digits are not increasing. Sequences of digits that are circled in pink prevent the five-digit number divisible by 11 from being a special number as the third digit of the five digit divisible by 11 (written in green) is larger than the following digits. Sequences of digits that are circled in purple prevent the five-digit number divisible by 11 from being a special number as the last two digits repeat. Therefore, it has been proven that all possible last two digits of all the five-digit divisible by 11 prevent the overall number from being a special number. (Read text circled in orange). This, in turn, proves that no five-digit number divisible by 11 is a special number."



However, I don't know if this is convincing enough as it doesn't use the divisibility rule of 11 in the proof. Any help on finding another proof using the divisibility rule of 11 would be extremely appreciated.



Thanks :)


Answer



Suppose $$abcde$$ is special and divisble by $11$. Then, the number $$a+c+e-b-d$$ must be divisible by $11$ The number $a+c+e-b-d$ must be positive because of $e>d$ and $c>b$



The maximum sum $a+c+e$ is given by $a=5$ , $c=7$ , $e=9$ , being smaller than $22$.




Hence, we must have $$e=(b-a)+(d-c)+11$$ This is obviously impossible because of $b>a$ and $d>c$


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...