Доска: умножение, прибавление и удаление цифры

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

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

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

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

  1. Неизменный остаток по модулю три
  2. Допустимая цепочка операций

    Сначала: Неизменный остаток по модулю три

  3. Ответ: да

    Сначала: Допустимая цепочка операций

  4. Неизменный остаток по модулю три

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

  5. Ответ: нет

    Сначала: Неизменный остаток по модулю три

  6. Неизменный остаток по модулю три

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

  7. Допустимая цепочка операций

    Сначала: Неизменный остаток по модулю три

  8. Получение всего класса остатков

    Сначала: Допустимая цепочка операций

  9. Ответ

    Сначала: Получение всего класса остатков

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

На доске записано некоторое натуральное число NN. Учитель по очереди вызывает учеников, которые выполняют с любым из уже записанных на доске чисел одно из следующих действий:

– умножить число на 4;

– прибавить к числу 12;

– если число не равно 6, то вычеркнуть из числа цифру 6.

Затем каждый из учеников записывает новое число на доску.

а) Можно ли за несколько действий получить из числа 34 число 1?

б) Можно ли за несколько действий получить из числа 35 число 60?

в) Какое наибольшее количество чисел, меньших 2000, может быть записано на доске, если N=1N=1.

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Умножение на 4 и прибавление 12 сохраняют остаток по модулю 3. Удаление цифры 6 или 9 также сохраняет его, поскольку сумма цифр меняется на кратное 3. Поэтому число с другим остатком получить невозможно.
N=34N=34
T=1T=1
Шаг 2. Выписываем цепочку. Каждый переход - умножение на 4, прибавление 12 или удаление одной указанной цифры из десятичной записи. Все результаты натуральны. Это непосредственная конструкция достижимости.
T=(34;46;4;16;1)\mathcal T=\left(34;46;4;16;1\right)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Умножение на 4 и прибавление 12 сохраняют остаток по модулю 3. Удаление цифры 6 или 9 также сохраняет его, поскольку сумма цифр меняется на кратное 3. Поэтому число с другим остатком получить невозможно.
N=35N=35
T=60T=60
Шаг 2. Нет. Необходимое ограничение или полный конечный разбор исключает такую возможность.
Шаг 1. Умножение на 4 и прибавление 12 сохраняют остаток по модулю 3. Удаление цифры 6 или 9 также сохраняет его, поскольку сумма цифр меняется на кратное 3. Поэтому число с другим остатком получить невозможно.
Шаг 2. Выписываем цепочку. Каждый переход - умножение на 4, прибавление 12 или удаление одной указанной цифры из десятичной записи. Все результаты натуральны. Это непосредственная конструкция достижимости.
T=((1);(1;4);(1;4;16;64;76;7);(1;4;16;28;40;160;10))\mathcal T=\left(\left(1\right);\left(1;4\right);\left(1;4;16;64;76;7\right);\left(1;4;16;28;40;160;10\right)\right)
Шаг 3. В данном пункте исходное число равно 1 или 3. Строим четыре наименьших положительных числа с тем же остатком по модулю 3: rr, r+3r+3, r+6r+6, r+9r+9. Затем прибавлением 12 из этих четырёх чисел получаем все положительные числа этого класса. Другие классы запрещены инвариантом. Поэтому количество чисел ниже HH равно ⌊H−1−r3⌋+1\left\lfloor \frac{H-1-r}{3}\right\rfloor +1.
R=1R=1
H=2000H=2000
Шаг 4. Записываем найденное значение.
667667

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

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