?

Log in

No account? Create an account
три доказательства - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

три доказательства [ноя. 16, 2008|01:43 pm]
Anatoly Vorobey
Эта запись может быть интересна тем, кого интересуют числа, доказательства, математика.

У теоремы, которую доказали 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]
СсылкаОтветить

Comments:
[User Picture]From: flaass
2008-11-16 01:40 pm
Ух ты! Первого изложения я не знал.
А когда (давно) читал первоначальную статью, вообще не знал этой идеи. Там было что-то длинное и корявое, хитро по индукции. Совершенно не запоминаемое.

(Ответить) (Thread)
[User Picture]From: french_man
2008-11-16 05:47 pm
А я именно первым способом доказал когда-то.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2008-11-16 05:51 pm
Крут!
(Ответить) (Parent) (Thread)
[User Picture]From: spartach
2008-11-16 02:41 pm
Да, про столбики очень симпатично, спасибо.

Почему-то довольно редко эту теорему формулируют в более общем, можно сказать, рамсеевском виде: из pq+1 чисел всегда можно выбрать либо возрастающую последовательность из p+1 числа, либо убывающую последовательность из q+1 числа.
(Ответить) (Thread)
From: ext_105441
2008-11-16 02:53 pm
Первое изложение отличное, да. Вариации на тему Робинсона-Шенстеда-Кнута, так сказать.
(Ответить) (Thread)
[User Picture]From: zelych
2008-11-20 09:42 am
А можно в двух словах, в чём связь?
Что таблица Юнга получается, это я вижу. А дальше?
(Ответить) (Parent) (Thread)
From: ext_105441
2008-11-20 11:05 am
Ну как бы это так сказать - давайте будем считать, что изначальная последовательность была перестановкой чисел от 1 до pq+1 (ну то есть соорудим изоморфизм упорядоченных множеств, если говорить научно). Тогда то, что построено в доказательстве номер один, это просто одна из двух таблиц Юнга, которые отвечают перестановке с помощью соответствия Робинсона-Шёнстеда-Кнута (с точностью до мелочей и разных определений). Раз у нас pq+1 чисел, наша диаграмма не влезает в прямоугольник p\times q. Ну а теперь лемма - если из перестановки после применения алгоритма Р-С-К получилась диаграмма Юнга Д, то в перестановке есть возрастающая подпоследовательность, длина которой равна длине первой строки Д, и убывающая подпоследовательность, длина которой равна длине первого столбца Д (ну и эти длины на самом деле максимально возможные).
(Ответить) (Parent) (Thread)
[User Picture]From: zelych
2008-11-20 01:41 pm
Cпасибо большое!
Идея ясна, буду разбираться.
(Ответить) (Parent) (Thread)
[User Picture]From: petrazmus
2008-11-16 04:01 pm
Я не математик, но из формулировок и текста Вашего не следует, что в последовательности не может быть равных чисел? Такое возможно?
"так что сами эти числа будут стоять либо от меньшего к большему, либо от большего к меньшему (возможно, с равенствами посредине)."
(Ответить) (Thread)
[User Picture]From: avva
2008-11-16 08:50 pm
Нет, как раз из процитированного вами следует, что все работает и когда некоторые числа равны - если понимать под "возрастающая" то, что каждое число больше или равно (а не строго больше) предыдущего, и то же самое про "убывающая".

(Ответить) (Parent) (Thread)
[User Picture]From: petrazmus
2008-11-17 08:31 am
Опять же не математик я, но где в Ваших начальных условиях оговаривается, что последовательность чисел {1,2,1,2,1} не годится?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-11-17 08:42 am
годится - в ней возрастающая подпоследовательность это 1,1,1 - опять-таки, если в "возрастающая" разрешить также равные числа.
(Ответить) (Parent) (Thread)
[User Picture]From: petrazmus
2008-11-17 09:43 am
Тогда докажите эту теорему для этой последовательности первым способом...
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-11-17 09:54 am
1, 2 - первый столбик
1 - второй столбик
2 - первый столбик
1 - второй столбик

2
2 1
1 1

В первом столбике есть три числа, поэтому этот метод дает 1,2,2.
(Ответить) (Parent) (Thread)
[User Picture]From: petrazmus
2008-11-17 10:47 am
А где сказано что столбики не могут быть такими
2 2
1 1 1
?
(Ответить) (Parent) (Thread)
[User Picture]From: alexey_rom
2008-11-17 11:32 pm
Могут. 1 1 1 и есть столбик высоты 3.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-11-17 11:34 pm
Если действовать по алгоритму, как он описан, то вторая двойка идет в верхушку первого столбика - перечитайте описание.

(Ответить) (Parent) (Thread)
[User Picture]From: petrazmus
2008-11-18 09:02 am
Алгоритм поправлен :-)
(Ответить) (Parent) (Thread)
[User Picture]From: dmarck
2008-11-16 06:01 pm
Толя, в оригинальном утверждении надо бы заменить возрастающую или убывающую на невозрастающую или неубывающую, иначе возникают проблемы с формулировками, как уже было указано выше.
(Ответить) (Thread)
[User Picture]From: avva
2008-11-16 08:51 pm
См. выше. Я не хочу использовать слова "невозрастающая" итд., потому что я хочу, чтобы док-во было понятно и людям, плохо знающим/помнящим математику, а для них дополнительный уровень косвенности может сильно затемнить картину.

(Ответить) (Parent) (Thread)
[User Picture]From: dmarck
2008-11-16 09:06 pm
Fair enough, как говорят в рассылках ;-)
(Ответить) (Parent) (Thread)
[User Picture]From: moon_aka_sun
2008-11-16 06:02 pm
> Из последовательности чисел
различных чисел?
(Ответить) (Thread)
[User Picture]From: avva
2008-11-16 08:52 pm
см. выше.

(Ответить) (Parent) (Thread)
[User Picture]From: deni_ok
2008-11-16 06:52 pm
Интересно, а что в обратную сторону? Если есть последовательность длины n, то можно что-то сказать о гарантированной самой длинной монотонной подпоследовательности?
(Ответить) (Thread)
[User Picture]From: ilya_dogolazky
2008-11-16 08:15 pm
оценка в теореме строгая, вот пример (для н=3 его очень просто набрать на цифровом блоке клавиатуры :-)

789456123
(Ответить) (Parent) (Thread)
From: ext_72902
2008-11-16 07:12 pm
Последнее - класс, не знал. Почему-то везде, где видел, приводится второе.
(Ответить) (Thread)
[User Picture]From: avva
2008-11-16 08:52 pm
Да, мне тоже третье больше нравится, чем второе, своей симметрией.

(Ответить) (Parent) (Thread)