спасибо партии за это

Узнал сегодня, что в этом году мне подарят лишнюю секунду.

Спасибо. Учту.

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

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

У теоремы, которую доказали Erdos и Szekeres в 1935-м году, простое условие:

Теорема. Из последовательности чисел длиной n²+1 можно всегда выбрать возрастающую или убывающую под-последовательность длиной n+1.

"Выбрать под-последовательность" здесь означает, что из всей последовательности в n²+1 чисел можно отобрать n+1 идущих в ней по порядку (но необязательно один за другим, можно "с пропусками"), так что сами эти числа будут стоять либо от меньшего к большему, либо от большего к меньшему (возможно, с равенствами посредине).

Например, возьмем самый простой случай n=2, тогда n²+1=5, n+1=3. Т.е. утверждается, что если записать пять чисел подряд: например, 3 10 5 8 6, то, идя слева направо, можно будет отобрать три числа, которые либо все время возрастают, либо все время убывают. И действительно, в данном случае это числа 10 8 6. Вот другой пример: 5 -5 15 -2 1. Здесь есть возрастающая под-последовательность: -5 -2 1.
Если вы попробуете написать пять чисел так, чтобы из них нельзя было выбрать три возрастающих или три убывающих, то вскоре убедитесь, что не получится.

------------------

Вот три простых и красивых доказательства этой теоремы. В каком-то смысле это одно и то же доказательство, т.е. общий принцип у них одинаковый, но все же методы разные.

Первое доказательство - зрительное. ( Read more... )

Это доказательство, в отличие от двух следующих, дает заодно простой алгоритм нахождения искомой под-последовательности.

Второе доказательство. ( Read more... )

Третье доказательство. ( Read more... )

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

[по материалам: Monotone Sequence Theorem: literature thing; J. Michael Steele, Variations on the Monotone Subsequence Theme of Erdos and Szekeres]