На доске записаны числа 1 и 1. За один ход разрешается прибавить одно из записанных чисел к другому, заменив второе число полученной суммой. За какое наименьшее число ходов можно получить пару чисел 43 и 68?
Пойдём от конца к началу. Последним ходом большее число получено как сумма двух чисел пары, поэтому перед этим ходом оно было равно разности большего и меньшего. Значит, обратный ход определён однозначно: из большего числа вычитаем меньшее. Поэтому и путь, и число ходов единственные.
Обратный путь:
Это
Проверим прямым ходом:
Получилось
Обратный путь однозначен: перед последним ходом большее число было равно разности большего и меньшего. Это то же самое, что алгоритм Евклида, поэтому меньшего числа ходов быть не может.
