Comments: Fido reads your mind

An hypothesis for anyone who wants to prove why fido works:

The difference is divisible by 9.

Posted by James Cloos at May 1, 2006 04:06 PM

Any permutation can be obtained from a sequence of swaps (mathematicians call them "inversions"). Each time you swap two digits, you add or subtract a multiple of 9.

Proof: Since the more significant digit decreases by the same amount as the increment of the less significant one. Let us call this amount x.
The difference is thus d=x*10^m-x*10^n where m>n denote the two positions.
By rearrangement, d=x*(10^(m-n)-1)*10^n where 10^(m-n)-1 is m-n 9 digits, thus divisible by 9 (the result of the division is m-n ones). Q.E.D.

The sum of the digits of a number that is divisible by 9 is also divisible by nine. Thus, if you tell all of them to Fido except the one you circled, which is not 0, exactly one of the nine remaining possibilities will result in a sum divisible by nine. Hence the mindreading.

Ain't math fun?

Posted by Daniel A. Nagy at May 1, 2006 05:37 PM

Hi Ian,

For some reason I cannot get to the site to post the solution as a comment, but here is the solution:

When you subtract a number and a permutation of that number from eachother, the result is always a multiple of 9. I will not give a proof, but try as much examples as you want to convince yourself.

This means that the sum of the digits of the result is a multiple of 9, as for each multiple of 9 the sum of the digits is also a multiple of 9.

By giving all but one of the digits, the flash script can calculate the digit needed to make the sum equal to a multiple of 9. For example when 560 is given, the sum for these digits is 11, so a 7 is needed to make a total of 18.

By excluding the 0 as a possibility, there is alway a unique solution: the only possiblity for a double solution would be when the sum of the digits without the circled one already is a multiple of 9. In that case adding a 0 or 9 would still result in a multiple of 9, but by excluding the 0 the script knows to choose the 9.


Edwin

Posted by Edwin at May 2, 2006 06:19 AM

Hi Ian,

Chose the number, call it a. Jumble it's digits, call the ensuing number b. substract the smaller, say a, from the larger, say b and call the difference c.

The digit sum should always be 9. If you drop a single digit from that digit sum, the missing digit is simply the complement to 9, e.g: say c = 3087 and you decide to drop the 3. Then the digit sum of the remaining digits is ds(15) = 6 and adding 3 complements the digit sum to 9, and this is the missing digit.

to compute a digit sum you simply keep adding up the digits of a number until you have a single digit, e.g: ds(12345) = ds(15) = 6


So the remaining problem is, why is the digit sum of the substraction always 9? Or stated otherwise, why is the difference always a multiple of 9? I leave that to the intrepid reader ;-)

Posted by gr, Twan at May 2, 2006 06:29 AM

Just got around to looking at this (I don't ordinarily have Flash, haven't found a plugin for Linux on PPC).

Anyway, a little thought will convince you that the difference must be a multiple of 9, and thus the sum of its digits must also be a multiple of 9. It's therefore easy to tell which digit is missing if given all the others. The only possible ambiguity is between 0 and 9, and you're told not to choose a 0 (and they can't all be 0's because you're told to choose a mix of different digits for your original number, and to mix them up to get a different number).

Likely somebody else has pointed this out already, but in case not...

Posted by Ray at May 17, 2006 05:28 AM
Post a comment









Remember personal info?






Hit Preview to see your comment.
MT::App::Comments=HASH(0x564cc5fd3c20) Subroutine MT::Blog::SUPER::site_url redefined at /home/iang/www/fc/cgi-bin/mt/lib/MT/Object.pm line 125.