|
|
 |
Условие
Назовём натуральное число хорошим, если все его цифры ненулевые. Хорошее число назовём особым, если в нём хотя бы k разрядов и цифры идут в порядке строгого возрастания (слева направо). Пусть имеется некое хорошее число. За ход разрешается приписать с любого края или вписать между любыми его двумя цифрами особое число или же, наоборот, стереть в его записи особое число. При каком наибольшем k можно из каждого хорошего числа получить любое другое хорошее число с помощью таких ходов?
Решение
Очевидно, в особом числе не более девяти цифр. Если k = 9, то при каждой операции число цифр меняется ровно на 9, то есть остаток от деления на 9 числа его цифр не меняется, и из однозначного числа нельзя сделать двузначное.
Пусть k = 8. Поскольку все операции обратимы, то достаточно доказать, что можно вставить любую цифру. Докажем индукцией по n, что можно вставить цифру n.
База. Чтобы вставить 1, вставим сначала 123456789, а затем вычеркнем 23456789.
Шаг индукции. Пусть мы умеем вставлять (и вычёркивать) цифры от 1 до n – 1 < 9. Чтобы вставить n, вставим сначала 123456789, сотрём 12...(n–1) по одной цифре, затем по одной цифре вставим 12...(n–1) справа от n и наконец вычеркнем число 12...(n–1)(n+1)...9 (при n = 9 последние два действия не нужны, а при n = 8 вычёркивается число 12...79).
Ответ
При k = 8.
