Из пары натуральных чисел (a;b), где a>b, за один ход получают пару (a+b;a-b). Какое наименьшее a может быть в паре (a;b), из которой за несколько ходов можно получить пару (408;370).
Для решения задачи рассмотрим заданные пары чисел в процессе их преобразования. Каждое преобразование от пары \((a; b)\) к паре \((a+b; a-b)\) приводит к тому, что первое число увеличивается, а второе может изменяться как в сторону увеличения, так и уменьшения, но всегда остается натуральным числом.
Нам нужно определить такие \(a\) и \(b\), которые позволят через некоторый набор преобразований получить пару \((408; 370)\). Поскольку преобразование на каждой итерации сохраняет порядок \(a > b\), давайте проанализируем, как мы можем "обратиться" из конечной пары назад к начальной.
Обратите внимание на разность \(d = a - b\). В нашем случае \(d = 408 - 370 = 38\).
В результате операции \((x, y) \rightarrow (x+y, x-y)\), новая пара образуется из \(408\) и \(370\), где \(x = 408\) и \(y = 370\) следовательно, \[ d_1 = 408 + 370 = 778, \] \[ d_2 = 408 - 370 = 38. \]
Мы можем итеративно рассматривать пары, начиная с \((408; 370)\) и применяя обратное преобразование в строку \((x,y)\) для получения предыдущих пар: \[ (x,y) \rightarrow (x-y, y). \]
Здесь мы просто переставляем \(x\) и \(y\) и понижаем их значения, чтобы пройти путь назад, пока не будем удовлетворять условию \(a > b\).
Таким образом, можно вывести последовательность:
- возьмем \( (408, 370) \),
- \( (778, 38) \),
- \((816, 778) \) (здесь первое число стало больше).
Продолжая этот путь, мы будем получать всё больший \(a\), и вы можете пытаться работать назад, уменьшать или увеличивать значения. Пара, представляющая наш интерес, минимизирует \(a\).
Также, любой последовательный шаг не может уменьшить значение \(a\) ниже определённого порога, потому что при каждом преобразовании новое \(a\) будет увеличением. Мы можем заметить, что повторяя преобразования, как показано, мы стремимся к некоторым минимальным числам.
Если мы сопоставим это с данной конечной парой \((408; 370)\) и обратим внимание, что минимальное значение \(a\) становится \( \max(408,370) + k \) (где \(k\) - минимальное количество шагов, необходимых для возврата к паре), мы можем найти, что наименьшее значение \(a\) составит 778 – это минимальная пара, из которой можно получить требуемую.
Таким образом, минимальное значение \(a\) равно 778.
