Пусть n > 2025 — натуральное число. На доске написаны натуральные числа от 2025 до n. За одну операцию робот берёт два наибольших числа на доске и заменяет их на их разность, тем самым уменьшая количество чисел на доске. Через некоторое время на доске останется только одно число. Сколько существует натуральных n < 7000, для которых это число будет равно 0?
Шаг 1. Преобразование операции
При данной операции каждый раз выбираются два наибольших числа a и b (предположим, a ≥ b) и на их месте записывается разность a – b. Заметим, что если взять два числа, то их наибольший общий делитель (НОД) не меняется, если заменять пару на их разность. Однако в данной задаче выбор происходит не произвольный, а всегда для двух максимальных чисел. При этом можно заметить, что операция обладает другим инвариантом – она сохраняет четность суммы чисел, так как сумма уменьшается на 2b (a+b заменяются на a–b, разность суммы: (a+b) – (a–b) = 2b, то есть вычит...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
