На доске записано некоторое натуральное число N. Учитель по очереди вызывает учеников, которые выполняют с любым из уже записанных на доске чисел одно из следующих действий:
– умножить число на 4;
– прибавить к числу 12;
– если число не равно 6, то вычеркнуть из числа цифру 6.
Затем каждый из учеников записывает новое число на доску.
а) Можно ли за несколько действий получить из числа 34 число 1?
б) Можно ли за несколько действий получить из числа 35 число 60?
в) Какое наибольшее количество чисел, меньших 2000, может быть записано на доске, если N=1.
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Умножение на 4 и прибавление 12 сохраняют остаток по модулю 3. Удаление цифры 6 или 9 также сохраняет его, поскольку сумма цифр меняется на кратное 3. Поэтому число с другим остатком получить невозможно.
N=34
T=1
Шаг 2. Выписываем цепочку. Каждый переход - умножение на 4, прибавление 12 или удаление одной указанной цифры из десятичной записи. Все результаты натуральны. Это непосредственная конструкция достижимости.
T=(34;46;4;16;1)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Умножение на 4 и прибавление 12 сохраняют остаток по модулю 3. Удаление цифры 6 или 9 также сохраняет его, поскольку сумма цифр меняется на кратное 3. Поэтому число с другим остатком получить невозможно.
N=35
T=60
Шаг 2. Нет. Необходимое ограничение или полный конечный разбор исключает такую возможность.
Шаг 1. Умножение на 4 и прибавление 12 сохраняют остаток по модулю 3. Удаление цифры 6 или 9 также сохраняет его, поскольку сумма цифр меняется на кратное 3. Поэтому число с другим остатком получить невозможно.
Шаг 2. Выписываем цепочку. Каждый переход - умножение на 4, прибавление 12 или удаление одной указанной цифры из десятичной записи. Все результаты натуральны. Это непосредственная конструкция достижимости.
Шаг 3. В данном пункте исходное число равно 1 или 3. Строим четыре наименьших положительных числа с тем же остатком по модулю 3: r, r+3, r+6, r+9. Затем прибавлением 12 из этих четырёх чисел получаем все положительные числа этого класса. Другие классы запрещены инвариантом. Поэтому количество чисел ниже H равно ⌊3H−1−r⌋+1.