Число, содержащее нужные подпоследовательности

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

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

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

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

  1. Сколько цифр каждой записи уже получено
  2. Минимальная длина общей записи

    Сначала: Сколько цифр каждой записи уже получено

  3. Ответ

    Сначала: Минимальная длина общей записи

  4. Сколько цифр каждой записи уже получено

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

  5. Минимальная длина общей записи

    Сначала: Сколько цифр каждой записи уже получено

  6. Ответ: нет

    Сначала: Минимальная длина общей записи

  7. Нижняя граница длины для всех чисел

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

  8. Наименьшая запись минимальной длины

    Сначала: Нижняя граница длины для всех чисел

  9. Ответ

    Сначала: Наименьшая запись минимальной длины

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

а) Приведите пример семизначного числа из которого, вычёркивая цифры, можно получить каждое из чисел: 123, 426, 786.

б) Существует ли девятизначное число из которого, вычёркивая цифры, можно получить каждое из чисел: 123, 238, 435, 567, 791?

в) Найдите наименьшее натуральное число, из которого можно получить все числа от 1 до 40 включительно, вычёркивая из него цифры.

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

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

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

Шаг 1. Состояние хранит, сколько начальных цифр каждой требуемой записи уже встретилось. При добавлении цифры dd продвигаемся на один знак во всех записях, у которых следующий нужный знак равен dd. Это жадное сопоставление эквивалентно существованию подпоследовательности; первая цифра исходного числа не может быть нулём.
Шаг 2. Всего состояний не больше произведения увеличенных длин требуемых записей. Начинаем с нулевого состояния и последовательно строим все достижимые состояния после 1, 2, …1,\,2,\,\ldots добавленных цифр. Первое полное состояние даёт наименьшую длину. Приведённая запись реализует найденные переходы. Если нужна большая длина, можно приписать слева ненулевые цифры.
T=((1;2;3);(4;2;6);(7;8;6))\mathcal T=\left(\left(1;2;3\right);\left(4;2;6\right);\left(7;8;6\right)\right)
Шаг 3. Записываем найденный результат.
14237861423786
Шаг 1. Состояние хранит, сколько начальных цифр каждой требуемой записи уже встретилось. При добавлении цифры dd продвигаемся на один знак во всех записях, у которых следующий нужный знак равен dd. Это жадное сопоставление эквивалентно существованию подпоследовательности; первая цифра исходного числа не может быть нулём.
Шаг 2. Всего состояний не больше произведения увеличенных длин требуемых записей. Начинаем с нулевого состояния и последовательно строим все достижимые состояния после 1, 2, …1,\,2,\,\ldots добавленных цифр. Первое полное состояние даёт наименьшую длину. Приведённая запись реализует найденные переходы. Если нужна большая длина, можно приписать слева ненулевые цифры.
T=((10;9);(1;2;4;3;5;6;7;8;9;1))\mathcal T=\left(\left(10;9\right);\left(1;2;4;3;5;6;7;8;9;1\right)\right)
Шаг 3. Нет. Полная конечная область либо доказанная нижняя граница исключает возможность.
Шаг 1. Для получения всех чисел от 1 до MM, где 10≤M≤9910\leq M\leq 99, нужны все цифры от 1 до 9 и цифра 0. Если число 11a≤M11a\leq M, цифра aa нужна по крайней мере дважды, чтобы получить aaaa. Эти требования задают нижнюю границу количества цифр и минимальный набор их кратностей.
T=(1;2;2;2;1;1;1;1;1;1)\mathcal T=\left(1;2;2;2;1;1;1;1;1;1\right)
Шаг 2. Для каждой требуемой двузначной записи abab отмечаем, появилась ли bb после хотя бы одной aa. Проверяем все записи с найденными минимальными кратностями цифр: состояние состоит из оставшихся кратностей, уже встреченных цифр и ещё не полученных пар. Если пара abab не получена, в остатке должна быть bb, а при отсутствии aa в префиксе - ещё и aa; для aaaa нужны две оставшиеся aa. Эти необходимые отсечения ничего не теряют. Полный конечный разбор в порядке цифр от 0 до 9 находит лексикографически наименьшую допустимую запись, с запретом начального нуля. Она достигает нижней границы длины, значит, является наименьшим натуральным числом.
M=40M=40
Шаг 3. Записываем найденный результат.
12312340567891231234056789

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

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