На доске написаны числа 2 и 3. За один ход два числа a и b, записанных на доске заменяется на два числа: a+b и 2a−1 или a+b и 2b−1. Пример: числа 2 и 3 заменяются на 3 и 5, на 5 и 5, соответственно.
а) Приведите пример последовательности ходов, после которых одно из чисел, написанных на доске, окажется числом 15.
б) Может ли после 50 ходов одно из двух чисел, написанных на доске, окажется числом 100.
в) Сделали 2015 ходов, причём на доске никогда не было написано одновременно двух равных чисел. Какое наименьшее значение может принимать разность большего и меньшего из полученных чисел?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Перебираем два разрешённых перехода из каждой пары, пока одно из чисел не станет заданным. По границе меньшего числа достаточно глубины floor(log2(цель−1)). Приводим последовательность пар и проверяем каждый переход исходными формулами.
Шаг 2. Приводим полученный набор, параметры или распределение.
T=((2;3);(5;3);(8;9);(17;15))
Шаг 1. Если меньшее число равно u, оба новых числа не меньше 2u−1. По индукции после t ходов меньшее число не меньше 2t+1, так как исходное меньшее число равно двум. Это исключает любое заданное число, меньшее этой границы.
n=50
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. Пусть разность большего и меньшего равна d. Выбор удвоенного меньшего даёт разность d+1, а удвоенного большего - ∣d−1∣. Начальная разность равна одному. Поэтому после нечётного числа ходов разность чётна; если равенства запрещены, она не меньше двух. Чтобы достичь двух, чередуем выбор меньшего при d=1 и большего при d=2. Разность чередуется между 1 и 2, равенства никогда нет.