|
|
 |
Условие
Дано натуральное число 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 и не превышающее N+125=0,2N+2,4, что строго меньше N при N>3. Иными словами, после каждого деления на 5 Верины числа уменьшаются, пока не получится число 1 или 2. Но из числа 2 за два шага также получается число 1.
Комментарий. Формулировка этой задачи похожа на известную открытую проблему — гипотезу Коллатца. С данным натуральным числом N проводится следующая операция: если N чётно, то оно делится на 2, а если нечётно, то оно умножается на 3 и к результату прибавляется 1 (получается число 3N+1), после чего процесс повторяется. Гипотеза состоит в том, что рано или поздно в результате таких операций получится единица.
На данный момент с использованием распределенных вычислений гипотеза проверена до чисел порядка 1021, в наиболее сложных случаях для получения единицы требуется порядка 3000 шагов.
Ответ
3k,k∈N.
