Математика · объяснение и практика

Теорема Эрдёша — Секереша: длинная монотонная подпоследовательность

Доказываем конечную гарантию rs+1 через пары длин, заканчивающихся в каждой позиции, строим резкий пример на rs членах и сохраняем исходный порядок индексов.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Если r и s — положительные целые, среди rs+1 различных действительных чисел в заданном порядке найдётся строго возрастающая подпоследовательность длины r+1 или строго убывающая длины s+1. Члены можно пропускать, но нельзя переставлять. Граница rs+1 в общем случае не уменьшается.

Подпоследовательность сохраняет время появления чисел

Выбираем строго возрастающие индексы i₁,i₂,… и читаем соответствующие члены в прежнем порядке. Их не требуется брать подряд, поэтому монотонная подпоследовательность отличается от непрерывного отрезка списка. Сортировка всех чисел создаёт новую последовательность и не является допустимым способом предъявить найденную подпоследовательность.

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

Каждая позиция получает пару неповторяющихся меток

Обозначим Iⱼ наибольшую длину возрастающей подпоследовательности, заканчивающейся в позиции j, а Dⱼ — такую же длину убывающей. Обе длины не меньше единицы: сам член даёт одноэлементный выбор. Если позиция i предшествует j и aᵢ меньше aⱼ, к лучшему возрастающему выбору, заканчивающемуся на i, можно добавить aⱼ. Поэтому Iⱼ≥Iᵢ+1.

Если при том же порядке позиций значение aᵢ больше aⱼ, получаем Dⱼ≥Dᵢ+1. Следовательно, пары (Iⱼ,Dⱼ) у любых двух позиций различны. Предположим теперь, что нужных длин нет. Тогда Iⱼ≤r и Dⱼ≤s, так что возможных положительных целых пар не больше rs. Но позиции дают rs+1 разных пар. Это противоречие доказывает хотя бы одну из двух требуемых длин. Мы не обязаны заранее угадывать, какая из альтернатив осуществится.

Пример

Объясните гарантию для семи различных чисел при r=3,s=2 и покажите, почему шести в общем случае недостаточно.

Семь=3·2+1, поэтому найдётся возрастающий выбор из четырёх членов либо убывающий из трёх. Шестичленный пример 2,1,4,3,6,5 состоит из трёх убывающих пар. Возрастающий выбор берёт не более одного из каждой пары и имеет длину не больше трёх. Убывающий остаётся в одной паре и имеет длину не больше двух. Поэтому уменьшить общий порог до шести нельзя.

Блочный пример показывает точность порога

Запишем r последовательных блоков по s чисел: сначала s,s−1,…,1, затем 2s,2s−1,…,s+1 и так далее. Каждый блок убывает, но все числа следующего блока больше всех чисел предыдущего. Возрастающий выбор берёт не больше одного члена из каждого блока, значит его длина не больше r. Убывающий не может переходить к более позднему блоку, значит его длина не больше s.

Так на rs членах обе требуемые более длинные альтернативы отсутствуют. Это доказывает резкость общего количества, а не утверждает, что каждый короткий список плох. Для конкретной последовательности можно найти значительно более длинный выбор. Пары меток также подсказывают алгоритм восстановления: вместе с длиной хранить предыдущую позицию, которая её достигла. Но вычислительный способ не заменяет аргумент, почему разных пар оказалось достаточно для теоремы.

От чтения к действию

А теперь — вы

В списке 13 различных чисел заявлено, что все метки I не больше 4, а все метки D не больше 3. Какое противоречие использует доказательство?

Частые вопросы

Найденные члены должны стоять рядом?

Нет. Требуются возрастающие индексы, а промежуточные позиции можно пропускать. Переставлять выбранные числа нельзя.

Теорема гарантирует сразу обе альтернативы?

Нет. Гарантируется хотя бы одна. Полностью возрастающий список не обязан содержать длинную строго убывающую подпоследовательность.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться