Russian problems Problem 43 Reduce each of the first billion natural numbers (billion = 10 9 ) to a single digit by taking its digit sum repeatedly. Do we get more 1s than 2s?
Taking digit sums repeatedly gives the remainder after dividing the number by 9, or 9 if the number is exactly divisible by 9. 10 9 - 1 = 9n, and for any r>=0 the nine consecutive numbers 9r+1, 9r+2, ... , 9r+9 include just one number giving remainder 1 and one number giving remainder 2. Hence the numbers up to 10 9 - 1 give equal numbers of 1s and 2s. 10 9 itself gives 1, so there is just one more of the 1s than the 2s. Russian 41-50 (C) John Scholes jscholes@kalva.demon.co.uk 18 Sep 1998