OBM 2018 - Nível 3 - P4

Problema 4

Esmeralda escreve $2n$ números reais $x_1, x_2,\dots, x_{2n}$, todos pertencentes ao intervalo $[0, 1]$, ao redor de um círculo e multiplica todos os pares de números vizinhos consecutivos entre si, obtendo, no sentido anti-horário, os produtos $p_1=x_1x_2, p_2=x_2x_3,\dots, p_{2n}=x_{2n}x_1$. Ela soma os produtos de índice par e subtrai os produtos de índice ímpar. Qual é o maior resultado que Esmeralda pode obter?

Solução de João Rafael:

Seja $S=-x_1x_2+x_2x_3-\dots+x_{2n}x_1=x_2(x_3-x_1)+x_4(x_5-x_3)+\dots+x_{2n}(x_1-x_{2n-1})$

Para maximizar o resultado podemos definir:

$x_{2a}=\begin{cases} 1\mbox{ se }(x_{2a+1}-x_{2a-1})>0 \\ 0\mbox{ se }(x_{2a+1}-x_{2a-1})\leq0\end{cases}$ pois assim maximizamos as parcelas positivas e deixamos as não-positivas iguais a $0$, maximizando $S$.

Considere, assim, os índices $2a_1, 2a_2,\dots, 2a_k$, com $k\leq n$, tais que $x_{2a_i}=1$. Assim podemos reescrever $S$ como:

$S=x_{2a_1}(x_{2a_1+1}-x_{2a_1-1})+x_{2a_2}(x_{2a_2+1}-x_{2a_2-1})+\dots+x_{2a_k}(x_{2a_k+1}-x_{2a_k-1})$ que se rearranjarmos nos dão:

$S=(x_{2a_1+1}+x_{2a_2+1}+\dots+x_{2a_k+1})-(x_{2a_1-1}+x_{2a_2-1}+\dots+x_{2a_k-1})$, pois as demais parcelas são $0$. Caso para algum $i=\{1,2,\dots ,k\}$, tivermos:

$x_{2a_i+1}=x_{2a_{i+1}-1}$, eles poderão se cancelar na soma acima nos deixando com $2j\leq k$ números distintos. Note agora que

$2j\leq k\leq n\Rightarrow 2j\leq n\Rightarrow j\leq\frac{n}{2}\Rightarrow \lfloor j\rfloor\leq\lfloor\frac{n}{2}\rfloor$ . Porém, como $j\in\mathbb{Z}$ temos que $j\leq\lfloor\frac{n}{2}\rfloor$

Assim podemos ver que para maximizar $S$ devemos ter todo as parcelas somando iguais a $1$ e todos as parcelas subtraindo iguais a $0$. Como temos $j$ termos somando e $j$ termos subtraindo então: $S\leq j \leq\lfloor\frac{n}{2}\rfloor$ sendo então $\lfloor\frac{n}{2}\rfloor$ o maior valor possível de S. Para termos a igualdade podemos fazer, por exemplo:

$x_{4k}=x_{4k+1}=1$ e $x_{4k+2}=x_{4k+3}=0$ pois assim $x_{4k+3}-x_{4k+1}=0-1=-1$ teria coeficiente $x_{4k+2}=0$ e $x_{4(k+1)+1}-x_{4k+3}=1-0=1$ teria coeficiente $x_{4(k+1)}=1$ maximizando nossa soma como já provamos.$\blacksquare$

RESPOSTA: $\lfloor\frac{n}{2}\rfloor$

Obs$_1$: A função parte inteira apareceu pois caso $n$ seja ímpar teriamos que o maior valor de $j$ seria um número decimal ($\frac{n}{2}$), o que é impossível pois $j$ é inteiro. Por isso, a parte inteira desse número será o maior valor de $j$.

Obs$_2$:Note que na solução estamos olhando para os índices módulo $2n$. Sempre que aparecer $x_{2n+1}$, por exemplo, estamos falando do $x_1$.