три доказательства
Nov. 16th, 2008 01:43 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЭта запись может быть интересна тем, кого интересуют числа, доказательства, математика.
У теоремы, которую доказали 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]
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-11-16 01:40 pm (UTC)А когда (давно) читал первоначальную статью, вообще не знал этой идеи. Там было что-то длинное и корявое, хитро по индукции. Совершенно не запоминаемое.
no subject
Date: 2008-11-16 05:47 pm (UTC)no subject
Date: 2008-11-16 05:51 pm (UTC)no subject
Date: 2008-11-16 02:41 pm (UTC)Почему-то довольно редко эту теорему формулируют в более общем, можно сказать, рамсеевском виде: из pq+1 чисел всегда можно выбрать либо возрастающую последовательность из p+1 числа, либо убывающую последовательность из q+1 числа.
no subject
Date: 2008-11-16 02:53 pm (UTC)no subject
Date: 2008-11-20 09:42 am (UTC)Что таблица Юнга получается, это я вижу. А дальше?
no subject
Date: 2008-11-20 11:05 am (UTC)no subject
Date: 2008-11-20 01:41 pm (UTC)Идея ясна, буду разбираться.
no subject
Date: 2008-11-16 04:01 pm (UTC)"так что сами эти числа будут стоять либо от меньшего к большему, либо от большего к меньшему (возможно, с равенствами посредине)."
no subject
Date: 2008-11-16 08:50 pm (UTC)no subject
Date: 2008-11-17 08:31 am (UTC)no subject
Date: 2008-11-17 08:42 am (UTC)no subject
Date: 2008-11-17 09:43 am (UTC)no subject
Date: 2008-11-17 09:54 am (UTC)1 - второй столбик
2 - первый столбик
1 - второй столбик
2
2 1
1 1
В первом столбике есть три числа, поэтому этот метод дает 1,2,2.
no subject
Date: 2008-11-17 10:47 am (UTC)2 2
1 1 1
?
no subject
Date: 2008-11-17 11:32 pm (UTC)no subject
Date: 2008-11-17 11:34 pm (UTC)no subject
Date: 2008-11-18 09:02 am (UTC)no subject
Date: 2008-11-16 06:01 pm (UTC)no subject
Date: 2008-11-16 08:51 pm (UTC)no subject
Date: 2008-11-16 09:06 pm (UTC)no subject
Date: 2008-11-16 06:02 pm (UTC)различных чисел?
no subject
Date: 2008-11-16 08:52 pm (UTC)no subject
Date: 2008-11-16 06:52 pm (UTC)no subject
Date: 2008-11-16 08:15 pm (UTC)789456123
no subject
Date: 2008-11-16 07:12 pm (UTC)no subject
Date: 2008-11-16 08:52 pm (UTC)