Eugene David
...The One-Minute Pundit

Tuesday, February 28, 2006


The DUHHHHHHHHHHHHHHHHHHHHHHHHHHB thinks:

CASTING OUT NINES [John Derbyshire]

A bazillion emails on the dog puzzle. It's just a slightly dressed-up version of the old "casting out nines" technique.

THEOREM. Take any number X; jumble up its digits to get Y; subtract the lesser from the greater of X and Y; the answer is bound to be divisible by 9.
PROOF. Suppose the digits of the original number, in order, are A, B, C, D,... That means that the number is A times some power of ten, plus B times the next-lower power of ten, plus C times the next-lower power of ten, and so on. When you jumble up the digits to make a new number, this new number will **still** be A times some power of ten, plus B times some power of ten, plus... Only the powers are different! Subtracting gives you A times (some power of ten minus some other power of ten) plus B times (some power of ten minus some other power of ten) plus... But any power of ten minus any other power of ten gives you a number divisible by nine. ( E.g. 10,000 minus 10 gives you 9,990.) So the result of your subtraction must divide by 9.

So that 4-digit difference -- the result of your subtraction in step 2 of the dog puzzle -- is bound to be some multiple of 9. For illustration, I'll suppose it's 7524, which does indeed divide by 9.

Instead of removing your chosen digit D (I'll choose D=5) from that difference, just imagine replacing the digit D by a zero. Call the resulting 4-digit number N. In my example, N=7024.

Now, treat that final step -- jumbling the three remaining digits -- as jumbling up the **four** digits of N, but making sure the zero ends up at far left. (E.g. treat jumbling up 724 to get 247 as jumbling up N=7024 to get 0247.)

By my theorem, the 3-digit (ignoring the leading zero now) result of this jumble differs from N by some multiple of 9. (Yes it does: 7024 minus 247 equals 6777, which is 9 times 753.)

AND, it also differs by some multiple of 9 from the number you get if you jumble up N's digits to put the zero -- the one that replaced the mystery digit -- at the far right, units, position. So 247 doesn't just differ from 7024 by some multiple of 9, but also from 7420 likewise... which is some multiple of 9, minus D! (Yep: 247 differs from 7420 by 7173, which is 9 times 797. and 7420 is 9 times 825, minus 5.)

Armed with this understanding, divide that final, jumbled, 3-digit number by 9 and note the remainder R. R, plus the mystery digit D, must equal 9. So D is 9 minus R. (247 is 9 times 27, remainder 4. 4 plus 5 is 9.)

So all the dog program does is look at your final, jumbled-up three digits, divide by 9 to get the remainder, and subtract that remainder form 9. Note that the final, jumbled-up three digits can't divide EXACTLY by 9 (giving remainder zero), because then so would my "N," which would mean you hadn't removed a digit....

Posted at 01:22 PM

Home
Site Meter eXTReMe Tracker