$x_{i}+x_{i+1}+x_{i+2}\leq 1$ and $0 \leq x_{i+2} \Rightarrow x_{i}x_{i+2}\leq x_{i+2}-x_{i+2}^2-x_{i+1}x_{i+2}$ $2S\leq \sum^{100}_{i=1}(2x_{i}-(2x_{i}^2+2x_{i}x_{i+1}))=\sum^{100}_{i=1}(x_{i}+x_{i+1})-(x_{i}+x_{i+1})^2=\sum^{100}_{i=1}(x_{i}+x_{i+1})(1-(x_{i}+x_{i+1}))\leq 100\cdot\frac{1}{4}=25$ it follows that $S\leq \frac{25}{2}$ we can make equality setting $x_{2i}=\frac{1}{2}$ and $x_{2i-1}=0$ So the answer is $S= \frac{25}{2}$

nice problem!! solution = by $x_i + x_{i+1} + x_{i+2} \leq 1$ and than AM-GM we have $x_i.x_{i+2}+x_{i+1}x_{i+3}\leq (1-x_{1+1}-x_{i+2})(x_{i+2})+(1-x_{1+1}-x_{i+2})(x_{i+2})= (1-x_{1+1}-x_{i+2})(x_{i+1}+x_{1+2})\leq \frac{1}{4}$ and so max. $S = \sum^{100}_{i=1} x_i x_{i+2}=\frac{25}{2}$ so we are done

Yay solved an A3

Cute little problem! IMO ShortList 2010 A3 wrote: Let $x_1, \ldots , x_{100}$ be nonnegative real numbers such that $x_i + x_{i+1} + x_{i+2} \leq 1$ for all $i = 1, \ldots , 100$ (we put $x_{101 } = x_1, x_{102} = x_2).$ Find the maximal possible value of the sum $S = \sum^{100}_{i=1} x_i x_{i+2}.$ Proposed by Sergei Berlov, Ilya Bogdanov, Russia Answer: the desired maximal value is $\boxed{\frac{25}{2}}$. For $x_{2i-1}=0$ and $x_{2i}=\frac{1}{2}$ we see that equality is achieved; next we show that this is an upper bound. Claim: Let $a, b, c, d$ be non-negative real numbers with $a+b+c \leqslant 1$ and $b+c+d \leqslant 1$. Then, $$ac+bd \leqslant \frac{1}{4}.$$ (Proof) Notice that $$ac+bd \leqslant ac+d(1-d-c)=d(1-d)+c(a-d),$$ and similarly, $$ac+bd \leqslant a(1-a-b)+bd=a(1-a)-b(a-d).$$ Note that for $x \in [0,1]$ we have $x(1-x) \le \frac{1}{4}$ and one of the inequalities $a \geqslant d$ or $d \geqslant a$ must hold; hence the claim is valid. $\blacksquare$ Evidently, from the previous claim we see that $$\sum^{100}_{i=1} x_ix_{i+2}=\frac{1}{2} \sum^{100}_{i=1} (x_ix_{i+2}+x_{i+1}x_{i+3}) \leqslant \frac{100}{8}=\frac{25}{2},$$ as desired. $\blacksquare$

We claim the maximal value is $\boxed{25/2}$, achieved when $x_i=1/2$ when $i$ even and $0$ when $i$ odd. We'll now show that $S\le 25/2$. Claim: We have $$x_1x_3+x_2x_4\le 1/4.$$ Proof: Let $a=x_1+x_2+x_3$ and $b=x_2+x_3+x_4$. Then, $$\begin{align*} x_1x_3+x_2x_4 &= x_1(a-x_1-x_2)+x_2(b-x_2-a+x_2+x_3) \\ &= a(x_1-x_2)+bx_2-x_1^2. \end{align*}$$ If $x_1\ge x_2$, then we can say $$x_1x_3+x_2x_4\le 1\cdot(x_1-x_2)+1\cdot x_2-x_1^2=x_1-x_1^2\le 1/4.$$ If $x_1\le x_2$, then since $a\ge x_1+x_2$, we have $$x_1x_3+x_2x_4\ge(x_1+x_2)(x_1-x_2)+1\cdot x_2-x_1^2=x_2-x_2^2\le 1/4,$$ so in all cases, $x_1x_3+x_2x_4\le 1/4$, as desired. $\blacksquare$ The claim clearly generalizes to $x_ix_{i+2}+x_{i+1}x_{i+3}\le 1/4$, so summing over odd $i$ gives the desired result.

