Получить монотонную последовательность удалением из заданной

[Tik-tak]

Помогите решить задачу:
На доске выписана перестановка чисел от $1$ до $n^2 +1$, $n \in \mathbb{N}$. Требуется доказать, что можна вытереть некоторые из них, так что останется $n +1$ число, которые либо будут расположены в порядке возрастания, либо в порядке спадания.

[antbez]

Не совсем ясно... Останется $n+1$ чисел?

[V.V.]

Если $n\geqslant (p-1)(q-1)+1$, то в любой перестановке чисел от $1$ до $n$
существует врзрастающая подпоследовательность длины $p$ или убывающая
подпоследовательность длины $q$.


Доказательство 1. Пусть для каждого числа $k$ числа $a_k$ и $b_k$
обозначают наибольшую длину соответственно возрастающей и убывающей
подпоследовательностей в перестановке чисел от $1$ до $n$, в которых $k$~---
последний член.

Предположим, что в перестановке число $i$ встречается раньше, чем число $j$.
Если $i<j$, то $a_i<a_j$ (поскольку любую возрастающую последовательность,
заканчивающуюся числом $i$, можно продолжить числом $j$). Если $i>j$, то
$b_i<b_j$ (поскольку любую убывающую последовательность, заканчивающуюся числом
$i$, можно продолжить числом $j$).
Поэтому при различных $i$ и $j$ пары чисел $(a_i,b_i)$ и $(a_j,b_j)$ также
различны. Значит, имеем $n$ различных пар указанного вида.
Если все возрастающие подпоследовательности имеют длину меньше $p$, то для
любого $k$ имеем $a_k\leqslant p-1$. Если все убывающие последовательности имеют
длину меньше $q$, то для любого $k$ имеем $b_k\leqslant q-1$. Но тогда всего пар
$(a_k,b_k)$ будет не больше $(p-1)(q-1)$, т.е. меньше $n$. Противоречие.



Доказательство 2. Проведем индукцию по $p+q$. База очевидна. Переход от
$p+q-1$ к $p+q$. Рассмотрим последовательность из $(p-1)(q-1)+1$ члена.
Поскольку число членов последовательностей больше $(p-2)(q-1)+1$, то по
предположению индукции найдется либо возрастающая подпоследовательность длины
$p-1$, либо убывающая подпоследовательность длины $q$ (и тогда мы нашли то, что
требуется). Среди всех возрастающих подпоследовательностей длины $(p-1)$
рассмотрим ту, у которой максимальный член (обозначим его $b_1$) расположен в
исходной последовательности как можно левее. Вычеркнем число $b_1$. У нас
останется $(p-1)(q-1)>(p-2)(q-1)+1$ членов. Опять выберем подпоследовательность
длины $p-1$, у которой максимальное число (обозначим его $b_2$) расположено как
можно левее. Очевидно, $b_1>b_2$. Вычеркнем $b_2$. Продолжая такие же построения
дальше, мы получим убывающую подпоследовательность из $q$ членов.


Доказательство 3.
Положим $a_1^{(1)}=a_1$. Пусть $a_2^{(1)}$~--- первое из оставшихся чисел,
которое больше $a_1^{(1)}$, $a_3^{(1)}$~--- первое из следующих за $a_2^{(1)}$
чисел, которое больше $a_2^{(1)}$ и т.д. Мы построили возрастающую
подпоследовательность $\{a_k^{(1)}\}$. Вычеркнем все ее члены из нашей
последовательности, после чего аналогично, используя только оставшиеся числа,
построим подпоследовательность $\{a_k^{(2)}\}$. Вычеркнем и ее, после чего
аналогично построим последовательность $a_3^{(k)}$ и т.д. Если хоть одна из
построенных подпоследовательностей состоит хотя бы из $p$ членов, задача
решена. В противном случае каждая из подпоследовательностей содержит не более
$p-1$ член и, значит, мы построим не менее $q$ подпоследовательностей.

Построим тогда убывающую подпоследовательность из $q$ членов. Пусть $b_q$~---
наибольшее (последнее) число в подпоследовательности $a_k^{(q)}$. Пусть
$b_{q-1}$~--- наибольшее число в подпоследовательности $a_k^{(q-1)}$,
расположенное левее $b_q$. Пусть $b_{q-2}$~--- наибольшее число в
подпоследовательности $a_k^{(q-1)}$, расположенное левее $b_{q-1}$, и т.д.
Пользуясь правилом построения последовательностей $\{a_k^{(i)}\}$, нетрудно
показать, что правильно построения подпоследовательности $\{b_k\}$ корректно и
что эта последовательность убывает.


