Maths Olympiad Prep

Library / /113 of 520

Algebra Difficulty 5.8 AIME, harder Find the answer

Let x1,,x100x_{1}, \ldots, x_{100} be nonnegative real numbers such that xi+xi+1+xi+21x_{i}+x_{i+1}+x_{i+2} \leq 1 for all i=1,,100i=1, \ldots, 100 (we put x101=x1,x102=x2x_{101}=x_{1}, x_{102}=x_{2} ). Find the maximal possible value of the sum
S=i=1100xixi+2 S=\sum_{i=1}^{100} x_{i} x_{i+2}
(Russia) Answer. 252\frac{25}{2}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let x2i=0,x2i1=12 x_{2i} = 0, x_{2i-1} = \frac{1}{2} for all i=1,,50 i = 1, \ldots, 50 . Then we have S=50(12)2=252 S = 50 \cdot \left( \frac{1}{2} \right)^2 = \frac{25}{2} . So, we are left to show that S252 S \leq \frac{25}{2} for all values of xi x_i 's satisfying the problem conditions. Consider any 1i50 1 \leq i \leq 50 . By the problem condition, we get x2i11x2ix2i+1 x_{2i-1} \leq 1 - x_{2i} - x_{2i+1} and x2i+21x2ix2i+1 x_{2i+2} \leq 1 - x_{2i} - x_{2i+1} . Hence by the AM-GM inequality we get
x2i1x2i+1+x2ix2i+2(1x2ix2i+1)x2i+1+x2i(1x2ix2i+1)=(x2i+x2i+1)(1x2ix2i+1)((x2i+x2i+1)+(1x2ix2i+1)2)2=14 \begin{aligned} x_{2i-1} x_{2i+1} + x_{2i} x_{2i+2} & \leq \left( 1 - x_{2i} - x_{2i+1} \right) x_{2i+1} + x_{2i} \left( 1 - x_{2i} - x_{2i+1} \right) \\ & = \left( x_{2i} + x_{2i+1} \right) \left( 1 - x_{2i} - x_{2i+1} \right) \leq \left( \frac{ \left( x_{2i} + x_{2i+1} \right) + \left( 1 - x_{2i} - x_{2i+1} \right) }{2} \right)^2 = \frac{1}{4} \end{aligned}
Summing up these inequalities for i=1,2,,50 i = 1, 2, \ldots, 50 , we get the desired inequality
i=150(x2i1x2i+1+x2ix2i+2)5014=252 \sum_{i=1}^{50} \left( x_{2i-1} x_{2i+1} + x_{2i} x_{2i+2} \right) \leq 50 \cdot \frac{1}{4} = \frac{25}{2}
Comment. This solution shows that a bit more general fact holds. Namely, consider 2n 2n nonnegative numbers x1,,x2n x_1, \ldots, x_{2n} in a row (with no cyclic notation) and suppose that xi+xi+1+xi+21 x_i + x_{i+1} + x_{i+2} \leq 1 for all i=1,2,,2n2 i = 1, 2, \ldots, 2n-2 . Then i=12n2xixi+2n14 \sum_{i=1}^{2n-2} x_i x_{i+2} \leq \frac{n-1}{4} . The proof is the same as above, though if might be easier to find it (for instance, applying induction). The original estimate can be obtained from this version by considering the sequence x1,x2,,x100,x1,x2 x_1, x_2, \ldots, x_{100}, x_1, x_2 .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.