|
|
 |
Условие
Натуральные числа от 1 до n расставляются в ряд в произвольном порядке. Расстановка называется плохой, если в ней можно отметить 10 чисел (не обязательно стоящих подряд), идущих в порядке убывания. Остальные расстановки называются хорошими. Докажите, что количество хороших расстановок не превосходит 81n.
Решение
Докажем, что если расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке
возрастания. Действительно, будем красить числа слева направо, используя каждый
раз такой цвет с наименьшим номером, что последнее покрашенное в этот цвет число
меньше текущего. Предположим, что девяти цветов не хватило. Мы не можем
покрасить очередное число (обозначим его a10) в девятый цвет, так как в девятый цвет уже было покрашено большее число a9. Число a9 не было покрашено в восьмой цвет, поскольку до него встретилось большее число a8, покрашенное в восьмой цвет. И так далее. Получается 10 чисел, которые идут в порядке убывания. Противоречие.
Расстановка чисел от 1 до n вместе с такой раскраской в девять цветов, что последовательность чисел каждого цвета возрастает, полностью определяется цветом каждого числа от 1 до n и цветом каждого места в ряду. Числа от 1 до n можно раскрасить в 9 цветов 9n способами. И столькими же способами можно раскрасить в 9 цветов n мест, на которые эти числа будут расставлены. (Следует еще следить за тем, чтобы количество чисел каждого цвета совпадало с количеством мест этого цвета, но это только уменьшит число способов.) Таким образом, число хороших расстановок не превосходит 81n.
Замечания
Существует n! расстановок чисел от 1 до n. Как известно,
= 0. Поэтому при больших n хороших расстановок "гораздо меньше", чем плохих.