Доказательство 4. Это рассуждение использует алгоритм
Робинсона-Шенстеда-Кнута. Рассмотрим нашу последовательность. Напишем первое ее
число в левой верхней клетке клетчатого листа бумаги. Будем добавлять новые
числа и переставлять имеющиеся по следующему алгоритму.

\begin{tabular}{p{11mm}p{144mm}} Шаг 1. & Возьмем очередное число последовательности. Назовем его текущим числом. Верхнюю левую клетку листа назовем текущей клеткой.\\ Шаг 2. & Если текущая клетка пуста, поставим в нее текущее число и перейдем к шагу 1, иначе перейдем к шагу 3.\\ Шаг 3. & Если текущее число меньше числа в текущей клетке, передвинемся на одну клетку вправо, назовем эту клетку текущей и перейдем к шагу 2; если же текущее число больше числа в текущей клетке, впишем в текущую клетку вместо имеющегося там числа текущее число, после чего назовем текущим число, только что удаленное из текущей клетки, сдвинемся на одну строку вниз, назовем ее самую левую клетку текущей и перейдем к шагу 2. \end{tabular}
В результате выполнения этого алгоритма числа нашей последовательности
окажутся расположенными в клетках фигуры, которая называется диаграммой Юнга.
Диаграмма Юнга состоит из нескольких горизонтальных рядов клеток, выровненных по
левому краю, причем каждый следующий ряд содержит не больше клеток, чем
предыдущий. Заметим, что если числа занимают $(p-1)(q-1)+1$ клетку, то в
полученной диаграмме либа первая строка содержит минимум $q$ клеток, либо первый
столбец~--- минимум $p$ клеток (в противном случае диаграмма содержалась бы в
прямоугольнике $(q-1)\times(p-1)$ и состояла бы не более, чем из $(p-1)(q-1)$
клеток). Оба случая означают наличие требуемой монотонной подпоследовательности.

[Tik-tak]

V.V. спасибо за столько решений

[TOTAL]

V.V. писал(а):

{\sf Доказательство 4}. Это рассуждение использует алгоритм Робинсона-Шенстеда-Кнута.

$p=q=3$, числа $41325$. Какая будет таблица?
У меня получается
532
4
1
но последовательности в первой строке и первом столбце неправильные.

[V.V.]

А я разве обещал, что будут _правильные_ последовательности?

[TOTAL]

V.V. писал(а):

А я разве обещал, что будут _правильные_ последовательности?

Тогда откуда следует наличие требуемой подпоследовательности?

[V.V.]

TOTAL, из построения.

Если была правильная последовательность, то мы её, конечно, портим, но строка (столбец) все равно остается.

[TOTAL]

V.V. писал(а):

TOTAL, из построения.

Если была правильная последовательность, то мы её, конечно, портим, но строка (столбец) все равно остается.

Что значит строка (столбец) останется?
Да я как попало буду бросать числа в прямоугольник и всегда получу длинную строку или длинный столбец.

Не надо заменять одно число на другое. Очередное число надо приставлять справа к самой верхней строке с сохранением в ней убывающего порядка. Если приставить невозможно, то начинаем новую строку. В результате для каждого числа (не из первой строки) найдется меньшее число из предыдущей строки, которое имеет меньший порядковый номер. При такой раскладке числа 41325 выстроятся в таблицу
41
32
5
В такой таблице легко выделить искомую (в данном случае возрастающую) последовательность.

[alper]

Помогите, пожалуйста решить задачу из книги Н. Б. Алфутова, А. В. Устинов. "Алгебра и теория чисел. Сборник задач для математических школ", в книге решения или указания нет.

Условие: Числа от 1 до 101 выписаны в произвольном порядке. Докажите, что из них можно вычеркнуть 90 чисел так, что оставшиеся 11 чисел будут следовать одно за другим в порядке возрастания или убывания.

[ИСН]

"Боян, было год назад".
http://mathworld.wolfram.com/Erdos-SzekeresTheorem.html
и здесь, кажется, тоже где-то разбирали.

[TOTAL]

Смотрите здесь http://dxdy.ru/topic17582.html

[alper]

Большое спасибо за обе ссылки!