Математика (проф. ур.) ((C7). Числа и их свойства)
На доске написаны числа 2 и 3. За один ход два числа a и b, записанных на доске заменяется на два числа: a + b и 2a − 1 или a + b и 2b − 1.
Пример: числа 2 и 3 заменяются на 3 и 5, на 5 и 5, соответственно.
а) Приведите пример последовательности ходов, после которых одно из чисел, написанных на доске, окажется числом 19.
б) Может ли после 50 ходов одно из двух чисел, написанных на доске, оказаться числом 100.
в) Сделали 2015 ходов, причём на доске никогда не было написано одновременно двух равных чисел. Какое наименьшее значение может принимать разность большего и меньшего из полученных чисел?
Ответ
а)
б) Заметим, что сумма чисел на доске увеличивается на 
или 
(поскольку число 1 на доске никогда не появится). Значит, после 49 ходов сумма станет минимум 
Поэтому после пятидесятого хода 
В то же время 
и 
потому что левая часть нечетна, а правая четна.
в) После хода разность чисел становится равна 
или 
Поэтому модуль разности чисел меняется на 1. Изначально он был равен 1, поэтому после 2015 ходов он будет четным. Значит, равен как минимум двум.
Приведем пример. Первым ходом получим пару (5;3), а затем каждые два хода будем получать ситуацию, в которой числа отличаются на 2 (и никогда в процессе не будут равны):
Повторяя эти действия, получим в итоге два числа с разностью 2.