Задание №20 — Числовые наборы на карточках/досках

Решение:
а) Проследим за изменением чисел в паре. Начиная с $(100; 1)$, после первого шага мы придем к паре $(100 + 1; 100 - 1) = (101; 99)$. Выполнив второй шаг, получим $(101 + 99; 101 - 99) = (200; 2)$. На третьем шаге образуется пара $(200 + 2; 200 - 2) = (202; 198)$. Наконец, после четвертого шага мы имеем $(202 + 198; 202 - 198) = (400; 4)$. Таким образом, это возможно.

б) Проанализируем алгоритм: если на некотором этапе у нас есть пара $(a; b)$, то через один ход она превращается в $(a + b; a - b)$. Еще через один ход мы получим $((a + b) + (a - b); (a + b) - (a - b))$, что упрощается до $(2a; 2b)$. Это означает, что за каждые два хода значения в паре просто удваиваются. Следовательно, из исходной пары $(100; 1)$ через четное число ходов $2n$ можно получить только вид $(2^n \cdot 100; 2^n \cdot 1)$, а через нечетное число ходов $2n+1$ — вид $(2^n \cdot 101; 2^n \cdot 99)$, где $n$ — целое неотрицательное число. Рассмотрим число 806. Оно не представимо ни в виде $100 \cdot 2^n$, ни в виде $101 \cdot 2^n$ (так как $806/100 = 8,06$, а $806/101 = 7,98...$). Значит, получить пару $(806; 788)$ из начальной пары $(100; 1)$ нельзя.

в) Чтобы определить предыдущую пару для $(c; d)$, нужно решить систему уравнений: $x + y = c$ и $x - y = d$. Отсюда $x = \frac{c + d}{2}$ и $y = \frac{c - d}{2}$. Это возможно в целых числах только тогда, когда $c$ и $d$ имеют одинаковую четность. Для искомой пары $(806; 788)$ оба числа четные, значит, она получена из $( \frac{806 + 788}{2}; \frac{806 - 788}{2} ) = (797; 9)$. Для пары $(797; 9)$ оба числа нечетные, следовательно, она могла быть получена из $( \frac{797 + 9}{2}; \frac{797 - 9}{2} ) = (403; 394)$. В паре $(403; 394)$ одно число нечетное, а другое четное. Такую комбинацию невозможно получить ни из какой другой целочисленной пары. Значит, цепочка обрывается. Минимальное значение $a$ в исходной паре, из которой можно прийти к $(806; 788)$, составляет 403.

Ответ: а) да; б) нет; в) 403.

Источник: ФИПИ