Problema 4
Inicialmente um número está escrito no quadro. Então, a cada minuto, Esmeralda escolhe um divisor $$d > 1$$ do número $$n$$ escrito na lousa, apaga $$n$$ e escreve $$n + d$$. Se o número inicial é $$2022$$, qual é
o maior número composto que Esmeralda nunca poderá escrever no quadro?
Solução por Luca Zanardi:
Primeiramente, note que todo número par $$\geq 2022$$ pode aparecer no quadro, pois basta escolher $$2$$ como o divisor do número, e daí como $$2$$ divide o número atual, também dividirá ele $$+2$$. A partir daí, considere $$k$$ o maior número que não pode ser escrito (a resposta do problema). Note que $$k$$ será ímpar, e se um primo ímpar $$p | k$$, então $$k – p < 2022$$. Isso ocorre pois $$k – p$$ é par, então se fosse maior que 2022, poderia ser escrito. Como $$p | k$$, e $$p | p$$, $$p | k – p \implies k – p + p = k$$ também pode ser escrito (Absurdo!). Porém, veja que, para qualquer primo ímpar, os números $$2022$$, $$2022 + 2$$, $$\dots$$, $$2022 + 2(p – 1)$$ formam um sistema completo de resíduos (esses números, em alguma ordem, deixam resto $$0$$, $$1$$, $$\dots$$, $$p-1$$ na divisão por $$p$$). Assim, teremos um múltiplo de $$p$$ menor ou igual a $$2022 + 2(p – 1) = 2020 + 2p$$. Sendo $$p$$ o menor primo que divide $$k$$, teremos que o primeiro múltiplo de $$p$$ que pode ser escrito deve ser maior do que $$k$$ (caso contrário, atingiríamos ele e iríamos saltando de múltiplo de $$p$$ em múltiplo de $$p$$). Assim, obteremos:
$$2022 + 2(p – 1) = 2020 + 2p \geq$$ [Múltiplo de $$p$$ que pode ser escrito] $$\geq$$ [Primeiro múltiplo de $$p$$ que pode ser escrito] $$> k$$. Como $$p$$ é o menor primo que divide $$k$$, e $$k$$ é composto, $$k \geq p^2$$ $$\implies 2020 + 2p > p^2$$.
Olhando as raízes da equação $$p^2 – 2p – 2020$$, obtemos que $$p = \frac{-(-2) \pm \sqrt{(-2)^2 – 4\cdot 1 \cdot (-2020)}}{2\cdot 1} = 1 \pm \sqrt{2021}$$. Assim, $$p \in (1 – \sqrt{2021}, 1 + \sqrt{2021})$$. Como $$\sqrt{2021} < \sqrt{2025} = 45$$, obtemos que $$p < 45 + 1 = 46$$. Como $$p$$ é primo, obtemos $$p \leq 43$$.
Agora, testaremos os casos em que $$p$$ varia entre $$3$$ e $$43$$.
(Lembrando que, para $$p|k$$, o primeiro múltiplo de $$p$$ maior que 2022 deve ser impossível de se obter).
Caso $$1$$: $$p = 3$$:
Nesse caso, $$2022$$ por si só já é múltiplo de $$3$$, então todo múltiplo de $$3$$ maior que 2022 pode ser escrito.
Caso $$2$$: $$p = 5$$:
Nesse caso, o primeiro múltiplo de $$5$$ maior que $$2022$$ é $$2025$$, que pode ser obtido com $$2022 \rightarrow 2022+3 = 2025$$. A partir daí, todo múltiplo de $$5$$ pode ser obtido.
Caso $$3$$: $$p = 7$$: $$(*)$$
Nesse caso, o primeiro múltiplo de $$7$$ maior que $$2022$$ é $$2023$$, que não pode ser obtido. A partir daí, o segundo múltiplo de 7 é 2030, que pode ser obtido com $$2022 \rightarrow 2022 + 3 = 2025 \rightarrow 2025 + 5 $$ $$= 2030$$, e depois disso, todo múltiplo de $$7$$ pode ser obtido.
Caso $$4$$: $$p = 11$$:
Nesse caso, o primeiro múltiplo de $$11$$ maior que $$2022$$ é $$2024$$, que pode ser obtido com $$2022 \rightarrow 2022+2 = 2024$$. A partir daí, todo múltiplo de $$11$$ pode ser obtido.
Caso $$5$$: $$p = 13$$:
Nesse caso, o primeiro múltiplo de $$13$$ maior que $$2022$$ é $$2028$$, que pode ser obtido com $$2022 \rightarrow 2022+2 = 2024 \rightarrow 2024 + 4 = 2028$$. A partir daí, todo múltiplo de $$13$$ pode ser obtido.
Caso $$6$$: $$p = 17$$: $$(*)$$
Nesse caso, o primeiro múltiplo de $$17$$ maior que $$2022$$ é $$2023$$, que não pode ser obtido. A partir daí, o segundo múltiplo de 17 é 2040, que pode ser obtido com $$2022 \rightarrow 2022 + 3 = 2025 \rightarrow 2025 + 15$$ $$= 2040$$, e depois disso, todo múltiplo de $$17$$ pode ser obtido.
Caso $$7$$: $$p = 19$$: $$(*)$$
Nesse caso, o primeiro múltiplo de $$17$$ maior que $$2022$$ é $$2033$$, que não pode ser obtido (provaremos depois). A partir daí, o segundo múltiplo de 19 é 2052, que pode ser obtido com $$2022 \rightarrow 2022+2 = 2024\rightarrow 2024 + 2 = 2026 \rightarrow \dots \rightarrow 2052$$, e depois disso, todo múltiplo de $$19$$ pode ser obtido.
Caso $$8$$: $$p = 23$$:
Nesse caso, o primeiro múltiplo de $$23$$ maior que $$2022$$ é $$2024$$, que pode ser obtido com $$2022 \rightarrow 2022+2 = 2024$$. A partir daí, todo múltiplo de $$23$$ pode ser obtido.
Caso $$9$$: $$p = 29$$:
Nesse caso, o primeiro múltiplo de $$29$$ maior que $$2022$$ é $$2030$$, que pode ser obtido com $$2022 \rightarrow 2022+3 = 2025 \rightarrow 2025 + 5 = 2030$$. A partir daí, todo múltiplo de $$29$$ pode ser obtido.
Caso $$10$$: $$p = 31$$:
Nesse caso, o primeiro múltiplo de $$31$$ maior que $$2022$$ é $$2046$$, que pode ser obtido com $$2022 \rightarrow 2022+2 = 2024\rightarrow 2024 + 2 = 2026 \rightarrow \dots \rightarrow 2046$$. A partir daí, todo múltiplo de $$31$$ pode ser obtido.
Caso $$11$$: $$p = 37$$:
Nesse caso, o primeiro múltiplo de $$37$$ maior que $$2022$$ é $$2035$$, que pode ser obtido com $$2022 \rightarrow 2022+3 = 2025 \rightarrow 2025 + 5 = 2030 \rightarrow 2030 + 5 = 2035$$. A partir daí, todo múltiplo de $$37$$ pode ser obtido.
Caso $$12$$: $$p = 41$$:
Nesse caso, o primeiro múltiplo de $$41$$ maior que $$2022$$ é $$2050$$, que pode ser obtido com $$2022 \rightarrow 2022+3 = 2025 \rightarrow 2025 + 25 = 2050$$. A partir daí, todo múltiplo de $$41$$ pode ser obtido.
Caso $$13$$: $$p = 43$$:
Nesse caso, o primeiro múltiplo de $$43$$ maior que $$2022$$ é $$2064$$, que pode ser obtido com $$2022 \rightarrow 2022+2 = 2024\rightarrow 2024 + 2 = 2026 \rightarrow \dots \rightarrow 2064$$. A partir daí, todo múltiplo de $$43$$ pode ser obtido.
Assim, concluímos que, sendo $$k$$ nossa resposta e $$p|k$$ o menor divisor do mesmo, $$p$$ deve ser menor ou igual a 43, e desses, pode ser apenas $$7$$, $$17$$ ou $$19$$ (Símbolos com $$(*)$$), fazendo os $$k$$’s possíveis serem $$2023$$ ou $$2033$$. Agora, basta provar que $$2033$$ é impossível.
Suponha que 2033 fosse possível. Veja que $$2033 = 19\cdot 107 \implies$$ se fosse possível escrevê-lo no quadro, teríamos que $$2033 = x + d$$, onde $$x = d\cdot x_0$$, $$d > 1$$ e $$x \geq 2022$$. Daí, $$19\cdot 107 = d(x_0 + 1) \implies d = 19$$ ou $$107\implies d \geq 19$$. Porém, sabemos que $$2023 = x + d \geq 2022 + 19 = 2041 \rightarrow$$ Absurdo! Logo, como $$2033$$ é o maior número da nossa lista de possíveis $$k$$’s, e realmente não pôde ser escrito, essa é a nossa resposta!