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

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

Условие

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

Подсказка

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

Решение

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

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

web-сайт
задача

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

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