Maths Olympiad Prep

Library / /1 of 5

Algebra Difficulty 7.5 National Olympiad, round 2 Prove it India

Given that a1,a2,,a10a_1, a_2, \dots, a_{10} are positive real numbers, determine the smallest possible value of
i=1107aiai+ai+1 \sum_{i=1}^{10} \left\lfloor \frac{7a_i}{a_i + a_{i+1}} \right\rfloor
where we define a11=a1a_{11} = a_1.

Solutions — 2

Solution 1

Let m=7m = 7 and n=10n = 10. We now claim that the minimum possible value is m1m-1 and this is achieved by letting ai=mia_i = m^i. Now, to show that this is indeed the minimum, we assume without loss of generality that ana_n is the largest amongst all aia_i. Now,
i=1nmaiai+ai+1ma1a1+a2+manan+a1ma1a1+an+manan+a1m(a1+an)an+a11m1 \sum_{i=1}^{n} \left\lfloor \frac{ma_i}{a_i + a_{i+1}} \right\rfloor \ge \left\lfloor \frac{ma_1}{a_1 + a_2} \right\rfloor + \left\lfloor \frac{ma_n}{a_n + a_1} \right\rfloor \ge \left\lfloor \frac{ma_1}{a_1 + a_n} \right\rfloor + \left\lfloor \frac{ma_n}{a_n + a_1} \right\rfloor \ge \left\lfloor \frac{m(a_1 + a_n)}{a_n + a_1} \right\rfloor - 1 \ge m - 1
We just use the fact that x+yx+y1\lfloor x \rfloor + \lfloor y \rfloor \ge \lfloor x + y \rfloor - 1.

Figure 1
This tells us that the problem is indeed true in much higher generality:
Let m,n2m, n \ge 2 be positive integers. Given that a1,,ana_1, \dots, a_n are positive real numbers, determine the smallest possible value of
i=1nmaiai+ai+1 \sum_{i=1}^{n} \left\lfloor \frac{ma_i}{a_i + a_{i+1}} \right\rfloor
where we define an+1=a1a_{n+1} = a_1.

We first observe that if aiai+1a_i \ge a_{i+1}, then
7aiai+ai+17ai2ai3. \left\lfloor \frac{7a_i}{a_i + a_{i+1}} \right\rfloor \ge \left\lfloor \frac{7a_i}{2a_i} \right\rfloor \ge 3.
Thus the sequence (taken cyclically) decreases at most once, otherwise we are done. WLOG a1<a2<<a10a_1 < a_2 < \dots < a_{10}.
Make the substitution ai+1/ai=xia_{i+1}/a_i = x_i. We have xi>1x_i > 1 for 1i91 \le i \le 9, and x10=1/x1x2x9x_{10} = 1/x_1 x_2 \dots x_9. The expression becomes
i=1971+xi+7x1x2x9x1x2x9+1. \sum_{i=1}^{9} \left\lfloor \frac{7}{1+x_i} \right\rfloor + \left\lfloor \frac{7x_1 x_2 \dots x_9}{x_1 x_2 \dots x_9 + 1} \right\rfloor.
If we have xi6x_i \ge 6 for any 1i91 \le i \le 9, then we get
7x1x2x9x1x2x9+16,7x1x2x9x1x2x9+16x1x2x9+6x1x2x96 \begin{aligned} \left\lfloor \frac{7x_1x_2\dots x_9}{x_1x_2\dots x_9+1} \right\rfloor &\ge 6, \\ \frac{7x_1x_2\dots x_9}{x_1x_2\dots x_9+1} &\ge 6x_1x_2\dots x_9+6 \\ x_1x_2\dots x_9 &\ge 6 \end{aligned}

and we are done.
If not, xi<6x_i < 6 for all 1i91 \le i \le 9. But then, for 1i91 \le i \le 9,
71+xi1, \left\lfloor \frac{7}{1 + x_i} \right\rfloor \ge 1,
which means the expression is at least 9, which is greater than our bound! ☐

Solution 2

(uses m=7,n=10m = 7, n = 10 critically) If at most 4 of the ziz_i's are zero, then at least 6 of them are 1\ge 1, and thus the sum is at least 6.
If not, then at least five of them are 0. Suppose z1==z5=0z_1 = \cdots = z_5 = 0 without loss of generality. Note that zi=0z_i = 0 implies
71+xi<1    xi>6, \frac{7}{1 + x_i} < 1 \implies x_i > 6,
so that x1,,x5>6x_1, \dots, x_5 > 6. Thus x1x2x3x4x5>65x_1x_2x_3x_4x_5 > 6^5, which means x6x7x8x9x10<1/65x_6x_7x_8x_9x_{10} < 1/6^5. Assuming WLOG x6=min{x6,x7,x8,x9,x10}x_6 = \min\{x_6, x_7, x_8, x_9, x_{10}\}, this implies x6<1/6x_6 < 1/6. However, then we have
z671+16=6, z_6 \ge \left\lfloor \frac{7}{1 + \frac{1}{6}} \right\rfloor = 6,
and the conclusion follows. ☐

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 reproduced verbatim; metadata (topic, difficulty) added by this project.