Maths Olympiad Prep

Library / /80 of 196

Number theory Difficulty 5.0 AIME Prove it Soviet Union

Problem:

Reduce each of the first billion natural numbers (billion =109= 10^9) to a single digit by taking its digit sum repeatedly. Do we get more 1s than 2s?

Solution

Taking digit sums repeatedly gives the remainder after dividing the number by 99, or 99 if the number is exactly divisible by 99. 1091=9n10^9 - 1 = 9n, and for any r0r \geq 0 the nine consecutive numbers 9r+19r + 1, 9r+29r + 2, ..., 9r+99r + 9 include just one number giving remainder 11 and one number giving remainder 22. Hence the numbers up to 109110^9 - 1 give equal numbers of 11s and 22s. 10910^9 itself gives 11, so there is just one more of the 11s than the 22s.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.