Принцип Дирихле

Каждому из чисел сопоставим пару из двух чисел где — длина наибольшей неубывающей последовательности, начинающейся с этого числа, а — длина наибольшей невозрастающей последовательности, начинающейся с этого числа. Заметим, что если хотя бы одно сопоставленное число больше то требуемая подпоследовательность найдена.

Если же все сопоставленные числа меньше то всего может быть сопоставлено различных пар чисел. Тогда по принципу Дирихле двум из наших чисел сопоставлены одинаковые пары чисел. Обозначим эти два числа через и и пусть имеет меньший номер в последовательности. Если то длина наибольшей неубывающей последовательности, начинающейся с будет заведомо больше длины такой же последовательности для Аналогично получаем противоречие, если