Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 2k<n2k+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 2k. Usamos indução:

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

Agora, suponha que marcamos n após n passos. Considere a configuração de n1 pontos marcados (não inclui os iniciais) obtida ao removermos o ponto marcado no passo n. O diâmetro nela  é no máximo 2n1 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 22n1=2n.

Isto mostra que precisamos de no mínimo k+1 passos para marcar n>0 onde 2k<n2k+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: [2n1+1,2n] pode ser marcado com, no máximo,  n passos.

Passo: Tome um M no intervalo: [2n+1,2n+1].

  • M é par: Como marcamos M2 com até n passos, basta tomar o reflexo de 0 por M2. Logo, usamos mais um passo, totalizando n+1
  • M é ímpar: Como marcamos M+12 com n passos, basta tomar o reflexo de 1 por M2 e marcamos M com n+1 passos.

Conclusão: f(n)=k+1 onde 2k<n2k+1 e n>0.

Agora, f(n)=f((n1)) pois ambos são simétricos por 12, logo o problema é o mesmo.

Com isso, sabemos as respostas para todos inteiros.