wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Math Trick II
        
(Message started by: Icarus on Jun 25^th, 2006, 12:02pm)

Title: Math Trick II
Post by Icarus on Jun 25^th, 2006, 12:02pm

Like the post that inspired it, this one is really too easy for the Putnam forum, but I am posting it here anyway because I think it is an interesting mathematical curiosity, and the other forums didn't fit all that well.

The majority of "Math tricks" I've seen rely on the easily proven fact that the sum of the digits of a number is congruent to the number itself modulo 9. Let S(x) be the sum of the digits of the integer x (in base 10). So 9 | (x - S(x)).

However, not all multiples of 9 can be so represented. For example, there is no value of x for which x - S(x) = 90.

Identify all positive integers n such that 9n != x - S(x) for any x.

Title: Re: Math Trick II
Post by Deedlit on Aug 1^st, 2006, 9:08pm

Let's make a number system where the ith digit from the right represents (10ⁱ - 1)/9. So

abcde = 11111a + 1111b + 111c + 11d + e.

Observe that

Sum [i = 1 to n] 9 * ((10ⁱ - 1)/9) = (10ⁿ⁺¹ - 1)/9 - n - 1 < (10ⁿ⁺¹ - 1)/9

so each number has at most one representation; you have to take the largest possible digit at each step, because otherwise you can't make up the difference at lower digits. The above says

100...0 = 99...9 + n + 1

so there are n numbers in between a number ending with exactly n 9's and the next number ending with n 0's. Since

x - S(x) = sum[i = 1 to n] x_i10ⁱ - sum[i = 1 to n] x_i
= 9 sum[i = 1 to n] x_i(10ⁱ - 1) / 9

the numbers that can be represented as x - S(x) are exactly the numbers represented by our number system.

A simple way to fill out the number system: note that

Sum [i = m+1 to n] 9 * (10ⁱ - 1)/9) + 10 * (10^m - 1)/9) = (10ⁿ⁺¹ - 1)/9 - n + m - 1

so we get the n missing numbers by letting m go from 1 to n. Letting a stand for 10, the numbers between, say, 32549999 and 32550000 are 3254999a, 325499a0, 32549a00, and 3254a000. So our number system includes the normal sequnces of digits 0-9, or sequnces of such digits followed by a and a string of 0's.

Title: Re: Math Trick II
Post by Icarus on Aug 2^nd, 2006, 6:44pm

That is a unique approach!:D Well done.