Maths Olympiad Prep

Library / /9 of 10

, 2024

Algebra Difficulty 7.3 National olympiad, round 2 Prove it China

Fix an irrational number α>1\alpha > 1 and a positive integer LL such that L>α2α1L > \frac{\alpha^2}{\alpha - 1}.
Given an integer x1>Lx_1 > L, define a sequence {xn}\{x_n\} as follows: for every integer n1n \ge 1,
xn+1={αxn,if xnL,xnα,if xn>L. x_{n+1} = \begin{cases} \lfloor \alpha x_n \rfloor, & \text{if } x_n \le L, \\ \lfloor \frac{x_n}{\alpha} \rfloor, & \text{if } x_n > L. \end{cases}
Here, u\lfloor u \rfloor denotes the largest integer that is less than or equal to uu.
(1) Prove that the sequence {xn}\{x_n\} is eventually periodic, i.e., there exist positive integers TT and NN such that for any integer n>Nn > N, we have xn+T=xnx_{n+T} = x_n.
(2) Prove that the smallest integer TT satisfying (1) is an odd integer that is independent of x1x_1.

Solution

Proof. First, since α\alpha is an irrational number, the integer part operation in the definition of xn+1x_{n+1} always makes the corresponding number strictly smaller. For any integer uu satisfying 1α1<uL\frac{1}{\alpha-1} < u \le L, we have αu>αu1>u\lfloor \alpha u \rfloor > \alpha u - 1 > u and αuαL\lfloor \alpha u \rfloor \le \alpha L; while for any integer vL+1v \ge L+1, we have vα>Lα1>1α1\lfloor \frac{v}{\alpha} \rfloor > \frac{L}{\alpha} - 1 > \frac{1}{\alpha-1} and vα<v\lfloor \frac{v}{\alpha} \rfloor < v. Therefore, it is easy to verify by mathematical induction that for any positive integer nn,
1α1<xnmax{x,αL}, \frac{1}{\alpha - 1} < x_n \le \max\{x, \alpha L\},
which implies that the sequence {xn}\{x_n\} is bounded. Since {xn}\{x_n\} is a recursive sequence, it must eventually become periodic. Let TT denote the smallest positive period of {xn}\{x_n\}. By definition, there exists a positive integer NN such that for any integer nNn \ge N, we have xn+N=xnx_{n+N} = x_n.
Since αL>αL1>L\lfloor \alpha L \rfloor > \alpha L - 1 > L, it follows that αLL+1\lfloor \alpha L \rfloor \ge L + 1. Thus, for any integer nNn \ge N, we have xnαLx_n \le \lfloor \alpha L \rfloor. Consequently, for any integer nNn \ge N, if xnL+1x_n \ge L + 1, then
xn+1=xnα<1ααL=L, x_{n+1} = \lfloor \frac{x_n}{\alpha} \rfloor < \frac{1}{\alpha} \cdot \alpha L = L,
and
xn+2=αxn+1. x_{n+2} = \lfloor \alpha x_{n+1} \rfloor.
Clearly, there exists an integer nNn \ge N such that xn>Lx_n > L. Let mN+1m \ge N + 1 be the smallest integer such that
xm1=min{xnnN and xn>L}. x_{m-1} = \min \{x_n \mid n \ge N \text{ and } x_n > L\}.
From the previous analysis, we know
xm=xm1α<Landxm+1=αxm>αxm1>xm. x_m = \lfloor \frac{x_{m-1}}{\alpha} \rfloor < L \quad \text{and} \quad x_{m+1} = \lfloor \alpha x_m \rfloor > \alpha x_m - 1 > x_m.
Note that xm+1<αxm<αxm1α=xm1x_{m+1} < \alpha x_m < \alpha \cdot \frac{x_{m-1}}{\alpha} = x_{m-1}. By the minimality of xm1x_{m-1}, we know xm+1Lx_{m+1} \le L. Since αxm<xm+1+1L+1\alpha x_m < x_{m+1} + 1 \le L + 1, it follows that
xm<L+1α, x_m < \frac{L+1}{\alpha},

and hence xmL+1αx_m \le \lfloor \frac{L+1}{\alpha} \rfloor. Moreover, since xm1L+1x_{m-1} \ge L+1, we have
xm=xm1αL+1α. x_m = \lfloor \frac{x_{m-1}}{\alpha} \rfloor \ge \lfloor \frac{L+1}{\alpha} \rfloor.
Therefore, xm=L+1αx_m = \lfloor \frac{L+1}{\alpha} \rfloor. By the minimality of xm1x_{m-1}, we conclude that for any integer nn0n \ge n_0, xnxmx_n \ge x_m.
For any integer nNn \ge N, if xm+1xnLx_m + 1 \le x_n \le L, then
xn+1=αxn>α(xm+1)1>αL+1α1=L, x_{n+1} = \lfloor \alpha x_n \rfloor > \alpha(x_m + 1) - 1 > \alpha \cdot \frac{L+1}{\alpha} - 1 = L,
which implies xn+1L+1x_{n+1} \ge L+1. Moreover,
xn+2=xn+1α<xn+1α<1ααxn=xn. x_{n+2} = \lfloor \frac{x_{n+1}}{\alpha} \rfloor < \frac{x_{n+1}}{\alpha} < \frac{1}{\alpha} \cdot \alpha x_n = x_n.
Combining the above analysis, we have
xm<xm+1L<xm+2. x_m < x_{m+1} \le L < x_{m+2}.
Furthermore, for each i=1,2,,T1i = 1, 2, \dots, T-1, when ii is odd, xm+iLx_{m+i} \le L; when ii is even, xm+i>Lx_{m+i} > L. Note also that xm+1>xm+3>>xm+T=xmx_{m+1} > x_{m+3} > \dots > x_{m+T} = x_m. Therefore, TT is an odd number.
Finally, note that xm=L+1αx_m = \lfloor \frac{L+1}{\alpha} \rfloor is independent of xx. Thus, the minimal positive period TT is also independent of xx.

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.