На доске написаны числа 3 и 5. За один ход разрешено заменить написанную на доске пару чисел a и b парой и
(например, из пары чисел 3 и 5 за один ход можно получить либо числа 5 и 9, либо числа 9 и 9).
а) Может ли получиться так, что после нескольких ходов на доске будут написаны числа 73 и 75?
б) Может ли получиться так, что после нескольких ходов одно из написанных на доске чисел будет равно 35?
в) После 2017 ходов на доске получили пару чисел, не равных друг другу. Какое наименьшее значение может иметь разность между большим и меньшим из этих чисел?
а) Да, например:
б) Нет. Очевидно и
поэтому как только оба числа в паре станут больше 35, дальше можно не перебирать.
На первом шаге можно получить или
На втором:
или
На третьем:
Все пары, кроме первой, дадут числа, большие 35. Первая может дать и после еще одного хода числа превысят 35.
в) Если числа дают остатки 1 и 3 от деления на 4, то их сумма кратна 4, поэтому
и
дают остаток 1 при делении на 4.
Если же оба числа дают остаток 1 при делении на 4, то или
дает остаток 1, а
дает остаток 3 при делении на 4.
Итак, пары остатков чередуются — после нечетного хода это после четного —
Поскольку числа не равны и дают одинаковый остаток от деления на 4, разность между ними не меньше 4. Этого достичь можно. Первым ходом получим пару
А затем с парой
будет проделывать пары ходов
после которых разность чисел в паре будет сохраняться.
Ответ: а) да; б) нет; в) 4.

