Maths Olympiad Prep

Library / /11 of 11

Algebra Difficulty 9.0 Shortlist Prove it Bulgaria

Problem:
Let {an}n=1\{a_{n}\}_{n=1}^{\infty} be a sequence of integers greater than 11 and let x>0x>0 be an irrational number. Denote by xnx_{n} the fractional part of the product anan1a1xa_{n} a_{n-1} \ldots a_{1} x

a) Prove that xn>1an+1x_{n} > \frac{1}{a_{n+1}} for infinitely many nn.

b) Find all sequences {an}n=1\{a_{n}\}_{n=1}^{\infty} such that there exist infinitely many x(0,1)x \in (0,1) for which xn>1an+1x_{n} > \frac{1}{a_{n+1}} for all nn.

Solution

Solution:

a) Suppose that the inequality {anan1a1x}>1an+1\{a_{n} a_{n-1} \ldots a_{1} x\} > \frac{1}{a_{n+1}} holds for finitely many values of nn. Hence there exists ss such that for any nsn \geq s we have {anan1a1x}1an+1\{a_{n} a_{n-1} \ldots a_{1} x\} \leq \frac{1}{a_{n+1}}. Since {anan1a1x}\{a_{n} a_{n-1} \ldots a_{1} x\} is not a rational number (in particular does not equal 00) we obtain that {anan1a1x}<1an+1\{a_{n} a_{n-1} \ldots a_{1} x\} < \frac{1}{a_{n+1}}, i.e. an+1{anan1a1x}<1a_{n+1} \{a_{n} a_{n-1} \ldots a_{1} x\} < 1. Using that an+1a_{n+1} is an integer we have
{an+1anan1a1x}={an+1{anan1a1x}}=an+1{anan1a1x} \{a_{n+1} a_{n} a_{n-1} \ldots a_{1} x\} = \{a_{n+1} \{a_{n} a_{n-1} \ldots a_{1} x\}\} = a_{n+1} \{a_{n} a_{n-1} \ldots a_{1} x\}
For any t>st > s we obtain
1>{atat1asas1a1x}=atat1as{as1a1x} 1 > \{a_{t} a_{t-1} \ldots a_{s} a_{s-1} \ldots a_{1} x\} = a_{t} a_{t-1} \ldots a_{s} \{a_{s-1} \ldots a_{1} x\}
a contradiction, since limtatat1as=\lim_{t \rightarrow \infty} a_{t} a_{t-1} \ldots a_{s} = \infty, but 0<{as1a1x}<10 < \{a_{s-1} \ldots a_{1} x\} < 1.

b) It is clear that if ai=1a_{i} = 1 for some i>1i > 1 then {ai1ai2a1x}>1ai=1\{a_{i-1} a_{i-2} \ldots a_{1} x\} > \frac{1}{a_{i}} = 1 is not true. Suppose that there exists tt such that ai=2a_{i} = 2 for i>ti > t. Then {2py}>12\{2^{p} y\} > \frac{1}{2} for y=atat1a1xy = a_{t} a_{t-1} \ldots a_{1} x and every pp. Since y<1y < 1 and j=112j=1\sum_{j=1}^{\infty} \frac{1}{2^{j}} = 1 we conclude that for every kk the inequality cky<ck+1c_{k} \leq y < c_{k+1} holds true, where ck=12+122++12kc_{k} = \frac{1}{2} + \frac{1}{2^{2}} + \cdots + \frac{1}{2^{k}}. Therefore 2ky[2kck,2kck+12)2^{k} y \in [2^{k} c_{k}, 2^{k} c_{k} + \frac{1}{2}), a contradiction to {2ky}>12\{2^{k} y\} > \frac{1}{2}.

We shall prove that if {an}n=1\{a_{n}\}_{n=1}^{\infty} is a sequence for which ai>1a_{i} > 1 for all i>1i > 1 and the inequality ai>2a_{i} > 2 holds true for infinitely many values of ii, then there exist infinitely many x(0,1)x \in (0,1) such that xn>1an+1x_{n} > \frac{1}{a_{n+1}}. Set
x=b1a1+b2a1a2+b3a1a2a3+ x = \frac{b_{1}}{a_{1}} + \frac{b_{2}}{a_{1} a_{2}} + \frac{b_{3}}{a_{1} a_{2} a_{3}} + \cdots
where b1a11b_{1} \leq a_{1} - 1 and 1biai11 \leq b_{i} \leq a_{i} - 1 for i>1i > 1 and infinitely many of the latter inequalities are strict. Then
x=b1a1+b2a1a2+b3a1a2a3+<a11a1+a21a1a2+a31a1a2a3+=11a1+1a11a1a2+1a1a2=1 \begin{aligned} x & = \frac{b_{1}}{a_{1}} + \frac{b_{2}}{a_{1} a_{2}} + \frac{b_{3}}{a_{1} a_{2} a_{3}} + \cdots \\ & < \frac{a_{1} - 1}{a_{1}} + \frac{a_{2} - 1}{a_{1} a_{2}} + \frac{a_{3} - 1}{a_{1} a_{2} a_{3}} + \cdots \\ & = 1 - \frac{1}{a_{1}} + \frac{1}{a_{1}} - \frac{1}{a_{1} a_{2}} + \frac{1}{a_{1} a_{2}} - \cdots = 1 \end{aligned}
The numbers of this type are infinitely many and we have as above that
bn+1an+1+bn+2an+1an+2+<1 \frac{b_{n+1}}{a_{n+1}} + \frac{b_{n+2}}{a_{n+1} a_{n+2}} + \cdots < 1
Therefore
xn=bn+1an+1+bn+2an+1an+2+>bn+1an+11an+1 x_{n} = \frac{b_{n+1}}{a_{n+1}} + \frac{b_{n+2}}{a_{n+1} a_{n+2}} + \cdots > \frac{b_{n+1}}{a_{n+1}} \geq \frac{1}{a_{n+1}}

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.