OBM 2019 - P2 - Solução

Problema 2

São dadas a reta real e os únicos pontos marcados $0$ e $1$. Podemos realizar quantas vezes quisermos a seguinte operação: tomamos dois pontos já marcados $a$ e $b$ e marcamos o simétrico de $a$ com relação a $b$. Seja $f(n)$ a quantidade mínima de operações necessárias para marcar na reta real o número $n$ (que é o número a uma distância $|n|$ do $0$ e está à direita de $0$ se $n >0$ e à esquerda de $0$ se $n < 0$). Por exemplo, $f(0) = f(1) = 0$ e $f(-1) = f(2) = 1$. Encontre $f(n)$.

Solução de Rodrigo Porto:

Seja $n>0$ um inteiro positivo tal que $2^k < n \leq 2^{k+1}$, afirmamos que $f(n)= k+1$.

Mostrando que não conseguimos atingir $n$ com menos passos:

Seja o diâmetro de uma configuração de pontos marcados, a diferença em módulo entre o maior e o menor deles. Mostraremos que o diâmetro de uma configuração após $k$ passos é no máximo $2^k$. Usamos indução:

• Base: $n=1$: Após $1$ passo, marcamos $-1$ ou $2$, em cada casos o diâmetro é : $1-(-1)=2$ e $2-0=2$. OK!

Agora, suponha que marcamos $n$ após n passos. Considere a configuração de $n-1$ pontos marcados (não inclui os iniciais) obtida ao removermos o ponto marcado no passo $n$. O diâmetro nela  é no máximo $2^{n-1}$ por hipótese. Note que o diâmetro da configuração que tínhamos é maximizado quando tomamos o simétrico de um dos pontos extremos pelo outro. Ou seja, o diâmetro no máximo dobra. Então é, de fato, no máximo $2\cdot 2^{n-1}=2^n$.

Isto mostra que precisamos de no mínimo $k+1$ passos para marcar $n>0$ onde $2^k < n \leq 2^{k+1}$.

Mostrando o exemplo:

Aqui prosseguimos por indução novamente:

Base: $n=1$: $2$ é obtido em um passo. $3$ e $4$ também podem ser obtidos em $2$ passos. (é só testar).

Hipótese de indução: Qualquer cara no intervalo: $[2^{n-1}+1,2^{n}]$ pode ser marcado com, no máximo,  n passos.

Passo: Tome um $M$ no intervalo: $[2^{n}+1,2^{n+1}]$.

• $M$ é par: Como marcamos $\dfrac{M}{2}$ com até n passos, basta tomar o reflexo de 0 por $\dfrac{M}{2}$. Logo, usamos mais um passo, totalizando $n+1$
• M é ímpar: Como marcamos $\dfrac{M+1}{2}$ com $n$ passos, basta tomar o reflexo de 1 por $\dfrac{M}{2}$ e marcamos $M$ com $n +1$ passos.

Conclusão: $f(n) = k+1$ onde $2^k < n \leq 2^{k+1}$ e $n>0$.

Agora, $f(n)= f(-(n-1))$ pois ambos são simétricos por $\dfrac{1}{2}$, logo o problema é o mesmo.

Com isso, sabemos as respostas para todos inteiros.