Maths Olympiad Prep

Library / /82 of 104

Number theory Difficulty 6.5 National Olympiad Prove it Bulgaria

Problem:
Let cc be a positive integer and let {an}n=1\{a_{n}\}_{n=1}^{\infty} be a sequence of positive integers such that an<an+1<an+ca_{n} < a_{n+1} < a_{n} + c for every n1n \geq 1. The terms of the sequence are written one after another and in this way one obtains an infinite sequence of digits. Prove that for every positive integer mm there exists a positive integer kk such that the number formed by the first kk digits of the above sequence is divisible by mm.

Solution

Solution:
Let MM be an arbitrary positive integer. We shall prove that there exists a term of the sequence {an}n=1\{a_{n}\}_{n=1}^{\infty}, whose decimal representation is obtained from that of MM by adding several digits from the right, i.e. the number MM is a "beginning" of that member.
Let kk be an index such that akM10l<ak+1<ak+ca_{k} \leq M \cdot 10^{l} < a_{k+1} < a_{k} + c, where ll is a positive integer which is greater than the number of the digits of cc. Then
M10l<ak+1<M10l+c M \cdot 10^{l} < a_{k+1} < M \cdot 10^{l} + c
and obviously ak+1a_{k+1} satisfies the above requirement.
Let m=2α5βtm = 2^{\alpha} 5^{\beta} t, where (t,10)=1(t, 10) = 1. It is enough to prove the assertion of the problem for m=10γtm = 10^{\gamma} t, where γ=max{α,β}\gamma = \max\{\alpha, \beta\}.
Let us consider the number
M=1000p1000p11000p1000q M = 1 \underbrace{00 \ldots 0}_{p} 1 \underbrace{00 \ldots 0}_{p} 1 \ldots 1 \underbrace{00 \ldots 0}_{p} 1 \underbrace{00 \ldots 0}_{q}
Here p=kφ(t)p = k \varphi(t), where φ(t)\varphi(t) is the Euler function, kk is a positive integer such that p>γp > \gamma, the number qq is greater than γ\gamma, and the number of 1's is t+1t+1.
Then MM is a "beginning" of some aka_{k}. Hence the sequence of the digits (formed by the terms of the sequence written one after another) looks like this:
f1f2fr1000p1000p11000p1000q f_{1} f_{2} \ldots f_{r} 1 \underbrace{00 \ldots 0}_{p} 1 \underbrace{00 \ldots 0}_{p} 1 \ldots 1 \underbrace{00 \ldots 0}_{p} 1 \underbrace{00 \ldots 0}_{q} \ldots
where f1,f2,,frf_{1}, f_{2}, \ldots, f_{r} are the digits before aka_{k}. It is clear now that, depending on the remainder of f1f2fr1\overline{f_{1} f_{2} \ldots f_{r} 1} modulo tt, we can add suitable digits from MM to f1f2fr1\overline{f_{1} f_{2} \ldots f_{r} 1} in such a way that the resulting number is divisible by 10αt10^{\alpha} t.

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.