LateNightHacking Louis Journal

Auth

Today's bit of fun: the Fido Puzzle. Try it! It's one of those where you chose a number, do some math on it, and the computer tells you what you picked. Scott sent this around today, and asked if anyone could figure out how it was done. The gauntlet had been thrown down.

The game goes like this. First you pick a three of four digit number (actually, any number of digits will work). Then you reorder those digits randomly to make a second number. Next you subtract the smaller from the larger (and that order only keeps the pesky minus sign from appearing and confusing people) to produce a third number. Now, you choose any one of the digits of the third number, but the digit may not be zero (this turns out to be important). Tell the computer the remaining digits, and it can tell you what digit you chose. But how?

˜ ™

The reason it works is that the sum of the digits of the third number must be nine (or zero). (By sum of the digits, I mean add the digits together, and if you get a multiple digit result add them together again until you finally get a one digit number. Ignore the leading minus sign if there is one.) The number you picked, plus the numbers you didn't pick (and thus gave to the computer) must add to nine, so it's easy for the computer to tell what that number is. The only problem is if the unchosen digits add to nine. Then you could have picked a nine or a zero, since digitsum(9 + 0) = digitsum(9) = 9 and digitsum(9 + 9) = digitsum(18) = 9. Since you are not allowed to pick zero, you must have picked a nine. Of course, if you pick your inital numbers poorly, you can get a third number which is all zeros and you are in trouble.

But how do we know that the third number has a digit sum of nine? Lets say you pick a four digit number, abcd. Now you jumble the numbers dbac and subtract. What does that give you? Well, we can actually look at it one digit at a time. In our example, we have (a*1000-a*10) + (b*100-b*100) + (c*10-c*1) + (d*1000+d*1). In general, for one digit, we have a*10m-a*10n = a(10m-10n). This has interesting properties:

Theorem 1: Prove a(10m-10n) = a*x*9 where x is an integer.
Notice
    10m-10n = s*(10q-1)*10p
where
    s is { 1 if m>=n, -1 if m<n } (that is, the sign)
    p is min(m,n) (that is, the exponent of the greatest common factor of 10m and 10n)
    q is abs(m-n) (that is, the exponend of remainder after division by the GCF)
Notice
    10q-1
is either
    0 if q is zero, or else
    a bunch of nines (101-1 = 10-1 = 9, 102-1 = 100-1 = 99, 103-1 = 1000-1 = 99, etc.)
so we can say
    10q-1 = y*9
where
    y is {0, 1, 11, 111, ...}.
so the whole thing is
    s*(10q-1)*10p = s*(y*9)*10p = x*9
where
    x is s*y*10p.
thus
    a(10m-10n) = a*x*9
[Proven]

Theorem 2: Prove n is an integer implies digitsum(n*9)=9 (or) digitsum(n*9)=0.

Lema 1: Prove digitsum(m)=9|0 -> digitsum(m+9)=9|0
    Represent the digits in a number as so: dn ... d2 d1 d0
case d0 = 0
    dn ... d1 0 + 9 -> dn ... d1 9
case d0 != 0
    dn ... d2 d1 d0 + 9 = dn ... d2 d1+1 d0-1 and digitsum still = 9
        note that if d1=9, -> d2+1 d1-9 and digitsum(d2+1 d1-9) = (digitsum(d2 d1)+1)%9
[Proved]
Yes, there is handwaving here, but I'm sure this is going in the right direction.

Proof by induction:
Base case: n=0
    digitsum(0)=9|0, by inspection.
Induction step: prove that if it is true for n it is true for n+1:
    digitsum(n*9)=9|0
-> {by Lema1}
    digitsum((n*9)+9)=9|0
->
    digitsum((n+1)*9)=9|0
The base case and the induction step have both been proved.
[Proved]
Thanks to Dan Tull for collaboration on these proofs.

˜ ™

I talked to Dan Cleary today at the end of the day, and we agreed that our team is in danger of losing our momentum. Without John, we don't really have an internal driving force any more. I can't really provide it - I'm a dev! I'm interested in satisfying the customer and writing better code. Financial chicanery is not my forte. Unfortunately, we haven't gotten any clear requirements from our customers recently either. They're more or less happy. Now, you'd think this would be a good thing. However, it's hard to argue for salary and bonuses when you can't show your customer you've given them something they really needed. This just means we're going to have to get more organized and dig harder to make sure we know what it is our customer, the fund, needs so we can provide it. There are certainly plenty of tasks to do. There's a huge laundry list. But unless we get it organized and focuses, it'll be hard to energize the team and impress the boss.

˜ ™

One last thing: The Royal Journal Of Found Art. The have a picture of the amazing Three Armed Princess.