Maths Olympiad Prep

Library / /198 of 520

Number theory Difficulty 6.7 National olympiad Prove it

Prove that among any 18 consecutive positive 3-digit numbers, there is at least one that is divisible by the sum of its digits!

Solution

1. Consider any 18 consecutive positive 3-digit numbers. Let these numbers be n,n+1,n+2,,n+17 n, n+1, n+2, \ldots, n+17 .

2. Among any 18 consecutive integers, there is at least one number that is divisible by 18. This is because 18 consecutive integers cover all possible remainders when divided by 18, ensuring that one of them must be divisible by 18.

3. Let a a be the number among these 18 consecutive integers that is divisible by 18. Thus, 18a 18 \mid a .

4. Since 18a 18 \mid a , it follows that 9a 9 \mid a (because 18 is a multiple of 9).

5. By the properties of divisibility, if 9a 9 \mid a , then the sum of the digits of a a , denoted as S(a) S(a) , must also be divisible by 9. This is a consequence of the rule that a number is divisible by 9 if and only if the sum of its digits is divisible by 9.

6. For a 3-digit number, the maximum sum of its digits is 9+9+9=27 9 + 9 + 9 = 27 . Therefore, S(a) S(a) can be 9, 18, or 27.

7. If S(a)=9 S(a) = 9 or S(a)=18 S(a) = 18 , then S(a)a S(a) \mid a because a a is divisible by 18 and 18 is divisible by both 9 and 18.

8. If S(a)=27 S(a) = 27 , then the only 3-digit number with a digit sum of 27 is 999. Since 27999 27 \mid 999 , it follows that S(a)a S(a) \mid a in this case as well.

9. Therefore, in all cases, there exists at least one number a a among the 18 consecutive 3-digit numbers such that S(a)a S(a) \mid a .

Thus, the proof is completed. \blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.