|
|
 |
Условие
Дано натуральное число $N$. Вера делает с ним следующие операции: сначала прибавляет 3 до тех пор, пока получившееся число не станет делиться на 5 (если изначально $N$ делится на 5, то ничего прибавлять не надо). Получившееся число Вера делит на 5. Далее делает эти же операции с новым числом, и так далее. Из каких чисел такими операциями нельзя получить 1?Решение
В самом деле, из чисел, кратных $3$, число $1$ получить не удастся, так как если число $N$ кратно $3$, то и $N + 3$ кратно $3$, а если $N = 5k$ кратно $3$, то и $k$ кратно $3$, так как $3$ и $5$ взаимно простые. А значит, все получающиеся в результате этих операций числа будут кратны $3$, но $1$ не делится на $3$.Пусть $N$ не кратно $3$. Заметим, что числа $N$, $N+3$, $N+6$, $N+9$ и $N+12$ также не кратны $3$ и имеют разные остатки при делении на $5$, значит, одно из них кратно $5$. Следовательно, после первой операции деления на $5$ Вера получит число, не кратное $3$ и не превышающее $\frac{N+12}{5} = 0{,}2N + 2{,}4$, что строго меньше $N$ при $N > 3$. Иными словами, после каждого деления на $5$ Верины числа уменьшаются, пока не получится число $1$ или $2$. Но из числа $2$ за два шага также получается число $1$.
Комментарий. Формулировка этой задачи похожа на известную открытую проблему — гипотезу Коллатца. С данным натуральным числом $N$ проводится следующая операция: если $N$ чётно, то оно делится на 2, а если нечётно, то оно умножается на 3 и к результату прибавляется 1 (получается число $3N+1$), после чего процесс повторяется. Гипотеза состоит в том, что рано или поздно в результате таких операций получится единица.
На данный момент с использованием распределенных вычислений гипотеза проверена до чисел порядка $10^{21}$, в наиболее сложных случаях для получения единицы требуется порядка 3000 шагов.
