13
правок
Изменения
Нет описания правки
Заметим что <tex>1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k</tex>, поэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>l k \geqslant n</tex>, ч. т. д.
}}
== Следствие из теоремы ==
{{Утверждение
|statement=
Пусть <tex>n</tex> - длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>
}}
