ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 107862
Темы:    [ Задачи с ограничениями ]
[ Вспомогательная раскраска (прочее) ]
[ Обратный ход ]
[ Перестановки и подстановки (прочее) ]
[ Правило произведения ]
Сложность: 5+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Натуральные числа от 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 хороших расстановок "гораздо меньше", чем плохих.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 61
Год 1998
вариант
Класс 11
задача
Номер 6
олимпиада
Название Московская математическая олимпиада
год
Номер 61
Год 1998
вариант
Класс 10
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .