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

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

Условие

Числа 1, 2, 3, ..., 101 выписаны в ряд в каком-то порядке.
Докажите, что из них можно вычеркнуть 90 так, что оставшиеся 11 будут расположены по их величине (либо возрастая, либо убывая).


Решение

Пусть числа выписаны в порядке  a1, ..., a100;   xk и yk – соответственно наибольшие длины возрастающей и убывающей последовательностей, начинающихся с ak. Предположим, что  xk ≤ 10  и  yk ≤ 10  для всех k. Тогда количество всех различных пар  (xk, yk)  не превосходит 100. Поэтому  xk = xl  и  yk = yl  для некоторых номеров  k < l.  Но этого не может быть: если  ak < al,  то  xk > xl,  а если  ak > al,  то  yk > yl.

Замечания

1. Эта задача не была решена никем из участников олимпиады.

2. Аналогично можно доказать, что любая последовательность из  mn + 1  попарно различных чисел содержит либо возрастающую последовательность из  m + 1  числа, либо убывающую последовательность из  n + 1  числа.

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

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 2
Название Комбинаторика
Тема Комбинаторика
параграф
Номер 2
Название Принцип Дирихле
Тема Принцип Дирихле (прочее)
задача
Номер 02.026
олимпиада
Название Московская математическая олимпиада
год
Номер 13
Год 1950
вариант
Класс 9,10
Тур 2
задача
Номер 2

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

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