Because I'm a Nerd

by Joe Archive on September 30, 2008

I was queued up at whole foods behind a lady who was taking forever… and she took even longer once the cashier realized that she had transposed two digits between the register and the credit card charge – instead of $152.73, she charged the lady $125.73. When she realized this, she had to charge the lady an additional $27. Which took even more time, between explaining and doing…br /br /All this is beside the point, except that I noticed that 27, while not round span style=”font-style: italic;”per se,/span was 3^3. I wondered if transpositions always gave interesting differences.br /br /A little experimentation in my head lead me to conjecture that, rather than a cubic, the difference between two numbers that had a pair of adjacent digits swapped was multiple of 9.br /br /A little more thought yielded a proof that is probably inelegant (but I’m a physicist not a mathematician, or a miracle worker!) and is also probably old news to all (but I don’t care to look it up).br /br /imagine a number n represented by ….def, where d, e, f are integers and the number is such that n = f+10*e+100*d + etcbr /br /now, consider the number m = …dfebr /br /m-n = e+10*f+100*d – (f+10*e+100*) = (1-10)*e + (10-1)*f = 9*(f-e)! br /br /It is obvious that this still holds if there are digits to the right of our pair of transposees – everything written above is just multiplied by sufficient powers of ten.br /br /What about when the pair of digits is separated by intervening digits?br /br /eg m = …fedbr /br /this can be considered the result of three transpositions:br /br /def — dfe — fde — fedbr /br /Each transposition provides a multiple of 9 to the difference, and so the statement still holds.br /br /we can prove the statement for general separations through induction -br /br /consider the difference betweenbr /br / …abc…..defbr /br /andbr /br /…aec…..dbf br /br /where there are j+1 digits between the b and the ebr /br /consider the following chain of swaps:br /br /…abc…..def — …acb…..def — …ace…..dbf — …aec…..dbfbr /This chain consists of two swaps of adjacent digits and one of digits seperated by j digits. All of these are known (or assumed) to satisfy the “multiple of nine” rule so the sum of the differences also obeys the rule.br /br /QED!br /br /I haven’t proven anything in ages… it’s actually a lot more fun when it isn’t on an exam (and when its something trivial)

Previous post:

Next post: