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.