S(N) denotes the sum of the digits of a base ten positive integer N.

Prove that:

S(2*N) ≤ 2*S(N) ≤ 10*S(2*N)

Looking at the effect doubling a digit has for each digit 0-9:

0 ->  0 (+0)
1 ->  2 (+1)
2 ->  4 (+2)
3 ->  6 (+3)
4 ->  8 (+4)
5 -> 10 (-4)
6 -> 12 (-3)
7 -> 14 (-2)
8 -> 16 (-1)
9 -> 18 (-0)

So, by doubling N, none of these values will decrease their contributions to the sum by any more than 80% (5 -> 10). Also, the lower values (1-4) only double in their contributions, so S(2N) can't exceed 2*S(N).

As the contributions are limited to an 80% decrease (5 -> 10), 2*S(N) ≤ 10*S(2N) becomes:

2*S(N) ≤ 10*0.2*S(N)
2*S(N) ≤ 2*S(N)

So a number consisting of all 5's will be the absolute largest decrease in the sum of the digits when doubled, but is limited to go no lower than 0.2*S(N). Multiplying by 10 and we can see in the above equation that 2*S(N) is always less than or equal to 10*S(2N).

Posted by Justin on 2010-01-16 16:41:32