ID: 00008994
Из пары натуральных чисел $( a ; b )$, где $a > b$, за один ход получают пару $( a + b ; a - b )$.
а) Можно ли за несколько таких ходов получить из пары $( 100 ; 1 )$ пару, большее число в которой равно $400$?
б) Можно ли за несколько таких ходов получить из пары $( 100 ; 1 )$ пару $( 806 ; 788 )$?
в) Какое наименьшее $a$ может быть в паре $( a ; b )$, из которой за несколько ходов можно получить пару $( 806 ; 788 )$?
Источник: ФИПИ
Что происходит: из пары $(a;b)$ (где $a\gt b$) за один ход делают пару $(a+b;\,a-b)$ — сумму и разность.
Пункт а). Можно ли из $(100;1)$ получить пару, где большее число равно $400$? Просто походим: $(100;1)\to(101;99)\to(200;2)\to(202;198)\to(400;4)$. В последней паре большее число $400$. Значит — да.
Пункт б). Можно ли получить $(806;788)$? Посмотрим, что даёт ход дважды: $(a;b)\to(a+b;a-b)\to\big((a+b)+(a-b);(a+b)-(a-b)\big)=(2a;2b)$. То есть два хода просто удваивают обе координаты! Поэтому из $(100;1)$ получаются только пары $\big(2^{k}\cdot 100;\,2^{k}\big)$ (после чётного числа ходов) и $\big(2^{k}\cdot 101;\,2^{k}\cdot 99\big)$ (после нечётного).
Большее число $806$ должно было бы равняться $2^{k}\cdot 100$, или $2^{k}\cdot 101$, или $2^{k}\cdot 99$ — но ни при каком целом $k\geqslant 0$ это не так ($806=2\cdot 403$, а $403$ не равно $50,\ 101,\ 99,\dots$). Значит — нет.
Пункт в). Здесь удобно идти назад. Если пара $(c;d)$ получена ходом из $(a;b)$, то $c=a+b$, $d=a-b$, откуда $a=\dfrac{c+d}{2}$, $b=\dfrac{c-d}{2}$. Это возможно, только если $c$ и $d$ одной чётности (иначе деление на $2$ не даст целых).
Отматываем $(806;788)$ назад: $\dfrac{806+788}{2}=797$, $\dfrac{806-788}{2}=9$, получаем $(797;9)$. Ещё шаг: $\dfrac{797+9}{2}=403$, $\dfrac{797-9}{2}=394$, получаем $(403;394)$. Дальше нельзя: $403$ нечётно, $394$ чётно — разной чётности. Значит самое маленькое возможное большее число $a$ в исходной паре — 403.
а) да; б) нет; в) $403$.