Maths Olympiad Prep

Library / /158 of 397

Algebra Difficulty 5.6 AIME, harder Prove it Taiwan

Let a1a2a107>0a_1 \ge a_2 \ge \cdots \ge a_{107} > 0, satisfying k=1107akM\sum_{k=1}^{107} a_k \ge M, and 0<b1b2b1070 < b_1 \le b_2 \le \cdots \le b_{107}, satisfying k=1107bkN\sum_{k=1}^{107} b_k \le N.
Prove that: for any m{1,2,,107}m \in \{1, 2, \dots, 107\}, the arithmetic mean of the sequence
a1b1,a2b2,,ambm \frac{a_1}{b_1}, \frac{a_2}{b_2}, \dots, \frac{a_m}{b_m}
is not less than MN\frac{M}{N}.

Solution

The original problem asks to prove that: for every m{1,2,,n}m \in \{1, 2, \dots, n\},
1mk=1makbkMN, where n=107. \frac{1}{m} \sum_{k=1}^{m} \frac{a_k}{b_k} \geq \frac{M}{N}, \text{ where } n = 107.

Let k=1nak=aM\sum_{k=1}^{n} a_k = a \ge M and k=1nbk=bN\sum_{k=1}^{n} b_k = b \le N, and define
xk=aka,yk=bkb,k=1,2,,n. x_k = \frac{a_k}{a}, \quad y_k = \frac{b_k}{b}, \quad k = 1, 2, \dots, n.

Then we have k=1nxk=k=1nyk=1\sum_{k=1}^{n} x_k = \sum_{k=1}^{n} y_k = 1, and the sequence {xk}\{x_k\} is decreasing, while the sequence {yk}\{y_k\} is increasing. Therefore, the sequence {xkyk}\{\frac{x_k}{y_k}\} is decreasing, and
x1y11xnyn. \frac{x_1}{y_1} \ge 1 \ge \frac{x_n}{y_n}.
We may take k0{1,2,,n}k_0 \in \{1, 2, \dots, n\} such that
x1y1x2y2xk0yk01xk0+1yk0+1xnyn. \frac{x_1}{y_1} \ge \frac{x_2}{y_2} \ge \cdots \ge \frac{x_{k_0}}{y_{k_0}} \ge 1 \ge \frac{x_{k_0+1}}{y_{k_0+1}} \ge \cdots \ge \frac{x_n}{y_n}.

(1) For a positive integer m{1,2,,k0}m \in \{1, 2, \dots, k_0\}, we have
k=1mxkykk=1mykxk=m; \sum_{k=1}^{m} \frac{x_k}{y_k} \geq \sum_{k=1}^{m} \frac{y_k}{x_k} = m;

k=1makbk=k=1maxkbykmabmMN, \sum_{k=1}^{m} \frac{a_k}{b_k} = \sum_{k=1}^{m} \frac{ax_k}{by_k} \geq \frac{ma}{b} \geq \frac{mM}{N},

1mk=1makbkMN. \frac{1}{m} \sum_{k=1}^{m} \frac{a_k}{b_k} \geq \frac{M}{N}.

(2) For a positive integer m{k0+1,k0+2,,n}m \in \{k_0 + 1, k_0 + 2, \dots, n\}, from
k=1nxk=k=1nyk, \sum_{k=1}^{n} x_k = \sum_{k=1}^{n} y_k,
we have
k=1k0(xkyk)=k=k0+1n(ykxk)k=k0+1m(ykxk). \sum_{k=1}^{k_0} (x_k - y_k) = \sum_{k=k_0+1}^{n} (y_k - x_k) \geq \sum_{k=k_0+1}^{m} (y_k - x_k).

k=1mxkyk=k=1k0(1+xkykyk)+k=k0+1m(1ykxkyk)m+1yk0+1(k=1k0(xkyk)k=k0+1m(ykxk))m. \begin{aligned} \sum_{k=1}^{m} \frac{x_k}{y_k} &= \sum_{k=1}^{k_0} \left(1 + \frac{x_k - y_k}{y_k}\right) + \sum_{k=k_0+1}^{m} \left(1 - \frac{y_k - x_k}{y_k}\right) \\ &\geq m + \frac{1}{y_{k_0+1}} \left(\sum_{k=1}^{k_0} (x_k - y_k) - \sum_{k=k_0+1}^{m} (y_k - x_k)\right) \geq m. \end{aligned}

k=1makbk=k=1maxkbykmabmMN, \sum_{k=1}^{m} \frac{a_k}{b_k} = \sum_{k=1}^{m} \frac{ax_k}{by_k} \geq \frac{ma}{b} \geq \frac{mM}{N},

1mk=1makbkMN. \frac{1}{m} \sum_{k=1}^{m} \frac{a_k}{b_k} \geq \frac{M}{N}.

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 translated into English from the original; metadata (topic, difficulty) added by this project.