Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

три доказательства

Эта запись может быть интересна тем, кого интересуют числа, доказательства, математика.

У теоремы, которую доказали 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]
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 27 comments