OBM 2022 - Nível 3 - P4

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!