Maths Olympiad Prep

Library / /15 of 129

Number theory Difficulty 4.2 AIME Find the answer Slovenia

How many positive integers smaller than 10001000 have the sum of the digits divisible by 77 and are multiples of 33?

Pick one

Solution

The sum of the digits of a multiple of 33 is divisible by 33. So, we are looking for numbers with the sum of the digits divisible by 2121. The sum of the digits of any number smaller than 10001000 is less than or equal to 9+9+9=279 + 9 + 9 = 27. So, in our case the sum of the digits is equal to 2121.

The smallest possible digit is at least 2118=321 - 18 = 3 and at most 213=7\frac{21}{3} = 7. The only possible triples of digits are (3,9,9)(3, 9, 9), (4,8,9)(4, 8, 9), (5,7,9)(5, 7, 9), (5,8,8)(5, 8, 8), (6,6,9)(6, 6, 9), (6,7,8)(6, 7, 8) and (7,7,7)(7, 7, 7). Each triple with three different digits corresponds to six different numbers. Each triple with two equal digits corresponds to three different numbers and the triple (7,7,7)(7, 7, 7) corresponds to one number. Hence, there are 36+33+1=283 \cdot 6 + 3 \cdot 3 + 1 = 28 numbers with the required properties.

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.