Задача №17307

Дано натуральное число $n\text{.}$ За один ход разрешается либо прибавить к числу его наибольший делитель, не равный самому числу ($d_{\max }<n$), либо вычесть из числа его наименьший делитель, больший 1 ($d_{\min }>1$).

а) Можно ли за несколько таких ходов из числа 4 получить число 15?
б) Можно ли за несколько таких ходов из числа 10 получить число 13?
в) Какое наименьшее количество ходов потребуется, чтобы из числа 2 получить число 60?

Правила: за один ход к натуральному $n$ либо прибавить $d_{\max }(n)$ — наибольший делитель, меньший $n\text{,}$ либо вычесть $d_{\min }(n)$ — наименьший простой делитель $n\text{.}$ Заметим, что $d_{\max }(n)=n/d_{\min }(n)\text{.}$

а) Построим явную цепочку:

$$4\stackrel{+2}{\to }6\stackrel{+3}{\to }9\stackrel{+3}{\to }12\stackrel{-2}{\to }10\stackrel{+5}{\to }15.$$

Проверка ходов:
1. $4=2^2\text{,}$ $d_{\max }=2\text{,}$ $4+2=6\text{.}$
2. $6=2\cdot 3\text{,}$ $d_{\max }=3\text{,}$ $6+3=9\text{.}$
3. $9=3^2\text{,}$ $d_{\max }=3\text{,}$ $9+3=12\text{.}$
4. $12=2^2\cdot 3\text{,}$ $d_{\min }=2\text{,}$ $12-2=10\text{.}$
5. $10=2\cdot 5\text{,}$ $d_{\max }=5\text{,}$ $10+5=15\text{.}$

Можно, за 5 ходов.

б) Покажем, что число 13 недостижимо никаким ходом из любого натурального $n\text{.}$ Пусть $n\to 13\text{.}$ Возможны два варианта.

1. $n+d_{\max }(n)=13\text{.}$ Если $n$ простое, $d_{\max }(n)=1\text{,}$ тогда $n+1=13\text{,}$ $n=12$ — не простое, противоречие. Если $n$ составное, $d_{\max }(n)=n/p\text{,}$ где $p=d_{\min }(n)⩾2\text{,}$ поэтому $n+n/p=13\text{.}$ Перебор:

• $p=2\text{:}$ $\frac{3n}{2}=13\Rightarrow n=\frac{26}{3}\text{,}$ не целое;
• $p=3\text{:}$ $\frac{4n}{3}=13\Rightarrow n=\frac{39}{4}\text{,}$ не целое;
• $p=5\text{:}$ $\frac{6n}{5}=13\Rightarrow n=\frac{65}{6}\text{,}$ не целое.

Прямой перебор $n⩽12\text{:}$ $n=9$ даёт 12, $n=10\to 15\text{,}$ $n=11\to 12\text{,}$ $n=12\to 18\text{.}$ Ни одно значение не даёт 13.

2. $n-d_{\min }(n)=13\text{,}$ то есть $n=13+p\text{,}$ где $p=d_{\min }(n)\text{.}$

• Если $p=2$ (т.е. $n$ чётное), то $n=15$ — нечётное, противоречие.
• Если $p⩾3$ (т.е. $n$ нечётное), то $13+p$ — чётное (нечёт + нечёт), противоречие с нечётностью $n\text{.}$

Таким образом, число 13 нельзя получить ни одним ходом. В частности, из 10 в 13 попасть нельзя.

в) Рассмотрим путь из 2 в 60.

$$2\stackrel{+1}{\to }3\stackrel{+1}{\to }4\stackrel{+2}{\to }6\stackrel{+3}{\to }9\stackrel{+3}{\to }12\stackrel{-2}{\to }10\stackrel{+5}{\to }15\stackrel{+5}{\to }20\stackrel{+10}{\to }30\stackrel{+15}{\to }45\stackrel{+15}{\to }60.$$

Это 11 ходов. Каждый ход выполнен по правилам:

• Простые 2, 3: $d_{\max }=1\text{.}$
• $4\to 6,6\to 9,9\to 12,10\to 15,15\to 20,20\to 30,30\to 45,45\to 60$ — прибавление наибольшего делителя.
• $12\to 10$ — вычитание $d_{\min }=2\text{.}$

Для проверки минимальности используем поиск в ширину (BFS):

Анализ показывает, что число 60 впервые появляется на 11-м уровне.

Ответ:

а) Да

б) Нет

в) 11