Задание №20 — Свойства чисел

Решение:

а) Проследим за преобразованием пары $(100; 1)$ по шагам:

1. После первого хода имеем: $(100 + 1; 100 - 1) = (101; 99)$;

2. После второго хода: $(101 + 99; 101 - 99) = (200; 2)$;

3. После третьего хода: $(200 + 2; 200 - 2) = (202; 198)$;

4. После четвёртого хода: $(202 + 198; 202 - 198) = (400; 4)$.

Таким образом, получить искомую пару возможно.

б) Проанализируем алгоритм: если из пары $(a; b)$ за один шаг выходит $(a + b; a - b)$, то за следующий шаг мы придем к паре $((a + b) + (a - b); (a + b) - (a - b)) = (2a; 2b)$. Это означает, что через каждое четное количество ходов элементы исходной пары просто увеличиваются в $2^k$ раз. Все достижимые пары из $(100; 1)$ имеют вид $(2^k \cdot 100; 2^k \cdot 1)$ или $(2^k \cdot 101; 2^k \cdot 99)$, где $k \in \mathbb{Z}, k \ge 0$.

Рассмотрим число $806$. Оно не представимо ни в виде $100 \cdot 2^k$, ни в виде $101 \cdot 2^k$ (так как $806/101 \approx 7,98$, а $806/100 = 8,06$). Следовательно, пара $(806; 788)$ не может быть получена из начальной пары $(100; 1)$.

в) Чтобы найти «предыдущую» пару для $(c; d)$, нужно решить систему уравнений относительно $a$ и $b$. Получаем: $a = \frac{c + d}{2}$ и $b = \frac{c - d}{2}$. Такой переход возможен в целых числах только тогда, когда $c$ и $d$ обладают одинаковой чётностью (оба чётные или оба нечётные).

Восстановим цепочку в обратном порядке для пары $(806; 788)$:

1. Перед ней была пара $(\frac{806 + 788}{2}; \frac{806 - 788}{2}) = (797; 9)$;

2. Перед парой $(797; 9)$ была пара $(\frac{797 + 9}{2}; \frac{797 - 9}{2}) = (403; 394)$.

Для пары $(403; 394)$ дальнейший обратный ход невозможен, так как одно число нечётное, а другое чётное. Значит, минимальное значение $a$, при котором процесс мог начаться и привести к $(806; 788)$, составляет $403$.

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

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