Maths Olympiad Prep

Library / /31 of 53

Algebra Difficulty 6.4 National olympiad Prove it China

For positive integer nn, an=n5n5a_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=4bn2+bn1b_n = 4b_{n-2} + b_{n-1} (n2n \ge 2). Then
bn=(2+5)n(25)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 1xk54731 \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:
y1y2y5473=1291. y_1 \le y_2 \le \dots \le y_{5473} = 1291.
For our convenience, let f(x)=xxf(x) = x - \lfloor x \rfloor. We have
f(xk5)=f(1292k55473yk5)=f((2+5)6(25)62k(2+5)7(25)72yk)=f((25)6k+(25)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<(25)6k(25)7yk5473(25)61291(25)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(25)k+(25)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,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.