Maths Olympiad Prep

Library / China Girls' Mathematical Olympiad /30 of 51

China Girls' Mathematical Olympiad

Algebra Difficulty 6.4 National Olympiad Prove it China

For positive integer nn, an=n5−⌊n5⌋a_n = n\sqrt{5} - \lfloor n\sqrt{5} \rfloor. Compute the maximum value and the minimum value of a1,a2,…,a2009a_1, a_2, \dots, a_{2009}. (For real number xx, ⌊x⌋\lfloor x \rfloor denotes the greatest integer less than or equal to xx.) (Posed by Wang Zhixiong)

Solution

Let b0=0b_0 = 0, b1=1b_1 = 1, bn=4bn−2+bn−1b_n = 4b_{n-2} + b_{n-1} (n≥2n \ge 2). Then
bn=(2+5)n−(2−5)n25. b_n = \frac{(2+\sqrt{5})^n - (2-\sqrt{5})^n}{2\sqrt{5}}.
In particular, b6=1292b_6 = 1292, b7=5473b_7 = 5473.
For every k=1,2,…,5473k = 1, 2, \dots, 5473, there are unique integers xk,ykx_k, y_k such that 1292k=xk+5473yk1292k = x_k + 5473y_k, and 1≤xk≤54731 \le x_k \le 5473. Since (1292,5473)=1(1292, 5473) = 1, x1,x2,…,x5473x_1, x_2, \dots, x_{5473} is a permutation of {1,2,…,5473}\{1, 2, \dots, 5473\}, and it is clear that {yk}\{y_k\} is nondecreasing:
y1≤y2≤⋯≤y5473=1291. y_1 \le y_2 \le \dots \le y_{5473} = 1291.
For our convenience, let f(x)=x−⌊x⌋f(x) = x - \lfloor x \rfloor. We have
f(xk5)=f(1292k5−5473yk5)=f((2+5)6−(2−5)62k−(2+5)7−(2−5)72yk)=f(−(2−5)6k+(2−5)7yk). \begin{aligned} f(x_k\sqrt{5}) &= f(1292k\sqrt{5} - 5473y_k\sqrt{5}) \\ &= f\left(\frac{(2+\sqrt{5})^6 - (2-\sqrt{5})^6}{2}k - \frac{(2+\sqrt{5})^7 - (2-\sqrt{5})^7}{2}y_k\right) \\ &= f(-(2-\sqrt{5})^6k + (2-\sqrt{5})^7y_k). \end{aligned}
Since
0<(2−5)6k−(2−5)7yk≤5473(2−5)6−1291(2−5)7<1, \begin{aligned} & 0 < (2-\sqrt{5})^6 k - (2-\sqrt{5})^7 y_k \\ & \le 5473(2-\sqrt{5})^6 - 1291(2-\sqrt{5})^7 < 1, \end{aligned}
it follows that
f(xk5)=1−(2−5)k+(2−5)7yk, f(x_k \sqrt{5}) = 1 - (2 - \sqrt{5})^k + (2 - \sqrt{5})^7 y_k,
and this is strictly decreasing.
Now, since x1=1292x_1 = 1292, x5473=5473x_{5473} = 5473, x5472=4181x_{5472} = 4181, x5471=2889x_{5471} = 2889, x5470=1597x_{5470} = 1597, we see that a1292a_{1292} attains the maximum and a1597a_{1597} the minimum.

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.