Два числа и управляемая разность

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Конструкция заданного значения
  2. Конструкция и точный результат

    Сначала: Конструкция заданного значения

  3. Рост меньшего числа

    Сначала: Конструкция и точный результат

  4. Ответ: нет

    Сначала: Рост меньшего числа

  5. Как изменяется разность

    Сначала: Ответ: нет

  6. Ответ

    Сначала: Как изменяется разность

Разобранный пример

На доске написаны числа 2 и 3. За один ход два числа aa и bb, записанных на доске заменяется на два числа: a+ba + b и 2a−12a - 1 или a+ba + b и 2b−12b - 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))\mathcal T=\left(\left(2;3\right);\left(5;3\right);\left(8;9\right);\left(17;15\right)\right)
Шаг 1. Если меньшее число равно uu, оба новых числа не меньше 2u−12u-1. По индукции после tt ходов меньшее число не меньше 2t+12^{t}+1, так как исходное меньшее число равно двум. Это исключает любое заданное число, меньшее этой границы.
n=50n=50
Шаг 2. Нет. Доказанная граница исключает возможность.
Шаг 1. Пусть разность большего и меньшего равна dd. Выбор удвоенного меньшего даёт разность d+1d+1, а удвоенного большего - ∣d−1∣|d-1|. Начальная разность равна одному. Поэтому после нечётного числа ходов разность чётна; если равенства запрещены, она не меньше двух. Чтобы достичь двух, чередуем выбор меньшего при d=1d=1 и большего при d=2d=2. Разность чередуется между 1 и 2, равенства никогда нет.
n=2015n=2015
Шаг 2. Записываем полученный ответ.
22

Открыть задачу целиком

Попробовать самостоятельно