Number Theory Brain Teaser

Question

I just got this book of number brain teasers and this one is sort of interesting and giving me some difficulty.

Ask Joe to think of any positive integer. Tell Joe to scramble the digits of this integer to obtain another number and then subtract the smaller of the two from the larger. If the difference consists of at least two digits ask Joe to tell you all but one of these digits including all zeros, you can provide the missing digit! Explain.

So I believe I've made some progress on this problem because I know that any integer can be decomposed as follows:

$n = a_{0} + a_{1}*10 + a_{2}*100 \space + \space ... \space + \space a_{n}*10^n$

$n = 9*(a_{1} + 11*a_{2} + 111*a_{3} + 111…1*a{n}) \space + \space (a_{0} + a_{1} + \space … \space + \space a_{n})$

So we could let $a_{n} = s_{n} - t_{n}$ where $s$ was the larger integer. So that's my thoughts on the problem so far, but I know I'm far from a solution. Any help on understanding this problem would be appreciated!

Answer 1

Let $a$ be the starting number, and let $b$ be the scrambled number. Recall that any number is congruent modulo $9$ to the sum of its decimal digits. So if $D$ is the sum of the digits of $a$ (and therefore of $b$), we have $a\equiv D\equiv b\pmod{9}$, and therefore $|a-b|$ is divisible by $9$.

Now just calculate the sum $s$ of the digits we were given. The missing digit is the digit that needs to be added to $s$ to get a number divisible by $9$.

The only potential trouble could come if $s$ is divisible by $9$, because there are then two digits ($0$ and $9$) that could be added to it to get a result divisible by $9$. That's where the special rule we were given about $0$'s comes into play. Since we were given all the $0$'s, if $s\equiv 0\pmod{9}$ then the missing digit must be $9$.

Remark: The fact that a number is congruent modulo $9$ to the sum of its digits is not hard to prove. For consider the number $$A=a_n10^n+a_{n-1}10^{n-1}+\cdots +a_1 10^1 +a_0.$$ Since $10^k\equiv 1\pmod{9}$, it follows that $a_k10^k\equiv a_k\pmod{9}$. Thus $A\equiv a_n+a_{n-1}+\cdots +a_1+a_0\pmod{9}$.

Answer 2

More generally, let $\rm\,\hat n$ be obtained from $\rm\,n\,$ by deleting any digit $\rm\:d\ne 0.\:$ Then $\rm\,d\,$ can be determined from $\rm\:\color{#C00}{n\ mod\ 9}\,$ and $\rm\:\color{#0A0}{\hat n\ mod\ 9}.\:$ Indeed, by casting $9$s we know that, mod $9,$ $\rm\: n \equiv s(n),\:$ the sum of the digits of $\rm\:n,\:$ so $\rm\:\hat n\equiv s(n)-d.\:$ Thus $\rm\:d\equiv s(n)-(s(n)-d)\equiv (\color{#C00}{n\ mod\ 9})-(\color{#0A0}{\hat n\ mod\ 9}).\:$ This determines $\rm\,d\,$ uniquely since the only digits congruent mod $9$ are $0$ and $9,\,$ but we know $\rm\,d\ne 0$.

Your problem is a special case: your $\rm\,n\,$ is the difference of an integer $\rm\:m\:$ and an integer $\rm\:m'$ obtained by permuting the digits of $\rm\,m.\:$ They both have same digits so they have they same digit sums $\rm\:s(m') = s(m).\:$ Thus mod $\rm9\!:$ $\rm\ n = m-m'\equiv s(m)-s(m')\equiv 0,\:$ i.e. $\rm\:(\color{#C00}{n\ mod\ 9}) = 0.$ Further, you're given all the digits of $\rm\,\hat n\:$ so you know its digit sum $\rm\,s(\hat n)\:$ which gives you $\rm\,\color{#0A0}{\hat n\ mod\ 9}.$