Maths Olympiad Prep

Library / Bulgarian Mathematical Competitions /71 of 92

Bulgarian Mathematical Competitions

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 n≥1n \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 ak≤M⋅10l<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
M⋅10l<ak+1<M⋅10l+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=100…0⏟p100…0⏟p1…100…0⏟p100…0⏟q 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:
f1f2…fr100…0⏟p100…0⏟p1…100…0⏟p100…0⏟q… 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 f1f2…fr1‾\overline{f_{1} f_{2} \ldots f_{r} 1} modulo tt, we can add suitable digits from MM to f1f2…fr1‾\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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.