very OT but how's it done 657

On Sat, 27 May 2006, graham

Well, it's exactly what i said in my post, for starters.

*preens*

*is still incomprehensible*

Okay, let me try. I'm very bad at explaining stuff, though ...

You have to think back, way back, to infant school, where you learnt about positional notation, ie hundreds, tens and units. Ie, when you have a number, like 216, what you've got is, first, the number of hundreds, then the number of tens, then the number of ones (or 'units', as the mathematicians call them). So, two hundreds, one ten and 6 ones make 216.

Another way of writing this is as a polynomial; a polynomial is a big sum, which consists of pairs of numbers (called terms, i think) which get multiplied together, with the results being added up, and specifically, one where the right-hand number in each pair is a power of some particular number, called the base (the number it's raised to is the exponent); the left-hand number is the coefficient. So, the polynomial with base 2 and coefficients 5 and 7 is:

5 * 2^1 + 7 * 2^0 ^ ^ ^ ^ ^ ^ +- exponent +--- base } second term +------- coefficient +----------- exponent +------------- base } first term +----------------- coefficient

* is multiplication here, and ^ means 'to the power of'. The value of this is 17, since 2^0 is 1.

The point is that a base-10 number is just a compact way of writing a polynomial; the base is 10, and the coefficients of the terms are the digits of the number, eg:

216 = 2 * 10^2 + 1 * 10^1 + 6 * 10^0

The nifty thing is that you can use this way of thinking to talk about arbitrary digit strings; a three-digit number 'abc' is:

a * 10^2 + b * 10^1 + c * 10^0

eg 216 is:

2 * 10^2 + b * 10^1 + c * 10^0

Really, 10^2 just means 'hundreds', 10^1 'tens' and 10^0 'units'.

That may look like an incredibly complicated way of looking at it, but it does something very powerful: it turns a digit string, which is something you can't analyse with algebra, into an expression, which is something you can. It's the key that lets you apply the whole of maths to problems of digit strings.

So, looking at two-digit numbers, you can work out that 'ab' - 'ba' looks like:

'ab' = a * 10^1 + b * 10^0 'ba' = b * 10^1 + a * 10^0

You can simplify that a bit by evaluating the powers:

'ab' = a * 10 + b * 1 'ba' = b * 10 + a * 1

Or even:

'ab' = a * 10 + b 'ba' = b * 10 + a

You can then do algebra:

'ab' - 'ba' = (a * 10 + b) - (b * 10 + a) = (a * 10) + b - (b * 10) - a = (a * 10) - (b * 10) + b - a = ((a - b) * 10) + b - a = ((a - b) * 10) - (a - b) = (a - b) * 9

And there you have it - that must be divisible by 9.

And if that's true of a two-digit number, it's true of a longer number where two digits get swapped, since at all the other digits, the difference will be zero.

So, what about shuffling all the digits in a long number?

Firstly, generalise the two-digits-in-a-long-number theorem, so that rather than two adjacent digits, it deals with any two digits in the number. In that case, you've got a situation where all the digits which are the same cancel out when you subtract, leaving you with the difference being:

(a * 10^x + b * 10^y) - (b * 10^x + a * 10^y)

you say z = x - y, you can boil that down to:

(a * 10^(z + y) + b * 10^y) - (b * 10^(z + y) + a * 10^y)

(a * 10^z * 10^y + b * 10^y) - (b * 10^z * 10^y + a * 10^y)

10^y * ((a * 10^z + b) - (b * 10^z + a))

10^y * ((a * 10^z) + b - (b * 10^z) - a)

10^y * ((a * 10^z) - (b * 10^z) + (b - a))

10^y * ( ((a - b) * 10^z) + (b - a) )

10^y * ( ((a - b) * 10^z) - (a - b) )

10^y * (a - b) * (10^z - 1)

10^z - 1 is always going to be a multiple of 9, for any value of z (except 0), because it's going to be a string of nines. I'm not sure i can prove that, but it's true.

Now, what we've proved there is if that we take a number and swap two digits around, the difference between the original number and the new number is a multiple of nine. So, if we then swap *another* pair of digits in the new number, the difference between the new number and the newer number is also a multiple of nine, because it's just the same again. Now, the difference between the newer number and the original is the sum of the two differences, and the sum of two multiples of nine must itself be a multiple of nine. You can do it again for a third swap, a fourth, any number - any number you can make by swapping pairs of digits of a starting number will have a difference from that starting number which is a multiple of nine. Swapping an unlimited number of pairs is enough to make every permutation of a number, and so this property of difference-divisible-by-nineness holds for any permutation of a number.

Which, turning back to the puzzle, means that any number which is the difference between a number and a permutation of that number is divisible by nine, so has a digital sum of nine.

QED.

tom

-- I don't wanna know your name, i just want BANG BANG BANG!