Maths Olympiad Prep

Library / /8 of 20

Algebra Difficulty 5.9 AIME, harder Prove it China

Let Sn=1+12++1nS_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}, where nn is a positive integer. Prove that for any real numbers a,ba, b with 0a<b10 \le a < b \le 1, there are infinite many terms in the sequence {Sn[Sn]}\{S_n - [S_n]\} that are within (a,b)(a, b). (Here [x][x] denotes the largest integer not greater than real number xx.)

Solutions — 2

Solution 1

For any nNn \in \mathbb{N}^*, we have
S2n=1+12+13++12n=1+12+(121+122)+(12n1+12n)>1+12+(122+122)++(12n++12n)=1+12+12++12>12n. \begin{align*} S_{2^n} &= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n} = 1 + \frac{1}{2} + \left( \frac{1}{2^1} + \frac{1}{2^2} \right) + \\ & \quad \left( \frac{1}{2^{n-1}} + \frac{1}{2^n} \right) \\ &> 1 + \frac{1}{2} + \left( \frac{1}{2^2} + \frac{1}{2^2} \right) + \cdots + \left( \frac{1}{2^n} + \cdots + \frac{1}{2^n} \right) \\ &= 1 + \frac{1}{2} + \frac{1}{2} + \cdots + \frac{1}{2} > \frac{1}{2}n. \end{align*}
Let N0=1ba+1N_0 = \lfloor \frac{1}{b-a} \rfloor + 1, m=SN0+1m = \lfloor S_{N_0} \rfloor + 1. Then 1ba<N0\frac{1}{b-a} < N_0, 1N0<ba\frac{1}{N_0} < b-a, and SN0<mm+aS_{N_0} < m \le m+a.
Let N1=22(m+1)N_1 = 2^{2(m+1)}. Then SN1=S22(m+1)>m+1m+bS_{N_1} = S_{2^{2(m+1)}} > m+1 \ge m+b.
We claim that there exist nNn \in \mathbb{N}^* with N0<n<N1N_0 < n < N_1 such that m+a<Sn<m+bm+a < S_n < m+b (or, in other words, Sn[Sn](a,b)S_n - [S_n] \in (a, b)).
Otherwise, assuming the claim is false, then there must exist k>N0k > N_0 such that Sk1m+aS_{k-1} \le m+a and Skm+bS_k \ge m+b.
Then SkSk1baS_k - S_{k-1} \ge b-a. But it contradicts the fact that
SkSk1=1k<1N0<ba. S_k - S_{k-1} = \frac{1}{k} < \frac{1}{N_0} < b - a.
Therefore, the claim is true.
Furthermore, assume there are only a finite number of positive integers n1,,nkn_1, \dots, n_k satisfying
Snj[Snj](a,b)(1jk). S_{n_j} - [S_{n_j}] \in (a, b) \quad (1 \le j \le k).
Define c=min1jk{Snj[Snj]}c = \min_{1 \le j \le k} \{S_{n_j} - [S_{n_j}]\}. Then there exists no nNn \in \mathbb{N}^* such that Sn[Sn](a,c)S_n - [S_n] \in (a, c). It contradicts the above claim.
Therefore, there are infinite terms in the sequence {Sn[Sn]}\{S_n - [S_n]\} that are within (a,b)(a, b).
The proof is complete.

Solution 2

For any nNn \in \mathbb{N}^*, we have
S2n=1+12+13++12n=1+12+(121+122)+(12n1+1++12n)>1+12+(122+122)++(12n++12n)=1+12+12++12>12n. \begin{align*} S_{2^n} &= 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{2^n} = 1 + \frac{1}{2} + \left( \frac{1}{2^1} + \frac{1}{2^2} \right) + \\ & \quad \left( \frac{1}{2^{n-1}} + 1 + \dots + \frac{1}{2^n} \right) \\ &> 1 + \frac{1}{2} + \left( \frac{1}{2^2} + \frac{1}{2^2} \right) + \dots + \left( \frac{1}{2^n} + \dots + \frac{1}{2^n} \right) \\ &= 1 + \frac{1}{2} + \frac{1}{2} + \dots + \frac{1}{2} > \frac{1}{2}n. \end{align*}
Therefore, SnS_n can be larger than any positive number as long as nn becomes sufficiently large.
Let N0=1ba+1N_0 = \lfloor \frac{1}{b-a} \rfloor + 1. Then 1N0<ba\frac{1}{N_0} < b-a, and when k>N0k > N_0, we have
SkSk1=1k<1N0<ba. S_k - S_{k-1} = \frac{1}{k} < \frac{1}{N_0} < b - a.
So for any positive integer m>SN0m > S_{N_0}, there exists n>N0n > N_0 such that Snm(a,b)S_n - m \in (a, b), or, in other words, m+a<Sn<m+bm + a < S_n < m + b. Otherwise, there must be k>N0k > N_0 such that Sk1m+aS_{k-1} \le m + a and Skm+bS_k \ge m + b, i.e., SkSk1baS_k - S_{k-1} \ge b - a. But it contradicts the fact that
SkSk1=1k<1N0<ba. S_k - S_{k-1} = \frac{1}{k} < \frac{1}{N_0} < b - a.
Now let mi=[SN0]+im_i = [S_{N_0}] + i (i=1,2,3,i = 1, 2, 3, \dots). Then there exists ni>N0n_i > N_0 such that mi+a<Sni<mi+bm_i + a < S_{n_i} < m_i + b, i.e., Sni[Sni](a,b)S_{n_i} - [S_{n_i}] \in (a, b).
Therefore, there are infinite terms in the sequence {Sn[Sn]}\{S_n - [S_n]\} that are within (a,b)(a, b). \square

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.