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$$.