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<n≤2k+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 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 2n−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⋅2n−1=2n.
Isto mostra que precisamos de no mínimo k+1 passos para marcar n>0 onde 2k<n≤2k+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: [2n−1+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<n≤2k+1 e n>0.
Agora, f(n)=f(−(n−1)) pois ambos são simétricos por 12, logo o problema é o mesmo.
Com isso, sabemos as respostas para todos inteiros.