Дано натуральное число n . За один ход разрешается либо прибавить к числу его наибольший делитель, не равный самому числу ( d_() < n ), либо вычесть из числа его наименьший делитель, больший 1 ( d_() > 1 ). а) Можно ли за несколько таких ходов из числа 4 получить число 15? б) Можно ли за несколько таких ходов из числа 10 получить число 13? в) Какое наименьшее количество ходов потребуется, чтобы из числа 2 получить число 60?

Правила: за один ход к натуральному n либо прибавить d_()(n) — наибольший делитель, меньший n , либо вычесть d_()(n) — наименьший простой делитель n . Заметим, что d_()(n) = n/d_()(n) . а) Построим явную цепочку: 4 +2 6 +3 9 +3 12 -2 10 +5 15. Проверка ходов: 1. 4 = 2^2 , d_() = 2 , 4 + 2 = 6 . 2. 6 = 2 * 3 , d_() = 3 , 6 + 3 = 9 . 3. 9 = 3^2 , d_() = 3 , 9 + 3 = 12 . 4. 12 = 2^2 * 3 , d_() = 2 , 12 - 2 = 10 . 5. 10 = 2 * 5 , d_() = 5 , 10 + 5 = 15 . Можно, за 5 ходов. б) Покажем, что число 13 недостижимо никаким ходом из любого натурального n . Пусть n 13 . Возможны два варианта. 1. n + d_()(n) = 13 . Если n простое, d_()(n) = 1 , тогда n + 1 = 13 , n = 12 — не простое, противоречие. Если n составное, d_()(n) = n/p , где p = d_()(n) 2 , поэтому n + n/p = 13 . Перебор: - p = 2 : (3n)/(2) = 13 => n = (26)/(3) , не целое; - p = 3 : (4n)/(3) = 13 => n = (39)/(4) , не целое; - p = 5 : (6n)/(5) = 13 => n = (65)/(6) , не целое. Прямой перебор n 12 : n = 9 даёт 12, n = 10 15 , n = 11 12 , n = 12 18 . Ни одно значение не даёт 13. 2. n - d_()(n) = 13 , то есть n = 13 + p , где p = d_()(n) . - Если p = 2 (т.е. n чётное), то n = 15 — нечётное, противоречие. - Если p 3 (т.е. n нечётное), то 13 + p — чётное (нечёт + нечёт), противоречие с нечётностью n . Таким образом, число 13 нельзя получить ни одним ходом. В частности, из 10 в 13 попасть нельзя. в) Рассмотрим путь из 2 в 60. 2 +1 3 +1 4 +2 6 +3 9 +3 12 -2 10 +5 15 +5 20 +10 30 +15 45 +15 60. Это 11 ходов. Каждый ход выполнен по правилам: - Простые 2, 3: d_() = 1 . - 4 6, 6 9, 9 12, 10 15, 15 20, 20 30, 30 45, 45 60 — прибавление наибольшего делителя. - 12 10 — вычитание d_() = 2 . Для проверки минимальности используем поиск в ширину (BFS): | Уровень | Достижимое множество | |---|---| | 0 | 2 | | 1 | 3 | | 2 | 4 | | 3 | 6 | | 4 | 9 | | 5 | 12 | | 6 | 10; 18 | | 7 | 8; 15; 16; 27 | | 8 | 14; 20; 24; 36 | | 9 | 21; 22; 30; 34; 54 | | 10 | 28; 32; 33; 45; 51; 52; 81 | | 11 | Содержит 60 | Анализ показывает, что число 60 впервые появляется на 11-м уровне. Ответ: а) Да б) Нет в) 11

А) да; Б) нет; В) 11