Maths Olympiad Prep

Library / /203 of 299

Number theory Difficulty 6.8 National Olympiad Prove it Iran

For two rational numbers r,sr, s we say rsr|s if there is kZk \in \mathbb{Z} so that s=krs = kr. The sequence (an)nN(a_n)_{n \in \mathbb{N}} is an increasing sequence of natural numbers such that for all i,jNi, j \in \mathbb{N}, gcd(ai,aj)=1\gcd(a_i, a_j) = 1 and (bn)nN(b_n)_{n \in \mathbb{N}} is a sequence of distinct natural numbers. Assume that for each nNn \in \mathbb{N} we have
i=1n1aii=1n1bi, \sum_{i=1}^{n} \frac{1}{a_i} \mid \sum_{i=1}^{n} \frac{1}{b_i},
prove that for all nNn \in \mathbb{N} we have an=bna_n = b_n.

Solution

i=1n1bi=kni=1n1ai \sum_{i=1}^{n} \frac{1}{b_i} = k_n \sum_{i=1}^{n} \frac{1}{a_i}
by subtracting these equalities for n,n+1n, n + 1 we have:
1bn+1=kn+11an+1+(kn+1kn)i=1n1ai \frac{1}{b_{n+1}} = k_{n+1} \frac{1}{a_{n+1}} + (k_{n+1} - k_n) \sum_{i=1}^{n} \frac{1}{a_i}
Choose a big enough mm, such that for n>mn > m we have bn>a0b_n > a_0, (this is possible because bib_i are distinct natural numbers). Then we have 1bn+1<i=1n1ai\frac{1}{b_{n+1}} < \sum_{i=1}^{n} \frac{1}{a_i}.
Therefore kn+1knk_{n+1} \le k_n.
Whence, for big enough ii, the sequence kik_i is decreasing, hence they are constant after some point. If kn=kn+1k_n = k_{n+1} then because gcd(an+1,an)=1\gcd(a_{n+1}, a_n) = 1 we have kn=kn+1=1k_n = k_{n+1} = 1. So we have an=bna_n = b_n for large enough nn.
Assume that for n>Nn > N, an=bna_n = b_n, kn=1k_n = 1, by subtracting the equations
i=1N+11bi=i=1N+11ai,aN+1=bN+1 \sum_{i=1}^{N+1} \frac{1}{b_i} = \sum_{i=1}^{N+1} \frac{1}{a_i}, \quad a_{N+1} = b_{N+1}
we get i=1N1bi=i=1N1ai\sum_{i=1}^{N} \frac{1}{b_i} = \sum_{i=1}^{N} \frac{1}{a_i} and so kN=1k_N = 1. Now we have
1bN=1aN+(1kN1)i=1N11ai \frac{1}{b_N} = \frac{1}{a_N} + (1 - k_{N-1}) \sum_{i=1}^{N-1} \frac{1}{a_i}
the aia_i are increasing so if kN11k_{N-1} \neq 1 the right hand side becomes negative which is a contradiction. Hence we have kN1=1k_{N-1} = 1 and by induction, we prove that ai=bia_i = b_i. ■

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.