(IMO SL 2010 A3) Let $x_{1}, \ldots, x_{100}$ be positive reals satisfying $x_{i}+x_{i+1}+x_{i+2} \leqslant 1$ for all $i \leqslant 100$ (with the convention $x_{101}=x_{1}$ and $x_{102}=x_{2}$). Determine the maximum value that

$$
S=\sum_{i=1}^{100} x_{i} x_{i+2}
$$

can take.
The idea here is to look at two consecutive terms of this sum and try to connect them using the hypothesis:

$$
x_{i} x_{i+2}+x_{i+1} x_{i+3} \leqslant\left(1-x_{i+1}-x_{i+2}\right) x_{i+2}+x_{i+1}\left(1-x_{i+1}-x_{i+2}\right)=\left(x_{i+1}+x_{i+2}\right)\left(1-\left(x_{i+1}+x_{i+2}\right)\right) \leqslant \frac{1}{4}
$$

using the inequality $x(1-x) \leqslant 1 / 4$ for all $x \in[0,1]$, which is the case for $x_{i+1}+x_{i+2}$. It remains to break down the sum into packets of four:

$$
S=\sum_{k=1}^{50}\left(x_{2 k-1} x_{2 k+1}+x_{2 k} x_{2 k+2}\right) \leqslant \sum_{k=1}^{50} \frac{1}{4}=\frac{25}{2}
$$

It remains to show that this value can be achieved. For this, we look at the case of equality of the inequalities we have used. Notably, for the inequalities used to be equalities, it is necessary that $x_{2 k}+x_{2 k+1}=\frac{1}{2}$. On the other hand, at least one of the two terms $x_{2 k-1}$ and $x_{2 k+2}$ must be $1 / 2$ to satisfy $x_{i}+x_{i+1}+x_{i+2}=1$. We then arrive at the construction $x_{2 k}=0$ and $x_{2 k+1}=1 / 2$ for all $k$, which we verify allows us to reach the maximum value.

## 5 LTE and Zsigmondy (Pierre-Marie)

## Course Elements

You can find the proofs of these course elements at the following address: https : //maths-olympiques.fr/wp-content/uploads/2017/09/arith_lte.pdf.

Theorem 1 (Lifting The Exponent Lemma, or LTE).

Let $p$ be a prime number, $x$ and $y$ integers coprime with $p$.

A) Case $p \neq 2$:

(i) If $p \mid x-y$ then $v_{p}\left(x^{n}-y^{n}\right)=v_{p}(x-y)+v_{p}(n)$

(ii) If $p \mid x+y$ and $n$ is odd then $v_{p}\left(x^{n}+y^{n}\right)=v_{p}(x+y)+v_{p}(n)$

B) Case $p=2$:

(i) If $2 \mid x-y$ and $n$ is even then $v_{2}\left(x^{n}-y^{n}\right)=v_{2}(x-y)+v_{2}(x+y)+v_{2}(n)-1$.

(ii) If $2 \mid x-y$ and $n$ is odd then $v_{2}\left(x^{n}-y^{n}\right)=v_{2}(x-y)$.

(iii) If $4 \mid x-y$ then $v_{2}\left(x^{n}-y^{n}\right)=v_{2}(x-y)+v_{2}(n)$.

Theorem 2 (Zsigmondy's Theorem).

Let $x>y>0$ be coprime integers. Let $u_{k}=x^{k}-y^{k}$ and $v_{k}=x^{k}+y^{k}$ for $k \geqslant 1$. We call a primitive prime factor of a term $s_{n}$ a prime number $p$ that divides $s_{n}$ but no previous term of the sequence $s$.

A) Except for the cases

- $n=2$ and $x+y$ is a power of 2,

- $n=6, x=2, y=1$,

every $u_{n}$ has a primitive prime factor.

B) Except for the case $n=3, x=2, y=1$, every $v_{n}$ has a primitive prime factor.

## Exercises