Cool! orl wrote: Let $x_1, \ldots , x_{100}$ be nonnegative real numbers such that $x_i + x_{i+1} + x_{i+2} \leq 1$ for all $i = 1, \ldots , 100$ (we put $x_{101 } = x_1, x_{102} = x_2).$ Find the maximal possible value of the sum $S = \sum^{100}_{i=1} x_i x_{i+2}.$ Proposed by Sergei Berlov, Ilya Bogdanov, Russia We have $$x_i \cdot x_{i+2} + x_{i+1}\cdot x_{i+3} \le (1-x_{i+1} - x_{i+2}) \cdot (x_{i+2}) + (1 - x_{i+1}-x_{i+2})\cdot x_{i+1} = (1-x_{i+1}-x_{i+2})\cdot (x_{i+1}+x_{i+2}) \le \frac{1}{4} \iff S \le 50 \cdot \frac{1}{4} = \frac{25}{2} \blacksquare$$

redacted.

Quite surprisingly, the dumbest bound I can think of works. Note that $x_1x_3+x_2x_4\leq (1-x_1-x_2)x_3+(1-x_1-x_2)x_2=(1-x_1-x_2)x_2x_3\leq \frac{1}{4}.$ Since there are $50$ pairs, the upper bound is $\frac{25}{2}.$ To show that this works, take the construction $(\frac{1}{2},0,\frac{1}{2},0,\ldots).$

