На доске написаны числа 7 и 8. За один ход разрешено заменить написанную на доске пару чисел a и b парой 2a – 1 и a + b (например, из пары 7 и 8 за один ход можно получить либо числа 13 и 15, либо числа 15 и 15).
а) Может ли случиться так, что после нескольких ходов одно из написанных на доске чисел будет равно 99?
б) Может ли случиться так, что после 22 ходов одно из написанных на доске чисел будет равно 8 787 878?
в) После 1001 хода на доске получили пару чисел, не равных друг другу. Какое наименьшее значение может иметь разность между большим и меньшим из этих чисел.
а) На первом шаге можно получить пары (13, 15) или (15, 15). На втором шаге — пары (25, 28), (28, 29), (29, 30). На третьем — пары (49, 53), (53 ,55), (55, 57), (57, 57), (57, 59), (59, 59). Все пары, кроме первой, дадут на четвертом и последующих шагах два числа, больших 99. Первая может дать (97, 102), но на следующем ходе числа станут больше 99. Значит, получить 99 нельзя.
б) Нет. Заметим, что если то
а если a = b, то
Значит, меньшее из двух чисел растет как минимум так: удваивается, и из результата вычитается 1. Поэтому минимальное число после 22 хода может быть не меньше чем
поэтому числа после 22 ходов станут больше 8 787 878.
в) Заметим, что выражения
отличаются от ровно на 1, причем в любую сторону, в которую нам захочется. То есть с каждой операцией разность между числами изменяется на 1. За 1001 действие она станет четной, но не нулем, значит, как минимум 2. Этого добиться можно, увеличив ее на 1 501 раз, а потом уменьшив на 1 500 раз.
Ответ: а) нет; б) нет в) 2.

