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 09:
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 (14) 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 20100116 16:41:32 