Maths Olympiad Prep

Library / /1 of 16

Number theory Difficulty 4.7 AIME Prove it Bulgaria

Problem:

Let mm be a positive integer and um=111mu_{m} = \underbrace{11 \ldots 1}_{m}. Prove that there is no positive integer multiple of umu_{m} such that the sum of its digits is less than mm.

Solution

Solution:

Assume the contrary. Then there exists a positive integer multiple of umu_{m} such that the sum of its digits is less than mm and let tt be the smallest number with this property. Since t>10mt > 10^{m}, the number tt can be written as t=10ma+bt = 10^{m} a + b, where 0<b<10m0 < b < 10^{m}.

We have t=10ma+b=(10m1)a+a+bt = 10^{m} a + b = (10^{m} - 1) a + a + b. Since umu_{m} divides both tt and 10m1=9um10^{m} - 1 = 9 u_{m}, we conclude that umu_{m} divides a+ba + b. But the sum of the digits of a+ba + b does not exceed the sum of the digits of tt and a+b<ta + b < t, a contradiction.

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.