let $x_i+x_{i+1}=z_i$, then $\forall i$ note the inequality $$x_{i-1}x_{i+1}+x_ix_{i+2} \leq (1-x_i-x_{i+1}) x_{i+1} + x_i (1-x_i x_{i+1} = (x_i+x_{i+1})-(x_i+x_{i+1})^2= z_i\cdot (1-z_i) \leq \left(\frac{z_i+(1-z_i)}{2}\right)^2=\frac{1}{4}$$ Tthis clearly means that $$S\leq 50\cdot \frac{1}{4} = \frac{25}{2}$$ equality is achievable when $x_{odd}=0$ and $x_{even}=\frac{1}{2}$. $\textbf{Remark }$ : I was quite surprised that there is no solution where you separately consider odds and evens, instead the only solutions seems to be brutally mashing together adjacent terms. Given $E=$ sum of the evens, it is very difficult to bound the $\sum x_{2i}x_{2i+2}$, it is not true that setting all equal is optimal , nor is setting as many $\frac{1}{2}$s. The setting as many $\frac{1}{2}$s as possible seems optimal for large enough $E$, but for small E it fails (for example $\frac{1}{3},\frac23,\frac13$ vs. $\frac{1}{2},\frac{1}{2},\frac13$.), so it seems that the philosophically more motivated solution of seperately considering odds and evens fails

Lemma: $a,b,c,d$ nonnegativa real numbers.If $a+b+c \leq 1$ and $b+c+d \leq 1$ $\implies$ $ac + bd \leq \frac{1}{4}$ Proof: $$ac \leq c(1-b-c)$$ $$bd \leq b(1-b-c)$$ $$ac+bd \leq (b+c)(1-b-c) \leq \frac{1}{4}.$$ By lemma $S = \sum^{100}_{i=1} x_i x_{i+2} \leq \frac{50}{4}.$

Answer: $\frac{50}{4}$, and the example is when $x_{2k}=1/2$ otherwise $x_i=0$ Claim:For any $i=1,2,\dots,100$: $x_ix_{i+2}+x_{i+1}x_{i+3} \leq \frac{1}{4}$ Proof: $$x_ix_{i+2}+x_{i+1}x_{i+3} \leq x_{i+2}(1-x_{i+2}-x_{i+1})+x_{i+1}(1-x_{i+2}-x_{i+1})$$ $$x_ix_{i+2}+x_{i+1}x_{i+3} \leq (1-x_{i+2}-x_{i+1})(x_{i+2}+x_{i+1})\leq \frac{1}{4}$$ The last part is by AM-AG. $\square$ Finally: $S = \sum^{100}_{i=1} x_i x_{i+2} \implies 2S = \sum^{100}_{i=1} x_i x_{i+2}+x_{i+1} x_{i+3} \leq \frac{100}{4} \implies S\leq \frac{50}{4}$ So we are done.

Note that we have $$x_ix_{i+2}+x_{i+1}x_{i+3}\leq x_{i+2}(1-x_{i+1}-x_{i+2})+x_{i+1}(1-x_{i+1}-x_{i+2})=(x_{i+1}+x_{i+2})(1-(x_{i+1}+x_{i+2})) \leq \frac{1}{4},$$ so $S$ has maximum $\frac{25}{2}$, achieved by setting $x_{\text{odd}}=\frac{1}{2}$ and $x_{\text{even}}=0$. $\blacksquare$

We claim that the maximum is $\frac{25}{2}$ when $(\frac{1}{2},0,\frac{1}{2},0,\dots).$ Since $$x_ix_{i+2}+x_{i+1}x_{i+3}\le (1-x_{i+1}-x_{i+2})x_{i+2}+x_{i+1}(1-x_{i+1}-x_{i+2})=(1-x_{i+1}-x_{i+2})(x_{i+1}+x_{i+2})\le \frac{1}{4}$$ and there are $50$ of these pairs, $S\le \frac{25}{2}.$

We claim that the answer is 12.5. This can be achieved by alternating 1/2 and 0. Consider four consecutive terms in the circle, $a,b,c,d$. Claim: $ac+bd\leq 1/4.$ We have $a+b+c\leq 1$ and $b+c+d\leq 1$. WLOG that $a\geq d$. Then, we have $b+c\leq 1-a$. Additionally, since $a\geq d$, and $b+c \leq 1-a$, $ac+bd$ is maximized when $c=1-a$ and $b=0$, so this becomes $a(1-a)$, and since $a(1-a)\leq 1/4$, this shows the claim. Summing this claim over every pair of terms in the sum gives that it is at most 12.5, so we are done.

..what? It's evident by the given condition and AM-GM that $$x_kx_{k+2}+x_{k+1}x_{k+3}\le x_{k+2}(1-x_{k+1}-x_{k+2})+x_{k+1}(1-x_{k+1}-x_{k+2})=(x_{k+1}+x_{k+2})(1-(x_{k+1}+x_{k+2}))\le\frac14;$$ in particular, over all 100 terms this occurs 50 times, so the maximum is $\frac{50}2,$ with equality at $x_{2n+1}=\frac12,x_{2n}=0$.

We claim that the maximum possible value is $\frac{25}{2}$, which is achievable by alternating $\frac{1}{2}$ and $0$. Claim: Suppose that $x_1 + x_2 + x_3 \le 1, x_2 + x_3 + x_4 \le 1$. Then $x_1x_3 + x_2x_4 \le \frac14$. Proof. WLOG we can assume that $x_1 + x_2 + x_3 = x_2 + x_3 + x_4 = 1$, so $x_1 = x_4$. As such, this simplifies as $x_1(x_2 + x_3) = x_1(1 - x_1) \le \frac{1}{4}$. $\blacksquare$ Applying this $50$ times on $x_{2k+1}x_{2k+3} + x_{2k+2}x_{2k+4}$ finishes.

Can anyone identify what is wrong with my Sol.

i will grind and grind and grind. allan needs to stop being arrogant. allan needs to get better at math. after some thinking i came up with this: Consider the four-variable case with $(a,b,c,d)$. Using only $a+b+c\le 1$ and $b+c+d\le 1$, we can obtain $b+c\in [0,1]$ and $$ac+bd\le (b+c)(1-(b+c))\le \frac{1}{4}.$$ So the answer for the four variable case is $$ac+bd+ca+db\le \frac{1}{2}.$$ Extending the argument, $$x_ix_{i+2}+x_{i+1}x_{i+3}\le (x_{i+1}+x_{i+2})(1-x_{i+1}-x_{i+2})\le \frac{1}{4}$$ hence summing yields $2S\le 25$ or $S\le \frac{25}{2}$. This is achieveable when $x_{2k}=\frac{1}{2}$ and $x_{2k+1}=0$. $\blacksquare$

cute

Easier than A2 For $1\leq k\leq 50$, let $t=\max(x_{2k-1},x_{2k+2})$ and note that $t+x_{2k+1}+x_{2k}\leq 1$. So we have, $$x_{2k-1}x_{2k+1}+x_{2k}x_{2k+2} \leq t(x_{2k+1}+x_{2k})\leq t(1-t)=\frac 14-\left (t-\frac 12\right)^2\leq \frac 14.$$ And, $$S=\sum_{k=1}^{50} (x_{2k-1}x_{2k+1}+x_{2k}x_{2k+2})\leq \sum_{k=1}^{50} \frac 14=\frac{25}2.$$ Equality holds, for instance, when $x_i=\begin{cases} 1/2 & i \text{ odd} \\ 0 & i \text{ even} \end{cases}$. This proves that the maximal value is $\frac{25}2$.

The answer is $\frac{25}2$. Equality is achieved when $a_{2k-1} = \frac 12$ and $a_{2k} = 0$ for all $1 \leq k \leq 50$. To show the bound, write $$\begin{align*} \sum_{i=1}^{100} x_ix_{i+2} &= \sum_{k=1}^{50} x_{2k-1}x_{2k+1} + x_{2k}x_{2k+2} \\ &\leq \sum_{k=1}^{50} x_{2k+1}\left(1-x_{2k}-x_{2k+1}\right) + x_{2k}\left(1-x_{2k+1}-x_{2k}\right) \\ &\leq \sum_{k=1}^{50} \left(x_{2k}+x_{2k+1}\right)\left(1-x_{2k}-x_{2k+1}\right) \\ &\leq 50 \cdot \frac 14 = \frac{25}2. \end{align*}$$ Remark: The equality case almost fully motivates the solution because we want a bound that is sharp when $a_{2k} + a_{2k+1} = \frac 12$ is constant.