Задача 77915

Темы:    [ Принцип Дирихле (прочее) ] [ Ограниченность, монотонность ] [ Правило произведения ] [ Последовательности (прочее) ]

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

Условие

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

Решение

Пусть числа выписаны в порядке  a₁, ..., a₁₀₀;   x_k и y_k – соответственно наибольшие длины возрастающей и убывающей последовательностей, начинающихся с a_k. Предположим, что  x_k ≤ 10  и  y_k ≤ 10  для всех k. Тогда количество всех различных пар  (x_k, y_k)  не превосходит 100. Поэтому  x_k = x_l  и  y_k = y_l  для некоторых номеров  k < l.  Но этого не может быть: если  a_k < a_l,  то  x_k > x_l,  а если  a_k > a_l,  то  y_k > y_l.

Замечания

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

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

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

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