Задача 34844

Темы:    [ Отношение порядка ] [ Геометрическая прогрессия ]

Сложность: 5 Классы: 9,10

Условие

Натуральные числа от 1 до n расставляются в ряд в произвольном порядке. Расстановка называется плохой, если в ней можно отметить 10 чисел (не обязательно стоящих подряд), идущих в порядке убывания. Остальные расстановки называются хорошими. Докажите, что количество хороших расстановок не превосходит 81ⁿ.

Подсказка

Если расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке возрастания.

Решение

1) Докажем, что если расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке возрастания. Действительно, будем красить числа слева направо, используя каждый раз такой цвет с наименьшим номером, что последнее покрашенное в этот цвет число меньше текущего. Предположим, что девяти цветов не хватило. Мы не можем покрасить очередное число в девятый цвет, так как в девятый цвет уже было покрашено большее число. Оно не было покрашено в восьмой цвет, поскольку до него встретилось большее число, покрашенное в восьмой цвет. И так далее. Получается 10 чисел, которые идут в порядке убывания. 2) Расстановка чисел от 1 до n вместе с такой раскраской в девять цветов, что последовательность чисел каждого цвета возрастает, полностью определяется цветом каждого числа от 1 до n и цветом каждого места в ряду. Числа от 1 до n можно раскрасить в 9 цветов 9ⁿ способами. И столькими же способами можно раскрасить в 9 цветов n мест, на которые эти числа будут расставлены. Таким образом, число хороших расстановок не превосходит 81ⁿ.

Источники и прецеденты использования

web-сайт

задача