'Fido'

A friend emailed this to me and I thought it was a nice change from the garden problems ;)

http://digicc.com/fido/

The question is: how does it work and why?

PS. I do have the proof if needed.

I don't have solid proof, but using simple method of observation i noticed, that no matter what numbers you pick, the sum of digits of result that you get by substracting smaller number from biger one is 18. this cant get any easier from this point. lets say you take out some digit, in order to find it, the programm substracts the sum of the digits that are left from 18, and you get the digit that you just took out. simply put:

ABCD>BCDA

ABCD-BCDA=ZXY

Z+X+Y=18 (always!!!)

lets say we take out X

Z+Y=18-X

in other words

18-(Z+Y)=X

That is simple as that ;)

example:

7359-5793=1566
1+5+6+6=18

lets take out 5 and we get 166 (or 1+6+6)

1+6+6=13
18-13=5

we got the number that we took out....simple, isn't it? ;)

It's all about the "don't pick zero"...
I can proove it using mods, but if u don't know them replace '=x(mod 9)' with 'leaves a remainder of x when divided by 9"

ok, say ur origional number is 'abcd'. Now, 'abcd' = (a+b+c+d) mod 9

And, any arrangement will be also (a+b+c+d) mod 9
("cbad" = (c+b+a+d) = (a+b+c+d) mod 9)

so, "cbad" - "abcd" = 0(mod 9) as p-p = 0(mod 9) always

=> ur resultant number must be a multiple of 9.
let the digits in ur resultant number be 'wxyz'. Now lets say you remove x. (x!=0)
then they know w+y+z (cos thats what u typed), => they work out what number needs to be added to get a multiple of 9. There is only one way for each (w+y+z) to do this, except if x can be 0 or 9. however, you can't cross out 0, so it has to be 9.
=> they work out, from ur input, what digit has to be added to make the digit sum a multiple of 9...tada!

As i said, i didn't have any solid proof. Just an observation, but comparing my solution to yours it's evident that one supports another.

One thing tho -
you are saying that they're working out the digit that will make a number which is multiple of 9, but you forgot to mention - the SMALLEST number which is multiple of 9. It happens that the smallest will be 18 ;) always 18 and only 18 :D :D :D :D

There is one saying: first time - accident, second time - coincidence, third time - rule (law) :)

Of course there is more credible proof for that solution than playing the game of observations, but i don't know it.

I like the puzzle, but how does it relate to 7-Up?

Actually, it's not always 18, but it is always a multiple of 9 (look at the example provided in the problem itself; it adds up to 9, not 18 ;)). sql_lall is right about the mod's, and the attached is how I proved it.

When you subtract a smaller number from a larger one, sometimes it is neccessary to perform a carryover event.
A carryover event always produces a multiple of 9 in the summation of the digits, because it is a series of subtracting 1 from one digit of the number, and adding 10 to its following digit.

So that, if we had AB, after a carryover event we'd have:

{A-1}{B+10}. So comparying the summations of the digits of the number before the carryover, and after, we'd see that:
AB==> A+B
{A-1}{B+10}==> A+B+9

With Numbers that have Digit counts greater than 2, the summation after carryover events have occured would be:
{A+B+C+D+...+ Z + n*9}

So, given 2 numbers, K and L, where K = A₀A₁A₂A₃, and L is a permutation of K's digits, and L < K, then the sum of the digits of the result of subtracting L from K is equivalent to the sum of the digits of K plus the sum of the carryovers, minus the sum of the digits of L.
And since the digits of L are identical to the digits of K, then you are left with the sum of the carryover, which is 9*n.

-Lou

Right, who here is sets the Qs for topcoder?
I liked the SRM 168 Question 2 Div 2:

Select two numbers between 1 and 9998, inclusive, which have the same exact group of non-zero digits, but are not the same number. For example, you could use 1234 and 4321, or 91 and 901. Now, subtract the smaller of the two numbers from the larger. Finally, pick one of the non-zero digits in the result, and remove the digit from the number. If the resulting number is less than 100, prepend enough zeros so that it has 3 digits. It turns out, that given the remaining 3 digits, one can always determine the digit removed. (See examples for clarification)
You will be given a string leftOver, which contains the three digits left over after the above algorithm is run. You must return the digit which was removed.

Sound AWEFULLY familiar?
495.43 points...unlucky that i couldn't do the actual comp, was at school....