Эта запись может быть интересна тем, кого интересуют числа, доказательства, математика.
У теоремы, которую доказали Erdos и Szekeres в 1935-м году, простое условие:
Теорема. Из последовательности чисел длиной n2+1 можно всегда выбрать возрастающую или убывающую под-последовательность длиной n+1.
"Выбрать под-последовательность" здесь означает, что из всей последовательности в n2+1 чисел можно отобрать n+1 идущих в ней по порядку (но необязательно один за другим, можно "с пропусками"), так что сами эти числа будут стоять либо от меньшего к большему, либо от большего к меньшему (возможно, с равенствами посредине).
Например, возьмем самый простой случай n=2, тогда n2+1=5, n+1=3. Т.е. утверждается, что если записать пять чисел подряд: например, 3 10 5 8 6, то, идя слева направо, можно будет отобрать три числа, которые либо все время возрастают, либо все время убывают. И действительно, в данном случае это числа 10 8 6. Вот другой пример: 5 -5 15 -2 1. Здесь есть возрастающая под-последовательность: -5 -2 1.
Если вы попробуете написать пять чисел так, чтобы из них нельзя было выбрать три возрастающих или три убывающих, то вскоре убедитесь, что не получится.
------------------
Вот три простых и красивых доказательства этой теоремы. В каком-то смысле это одно и то же доказательство, т.е. общий принцип у них одинаковый, но все же методы разные.
Первое доказательство - зрительное. Его проще нарисовать, чем объяснить, так что предлагаю читателю нарисовать описанное ниже в голове или на бумаге. Возьмем данные нам n2+1 чисел и будем их по одному выкладывать в столбики. Сначала первое число поставим в основание первого столбика. Затем каждое следующее число сравним с верхушками уже имеющихся столбиков: если оно больше или равно какой-то верхушки, поставим ее наверх этого столбика (самого левого из таких). А если нет такого, то поставим его в основание нового столбика справа от имеющихся.
Ясно, что внутри каждого столбика числа расположены снизу вверх по возрастанию (и в порядке, в котором они идут в последовательности). А кроме того, для каждого числа X из второго столбика или дальше найдется какое-то число Y из предыдущего столбика, которое больше его (и в последовательности раньше его). Ведь когда мы добавляли X, мы не поставили его на верхушку предыдущего столбика, где в это время уже стояло какое-то число Y; значит, X меньше Y.
Поэтому, если после того, как мы распределили все n2+1 чисел, у нас есть столбик высотой n+1 чисел или больше, то он дает нам возрастающую последовательность длиной n+1. А если у нас есть n+1 столбиков или больше, то начиная с числа в последнем столбике, мы можем, прыгая от столбика к столбику в обратном направлении, как описано в предыдущем абзаце, построить (от конца к началу) убывающую последовательность длиной n+1. Но если у нас и столбиков меньше n+1 (т.е. n или меньше), и в каждом столбике чисел меньше n+1 (т.е. n или меньше), то всего чисел у нас не больше n2, что противоречит условию. Значит, есть либо высокий столбик, либо много столбиков, что и требовалось доказать.
Это доказательство, в отличие от двух следующих, дает заодно простой алгоритм нахождения искомой под-последовательности.
Второе доказательство. У нас есть последовательность из n2+1 чисел. Каждому из них поставим в соответствие другое число: а именно, длину самой длинной возрастающей подпоследовательности, которая начинается с данного числа. Если у какого-то числа такая длина будет n+1 или больше, то это уже дает то, что требуется: возрастающую подпоследовательность длиной n+1. Поэтому предположим, что все такие длины находятся в границах от 1 до n. Но их - этих длин - мы нашли n2+1, по одной на каждое число, поэтому тогда среди них найдется обязательно n+1 одинаковое значение (если каждая возможная длина от 1 до n встречается не больше n раз, то всего есть не больше n2 длин). Пусть например это значение равно 5, т.е. есть n+1 разных числа в нашей последовательности, для каждого из которых длина самой длинной возрастающей подпоследовательности, начинающейся с него, равна 5. Но тогда каждое из этих чисел больше следующего: ведь если одно из них меньше следующего, и начиная со следующего уже есть возрастающая подпоследовательность длиной 5, то начиная с этого можно построить длиной 6, просто добавив его в начало; а мы знаем, что у каждого из них самая длинная - 5. Поэтому эти числа вместе составляют убывающую подпоследовательность длиной n+1.
Третье доказательство. Каждому числу X нашей последовательности поставим в соответствие пару чисел (G(X), L(X)), где G(X) - длина самой длинной возрастающей подпоследовательности, начиная с X, а L(X) - то же самое, но убывающей, начиная с X. Рассмотрим любые два числа в последовательности, X и Y, так что X стоит раньше Y. Если, например, X меньше или равно Y, то G(X) больше G(Y), потому что любую возрастающую подпоследовательность, начинающуюся с Y, можно продолжить, добавив X в начало, и она будет на единицу длиннее. Точто так же, если X больше Y, то заключаем, что L(X) больше L(Y). Отсюда следует, что ни у каких двух чисел не могут совпадать одновременно G(X) и L(X), т.е. разным членам последовательности соответствуют разные пары. Но если числа G(X) и L(X) всегда находятся в рамках от 1 до n, то разных пар из них можно составить всего n2, а у нас есть n2+1 членов последовательности. Поэтому хотя бы одно из чисел G(X) или L(X) больше или равно n+1, но это как раз и значит, что есть возрастающая или убывающая последовательность длиной n+1.
Что и требовалось доказать.
[по материалам: Monotone Sequence Theorem: literature thing; J. Michael Steele, Variations on the Monotone Subsequence Theme of Erdos and Szekeres]
У теоремы, которую доказали Erdos и Szekeres в 1935-м году, простое условие:
Теорема. Из последовательности чисел длиной n2+1 можно всегда выбрать возрастающую или убывающую под-последовательность длиной n+1.
"Выбрать под-последовательность" здесь означает, что из всей последовательности в n2+1 чисел можно отобрать n+1 идущих в ней по порядку (но необязательно один за другим, можно "с пропусками"), так что сами эти числа будут стоять либо от меньшего к большему, либо от большего к меньшему (возможно, с равенствами посредине).
Например, возьмем самый простой случай n=2, тогда n2+1=5, n+1=3. Т.е. утверждается, что если записать пять чисел подряд: например, 3 10 5 8 6, то, идя слева направо, можно будет отобрать три числа, которые либо все время возрастают, либо все время убывают. И действительно, в данном случае это числа 10 8 6. Вот другой пример: 5 -5 15 -2 1. Здесь есть возрастающая под-последовательность: -5 -2 1.
Если вы попробуете написать пять чисел так, чтобы из них нельзя было выбрать три возрастающих или три убывающих, то вскоре убедитесь, что не получится.
------------------
Вот три простых и красивых доказательства этой теоремы. В каком-то смысле это одно и то же доказательство, т.е. общий принцип у них одинаковый, но все же методы разные.
Первое доказательство - зрительное. Его проще нарисовать, чем объяснить, так что предлагаю читателю нарисовать описанное ниже в голове или на бумаге. Возьмем данные нам n2+1 чисел и будем их по одному выкладывать в столбики. Сначала первое число поставим в основание первого столбика. Затем каждое следующее число сравним с верхушками уже имеющихся столбиков: если оно больше или равно какой-то верхушки, поставим ее наверх этого столбика (самого левого из таких). А если нет такого, то поставим его в основание нового столбика справа от имеющихся.
Ясно, что внутри каждого столбика числа расположены снизу вверх по возрастанию (и в порядке, в котором они идут в последовательности). А кроме того, для каждого числа X из второго столбика или дальше найдется какое-то число Y из предыдущего столбика, которое больше его (и в последовательности раньше его). Ведь когда мы добавляли X, мы не поставили его на верхушку предыдущего столбика, где в это время уже стояло какое-то число Y; значит, X меньше Y.
Поэтому, если после того, как мы распределили все n2+1 чисел, у нас есть столбик высотой n+1 чисел или больше, то он дает нам возрастающую последовательность длиной n+1. А если у нас есть n+1 столбиков или больше, то начиная с числа в последнем столбике, мы можем, прыгая от столбика к столбику в обратном направлении, как описано в предыдущем абзаце, построить (от конца к началу) убывающую последовательность длиной n+1. Но если у нас и столбиков меньше n+1 (т.е. n или меньше), и в каждом столбике чисел меньше n+1 (т.е. n или меньше), то всего чисел у нас не больше n2, что противоречит условию. Значит, есть либо высокий столбик, либо много столбиков, что и требовалось доказать.
Это доказательство, в отличие от двух следующих, дает заодно простой алгоритм нахождения искомой под-последовательности.
Второе доказательство. У нас есть последовательность из n2+1 чисел. Каждому из них поставим в соответствие другое число: а именно, длину самой длинной возрастающей подпоследовательности, которая начинается с данного числа. Если у какого-то числа такая длина будет n+1 или больше, то это уже дает то, что требуется: возрастающую подпоследовательность длиной n+1. Поэтому предположим, что все такие длины находятся в границах от 1 до n. Но их - этих длин - мы нашли n2+1, по одной на каждое число, поэтому тогда среди них найдется обязательно n+1 одинаковое значение (если каждая возможная длина от 1 до n встречается не больше n раз, то всего есть не больше n2 длин). Пусть например это значение равно 5, т.е. есть n+1 разных числа в нашей последовательности, для каждого из которых длина самой длинной возрастающей подпоследовательности, начинающейся с него, равна 5. Но тогда каждое из этих чисел больше следующего: ведь если одно из них меньше следующего, и начиная со следующего уже есть возрастающая подпоследовательность длиной 5, то начиная с этого можно построить длиной 6, просто добавив его в начало; а мы знаем, что у каждого из них самая длинная - 5. Поэтому эти числа вместе составляют убывающую подпоследовательность длиной n+1.
Третье доказательство. Каждому числу X нашей последовательности поставим в соответствие пару чисел (G(X), L(X)), где G(X) - длина самой длинной возрастающей подпоследовательности, начиная с X, а L(X) - то же самое, но убывающей, начиная с X. Рассмотрим любые два числа в последовательности, X и Y, так что X стоит раньше Y. Если, например, X меньше или равно Y, то G(X) больше G(Y), потому что любую возрастающую подпоследовательность, начинающуюся с Y, можно продолжить, добавив X в начало, и она будет на единицу длиннее. Точто так же, если X больше Y, то заключаем, что L(X) больше L(Y). Отсюда следует, что ни у каких двух чисел не могут совпадать одновременно G(X) и L(X), т.е. разным членам последовательности соответствуют разные пары. Но если числа G(X) и L(X) всегда находятся в рамках от 1 до n, то разных пар из них можно составить всего n2, а у нас есть n2+1 членов последовательности. Поэтому хотя бы одно из чисел G(X) или L(X) больше или равно n+1, но это как раз и значит, что есть возрастающая или убывающая последовательность длиной n+1.
Что и требовалось доказать.
[по материалам: Monotone Sequence Theorem: literature thing; J. Michael Steele, Variations on the Monotone Subsequence Theme of Erdos and Szekeres]
