Maximum value of a cyclic sum

57 Views Asked by At

Esmeralda writes $2n$ real numbers $x_1, x_2, \dots , x_{2n}$, all belonging to the interval $[0, 1]$, around a circle and multiplies all the pairs of numbers neighboring to each other, obtaining, in the counterclockwise direction, the products $p_1 = x_1x_2$, $p_2 = x_2x_3$, $\dots$ , $p_{2n} = x_{2n}x_1$. She adds the products with even indices and subtracts the products with odd indices. What is the maximum possible number Esmeralda can get?

Adjust every $x_i\in\{0,1\}$.

Then we get some paragraph of 0 and 1. We can adjust 1 such that every 1 contain at most two 1s.

How do I proceed in a more formalized way?

1

There are 1 best solutions below

1
On BEST ANSWER

Let $P = - x_1x_2 + x_2x_3 - x_3x_4 + \ldots + x_{2n}x_1 $ be the expression we want to maximize.
Like you suggested, since $P$ is linear in each of the $x_i$, hence the maximum occurs when $x_i \in \{ 0, 1 \}$.

Hint: $P = x_1 (x_{2n} - x_2) + x_3 (x_2 - x_4) + \ldots + x_{2n-1} (x_{2n-2} - x_{2n})$.

Let $a_i = x_{2(i-1)} - x_{2i}$ for $ i = 1$ to $n$.
Clearly, $a_i \in \{ 1, 0, -1 \}$ and $\sum a_i = 0$.

Hint: $ P \leq $ the number of $a_i$ which is equal to 1.
Hence $ P \leq \lfloor \frac{n}{2} \rfloor$. Can equality hold?