Library / /9 of 48

, 1997

Combinatorics Difficulty 4.5 AIME Prove it Baltic Way

Problem:

Prove that in every sequence of 79 consecutive positive integers written in the decimal system, there is a positive integer whose sum of digits is divisible by 13.

Solution

Solution:

Among the first 40 numbers in the sequence, four are divisible by 10 and at least one of these has its second digit from the right less than or equal to 6. Let this number be $x$ and let $y$ be its sum of digits. Then the numbers $x, x+1, x+2, \ldots, x+39$ all belong to the sequence, and each of $y, y+1, \ldots, y+12$ appears at least once among their sums of decimal digits. One of these is divisible by 13.

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.