A3. 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_{i=1}^{100} x_{i} x_{i+2}
$$
Answer. $\frac{25}{2}$.
Solution 1. Let $x_{2 i}=0, x_{2 i-1}=\frac{1}{2}$ for all $i=1, \ldots, 50$. Then we have $S=50 \cdot\left(\frac{1}{2}\right)^{2}=\frac{25}{2}$. So, we are left to show that $S \leq \frac{25}{2}$ for all values of $x_{i}$ 's satisfying the problem conditions.

Consider any $1 \leq i \leq 50$. By the problem condition, we get $x_{2 i-1} \leq 1-x_{2 i}-x_{2 i+1}$ and $x_{2 i+2} \leq 1-x_{2 i}-x_{2 i+1}$. Hence by the AM-GM inequality we get
$$
\begin{aligned}
x_{2 i-1} x_{2 i+1} & +x_{2 i} x_{2 i+2} \leq\left(1-x_{2 i}-x_{2 i+1}\right) x_{2 i+1}+x_{2 i}\left(1-x_{2 i}-x_{2 i+1}\right) \\
& =\left(x_{2 i}+x_{2 i+1}\right)\left(1-x_{2 i}-x_{2 i+1}\right) \leq\left(\frac{\left(x_{2 i}+x_{2 i+1}\right)+\left(1-x_{2 i}-x_{2 i+1}\right)}{2}\right)^{2}=\frac{1}{4} .
\end{aligned}
$$

Summing up these inequalities for $i=1,2, \ldots, 50$, we get the desired inequality
$$
\sum_{i=1}^{50}\left(x_{2 i-1} x_{2 i+1}+x_{2 i x_{2 i+2}}\right) \leq 50 \cdot \frac{1}{4}=\frac{25}{2} .
$$

Comment. This solution shows that a bit more general fact holds. Namely, consider $2 n$ nonnegative numbers $x_{1}, \ldots, x_{2 n}$ in a row (with no cyclic notation) and suppose that $x_{i}+x_{i+1}+x_{i+2} \leq 1$ for all $i=1,2, \ldots, 2 n-2$. Then $\sum_{i=1}^{2 n-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 $x_{1}, x_{2}, \ldots, x_{100}, x_{1}, x_{2}$

Solution 2. We present another proof of the estimate. From the problem condition, we get
$$
\begin{aligned}
S=\sum_{i=1}^{100} x_{i} x_{i+2} \leq \sum_{i=1}^{100} x_{i}\left(1-x_{i}-x_{i+1}\right) & =\sum_{i=1}^{100} x_{i}-\sum_{i=1}^{100} x_{i}^{2}-\sum_{i=1}^{100} x_{i} x_{i+1} \\
& =\sum_{i=1}^{100} x_{i}-\frac{1}{2} \sum_{i=1}^{100}\left(x_{i}+x_{i+1}\right)^{2} .
\end{aligned}
$$

By the AM-QM inequality, we have $\sum\left(x_{i}+x_{i+1}\right)^{2} \geq \frac{1}{100}\left(\sum\left(x_{i}+x_{i+1}\right)\right)^{2}$, so
$$
\begin{aligned}
S \leq \sum_{i=1}^{100} x_{i}-\frac{1}{200}\left(\sum_{i=1}^{100}\left(x_{i}+x_{i+1}\right)\right)^{2} & =\sum_{i=1}^{100} x_{i}-\frac{2}{100}\left(\sum_{i=1}^{100} x_{i}\right)^{2} \\
& =\frac{2}{100}\left(\sum_{i=1}^{100} x_{i}\right)\left(\frac{100}{2}-\sum_{i=1}^{100} x_{i}\right) .
\end{aligned}
$$

And finally, by the AM-GM inequality
$$
S \leq \frac{2}{100} \cdot\left(\frac{1}{2}\left(\sum_{i=1}^{100} x_{i}+\frac{100}{2}-\sum_{i=1}^{100} x_{i}\right)\right)^{2}=\frac{2}{100} \cdot\left(\frac{100}{4}\right)^{2}=\frac{25}{2} .
$$

Comment. These solutions are not as easy as they may seem at the first sight. There are two different optimal configurations in which the variables have different values, and not all of sums of three consecutive numbers equal 1. Although it is easy to find the value $\frac{25}{2}$, the estimates must be done with care to preserve equality in the optimal configurations.