OBM 2020 - Nível 2 - P3

Problema 3.

Consideremos uma sequência infinita $x_1$, $x_2,\dots$ de números inteiros positivos tais que, para todo inteiro $n \geq 1$:

• Se $x_n$ é par, então $x_{n+1} = \frac{x_n}{2}$;
• Se $x_n$ é ímpar, então $x_{n+1} = \frac{x_n - 1}{2} + 2^{k-1}$, onde $k$ é o inteiro tal que $2^{k-1} \leq x_n < 2^k$.

Determine o menor valor possível de $x_1$ para o qual a sequência contenha algum termo igual a $2020$.

Solução de João Ferreira.

Seja $\overline{a_1 a_2 a_3 \dots a_m} = x_n$ a representação binária de $x_n$ ($a_i \in \{0, 1\} \forall i$).

Se $x_n$ é par, $a_m = 0$ e $x_{n+1} = \overline{a_1 a_2 a_3 \dots a_{m-1} 0} \cdot \frac{1}{2}$

$= \overline{a_1 a_2 a_3 \dots a_{m-1}}$.

Se $x_n$ é ímpar, $a_m = 1$ e $x_{n+1} = \dfrac{\overline{a_1 a_2 a_3 \dots a_{m-1} 1} - 1}{2} + 2^{m - 1}$

$= \overline{a_1 a_2 a_3 \dots a_{m-1}} + \overline{1\underbrace{00\dots 00}_{m - 1 \text{ zeros}}}$

$= \overline{1a_1 a_2 a_3 \dots a_{m-1}}$.

Desta forma, nossas operações removem um $0$ do final ou movem um $1$ do final para o começo.

Como $2020 = \overline{11111100100}$ e $x_1 \leq 2020$, $x_q=2020$ tem que ser um resultado de aplicações da segunda operação, portanto podemos realizar o inverso da segunda operação para descobrir o menor $x_1$ possível.

$2020 = \overline{11111100100} \leftarrow \overline{11111001001} \leftarrow \dots \leftarrow \overline{10010011111} = 1183$

Não podemos mais realizar o inverso da primeira operação, pois obteríamos um número de $11$ dígitos na base $2$ que começa com um $0$.

Consequentemente a resposta do problema é $x_1 = 1183$.