Сложнейшая задача для гениев Луиза написала в тетради k-значное натуральное число без нулей в записи. Серёжа пытался вычеркнуть несколько цифр так, чтобы оставшиеся цифры образовывали трёхзначное число, в котором каждая следующая цифра не меньше предыдущей (слева направо). Серёжа перепробовал все способы, но так и не добился желаемого. При каком наибольшем k это возможно?

Предыдущий
вопрос Следующий
вопрос

Давайте рассмотрим задачу более детально.

Мы ищем максимальное значение ( k ), для которого возможно вычеркнуть цифры из ( k )-значного натурального числа, чтобы из оставшихся цифр получилось трехзначное число, каждая следующая цифра которого не меньше предыдущей. Это значит, что оставшиеся цифры должны быть неуклонно возрастающими или равными, т.е., выбранные цифры должны образовывать возрастающую последовательность, где каждая из оставшихся цифр не меньше предыдущей.

Мы можем использовать следующий подход:

Определяем количество доступных цифр. В записи натурального числа без нулей у нас есть цифры от 1 до 9. Это составляет 9 различных цифр.

Требование к трем цифрам. Нужно выбрать три цифры, чтобы они удовлетворяли условию неуклонного возрастания. Разрешено использовать одни и те же цифры. Это дает возможность выбирать такие комбинации как, например, "111", "122", "223" и так далее.

Максимальное количество цифр. Если мы имеем ( k ) цифр, мы можем создать число ( \binom{n + r - 1}{r} ) возможных комбинаций, где ( n ) — число уникальных цифр (в нашем случае 9) и ( r ) — количество цифр для выбора (в нашем случае 3).

Сравнение с ( k ). Подумайте, может ли число ( k ) превысить 12. Это связано с тем, что для формирования трех цифр при условии, что не должно быть "пустых" мест, мы не можем использовать все 9 уникальных цифр в различных порядках, если число превышает 12.

Таким образом, при ( k = 12 ) мы можем составить три 3-значных числа с возрастанием, но начиная с ( k = 13 ), поскольку комбинированная структура цифр может привести к тому, что они перестанут удовлетворять одно из условий.

Итак, максимальное значение ( k ), при котором возможно снять три цифры - это:

[
\boxed{12}
]