Maths Olympiad Prep

Library / /29 of 55

, 2006

Algebra Difficulty 8.7 Shortlist Prove it IMO

A sequence of real numbers a0,a1,a2,a_{0}, a_{1}, a_{2}, \ldots is defined by the formula
ai+1=aiai for i0 a_{i+1}=\left\lfloor a_{i}\right\rfloor \cdot\left\langle a_{i}\right\rangle \quad \text{ for } \quad i \geq 0
here a0a_{0} is an arbitrary real number, ai\left\lfloor a_{i}\right\rfloor denotes the greatest integer not exceeding aia_{i}, and ai=aiai\left\langle a_{i}\right\rangle=a_{i}-\left\lfloor a_{i}\right\rfloor. Prove that ai=ai+2a_{i}=a_{i+2} for ii sufficiently large.

Solution

First note that if a00a_{0} \geq 0, then all ai0a_{i} \geq 0. For ai1a_{i} \geq 1 we have (in view of ai<1\left\langle a_{i}\right\rangle<1 and ai>0\left\lfloor a_{i}\right\rfloor>0 )
ai+1ai+1=aiai<ai \left\lfloor a_{i+1}\right\rfloor \leq a_{i+1}=\left\lfloor a_{i}\right\rfloor \cdot\left\langle a_{i}\right\rangle<\left\lfloor a_{i}\right\rfloor
the sequence ai\left\lfloor a_{i}\right\rfloor is strictly decreasing as long as its terms are in [1,)[1, \infty). Eventually there appears a number from the interval [0,1)[0,1) and all subsequent terms are 00.

Now pass to the more interesting situation where a0<0a_{0}<0; then all ai0a_{i} \leq 0. Suppose the sequence never hits 00. Then we have ai1\left\lfloor a_{i}\right\rfloor \leq -1 for all ii, and so
1+ai+1>ai+1=aiai>ai 1+\left\lfloor a_{i+1}\right\rfloor>a_{i+1}=\left\lfloor a_{i}\right\rfloor \cdot\left\langle a_{i}\right\rangle>\left\lfloor a_{i}\right\rfloor
this means that the sequence ai\left\lfloor a_{i}\right\rfloor is nondecreasing. And since all its terms are integers from (,1](-\infty,-1], this sequence must be constant from some term on:
ai=c for ii0;c a negative integer.  \left\lfloor a_{i}\right\rfloor=c \quad \text{ for } \quad i \geq i_{0} ; \quad c \text{ a negative integer. }
The defining formula becomes
ai+1=cai=c(aic)=caic2 a_{i+1}=c \cdot\left\langle a_{i}\right\rangle=c\left(a_{i}-c\right)=c a_{i}-c^{2}
Consider the sequence
bi=aic2c1 \begin{equation*} b_{i}=a_{i}-\frac{c^{2}}{c-1} \tag{1} \end{equation*}
It satisfies the recursion rule
bi+1=ai+1c2c1=caic2c2c1=cbi b_{i+1}=a_{i+1}-\frac{c^{2}}{c-1}=c a_{i}-c^{2}-\frac{c^{2}}{c-1}=c b_{i}
implying
bi=cii0bi0 for ii0 \begin{equation*} b_{i}=c^{i-i_{0}} b_{i_{0}} \quad \text{ for } \quad i \geq i_{0} \tag{2} \end{equation*}
Since all the numbers aia_{i} (for ii0i \geq i_{0} ) lie in [c,c+1)[c, c+1), the sequence (bi)\left(b_{i}\right) is bounded. The equation (2) can be satisfied only if either bi0=0b_{i_{0}}=0 or c=1|c|=1, i.e., c=1c=-1.

In the first case, bi=0b_{i}=0 for all ii0i \geq i_{0}, so that
ai=c2c1 for ii0. a_{i}=\frac{c^{2}}{c-1} \quad \text{ for } \quad i \geq i_{0} .
In the second case, c=1c=-1, equations (1) and (2) say that
ai=12+(1)ii0bi0={ai0 for i=i0,i0+2,i0+4,,1ai0 for i=i0+1,i0+3,i0+5,. a_{i}=-\frac{1}{2}+(-1)^{i-i_{0}} b_{i_{0}}= \begin{cases}a_{i_{0}} & \text{ for } i=i_{0}, i_{0}+2, i_{0}+4, \ldots, \\ 1-a_{i_{0}} & \text{ for } i=i_{0}+1, i_{0}+3, i_{0}+5, \ldots .\end{cases}
Summarising, we see that (from some point on) the sequence (ai)\left(a_{i}\right) either is constant or takes alternately two values from the interval (1,0)(-1,0). The result follows.

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 and solution reproduced as published; topic and difficulty added by this site.