Friday, April 19, 2013

multiple of 11

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Question: What are the smallest and largest multiples of 11 that are made up of the nine digits 1,2,3,4,5,6,7,8,9?

123456789
123456798
123456879
123456897
123457689
123457698
123457869
123457896
123457968
123457986
..................
..................
..................
987654312
987654321

Answer:

If $A=a_1a_2a_3a_4a_5a_6a_7a_8a_9$ is a multiple of 11, then we know the difference $(a_1+a_3+a_5+a_7+a_9)-(a_2+a_4+a_6+a_8)$ is also a multiple of 11, say $11x$.

Note that $a_1+a_2+\cdots+a_9=1+2+\cdots+9=45$ and hence $a_1+a_3+a_5+a_7+a_9=(45+11x)/2$ and $a_2+a_4+a_6+a_8=(45-11x)/2$.

Note that if $x=3$, then $a_2+a_4+a_6+a_8=6$ which is impossible. Likewise $x\ne -3$. Therefore $x$ can only be $1$ or $-1$.

Therefore either $a_1+a_3+a_5+a_7+a_9=28, a_2+a_4+a_8+a_9=17$ or $a_1+a_3+a_5+a_7+a_9=17, a_2+a_4+a_8+a_9=28$.

To get the smallest multiple of 11, we would like to see $A=12345\ldots$. Both $1+3+5+a_7+a_9=28$ and $1+3+5+a_7+a_9=17$ are impossible (the latter one is possible only if $\{a_7, a_9\}=\{2,6\}$ but we already have $a_2=6$.).

Try $A=1234\ldots$. Now $1+3+a_5+a_7+a_9=28$ is possible if $\{a_5,a_7,a_9\}=\{7,8,9\}$ (and so $\{a_6,a_8\}=\{5,6\}$) but $1+3+a_5+a_7+a_9=17$ is impossible. Therefore the smallest multiple of 11 is $A=123475869$.

To get the largest multiple of 11, we would like to see $A=98765\ldots$. Now $9+7+5+a_7+a_9=28$ is possible if $\{a_7,a_9\}=\{3,4\}$ (and so $\{a_6,a_8\}=\{1,2\}$). Thus the largest multiple of 11 is $A=987652413$.