6. За один ход разрешается прибавить одно из записанных чисел к другому, заменив последнее полученной суммой. За какое наименьшее число ходов можно получить на доске пару чисел 93 и 161?

Пусть исходные числа — целые положительные числа. При операции сумма чисел увеличивается, поэтому из пары 93 и 161 можно восстановить предыдущую пару, вычитая меньшее число из большего.

1. 161 − 93 = 68, значит предыдущая пара могла быть 93 и 68.
2. 93 − 68 = 25, получаем 68 и 25.
3. 68 − 25 = 43, получаем 25 и 43.
4. 43 − 25 = 18; затем 25 − 18 = 7; затем 18 − 7 = 11; затем 11 − 7 = 4; затем 7 − 4 = 3; затем 4 − 3 = 1.

Обратная цепочка сложений от пары 1 и 1 даёт числа Фибоначчи: 1, 1 → 1, 2 → 3, 2 → 3, 5 → 8, 5 → 8, 13 → 21, 13 → 21, 34 → 55, 34 → 55, 89 → 144, 89 → 144, 233. Но в цепочке до 93 и 161 имеются 11 переходов от исходной пары 1 и 1; пары 93 и 161 возникают не в этой последовательности. Поэтому нужно учитывать, что исходная доска содержит числа 1 и 1, а разрешённые ходы дают последовательность пар с последующим сложением меньшего числа с большим: 1,1; 1,2; 3,2; 3,5; 8,5; 8,13; 21,13; 21,34; 55,34; 55,89; 144,89. Пара 93 и 161 в этой цепочке недостижима.

Также можно проверить инвариант: любые числа, полученные из 1 и 1 таким способом, взаимно просты. Числа 93 и 161 взаимно просты, но это необходимое, а не достаточное условие. Обратный алгоритм для них приводит к паре 1 и 1, однако он требует вычитаний с повторением: 161,93 → 68,93 → 25,68 → 25,43 → 18,25 → 7,18 → 7,11 → 4,7 → 3,4 → 1,3 → 1,2 → 1,1. Это 11 обратных ходов, следовательно, 11 прямых ходов достаточно и необходимо.

Ответ: 11 ходов.