Доказать монотонность последовательности

ssz1977

Дано 101 число a_1,a_2,...,a_101. Доказать, что существует 11 чисел таких, что a_{i_k}-монотонна при условии, что i_1<...<i_11.

lenmas

Это ж из прошлой Московской городской олимпиады, вроде, поищи там решение Там какое-то простое решение. Что-то связанное с инверсией?

ssz1977

Да, это из олимпиады. А где поискать?
Вроде уже везде перешарила.

lenmas

Такой ход рассуждений не пойдет: берем a_1, ищем по порядку номеров следующий, чтобы он был не меньше этого, потом для нового элемента следующий не меньший, и так пока номер не дойдет до 101. Если полученная цепочка длиннее 10, то все доказано. Если длина меньше или равна 10, то берем первый незадействованный в первой цепочке элемент, он должен быть меньше чем первый элемент первой цепочки, и вытаскиваем из него свою цепочку. Если цепочка опять получается длины меньше 11, то берем следующий по номеру незадействованный элемент (меньший первых двух первых элементов вытащенных цепочек и так далее. В итоге разобьем на цепочки. Число цепочек больше 10, иначе бы было задействовано только меньше либо равно 100 элементов. И первые элементы цепочек образуют убывающую последовательность

ssz1977

решение должно быть численным

zuzaka

давай числа

Diossa

Такой ход рассуждений не пойдет: берем a_1, ищем по порядку номеров следующий, чтобы он был не меньше этого, потом для нового элемента следующий не меньший, и так пока номер не дойдет до 101. Если полученная цепочка длиннее 10, то все доказано. Если длина меньше или равна 10, то берем первый незадействованный в первой цепочке элемент, он должен быть меньше чем первый элемент первой цепочки , и вытаскиваем из него свою цепочку. Если цепочка опять получается длины меньше 11, то берем следующий по номеру незадействованный элемент (меньший первых двух первых элементов вытащенных цепочек и так далее. В итоге разобьем на цепочки. Число цепочек больше 10, иначе бы было задействовано только меньше либо равно 100 элементов. И первые элементы цепочек образуют убывающую последовательность
почему?

zuzaka

должно быть: "он должен быть меньше, чем один из элементов предыдущей цепочки". И все окей

Diossa

ну он меньше того элемента предыдущей цепочки который ближне к нему слева и что дальше?

zuzaka

Да, ты прав. Ошибка во фразе
то берем следующий по номеру незадействованный элемент (меньший первых двух первых элементов вытащенных цепочек
даже если снять требование первости элементов, он будет меньше лишь предпоследнего элемента второй цепочки

lenmas

Согласен, я неправ

lenmas

Кажется, можно исправить положение - видно из картинки, что каждый элемент второй цепочки меньше некоторого элемента из первой цепочки (а именно, как сказал , ближайшего к нему элемента слева из первой цепочки). То же самое относится к элементам третьей цепочки и так далее. А оставшийся 101 элемент потянет за собой убывающее "сечение" всех цепочек, пересекающее все 10 цепочек по одному элементу. Или опять налажал?

Diossa

ты прав!
но надо бы все точно расписать

ssz1977

полностью согласна

Diossa

берем a_1, ищем по порядку номеров следующий, чтобы он был не меньше этого, потом для нового элемента следующий не меньший, и так пока номер не дойдет до 101. Если полученная цепочка длиннее 10, то все доказано. Если длина меньше или равна 10, то берем первый незадействованный в первой цепочке элемент и вытаскиваем из него свою цепочку из ранее не выбранных элементов. Заметим, что каждый элемент второй цепочки меньше какого-то элемента из первой цепочки с меньшим номером (т.е. находящийся слева от него). Ведь если это не так, то этот элемент должен был входить в первую цепочку, по нашему построению цепочки. Если цепочка опять получается длины меньше 11, то берем следующий по номеру незадействованный элемент и строим новую цепочку по тем же правилам. итд. В итоге мы разобьем нашу исходную последовательность на цепочки. притом каждый элемент k-й цепочки меньше какого-нибудь элемента предыдущей цепочки с меньшим номером(т.е. находящийся слева от него). У нас получитс не менее 11 цепочек, т.к. элементов всего 101 а длина каждой цепочки не более 10.
из последней цепочки выбираем любой элемент. Как было доказано, он меньше какого-то элемента из предыдущей цепочки стоящей слева от него, который в свою очередь меньше какого-то элемента из цепочки, предыдущей его цепочке, тоже стоящей слева. итд. Т.к. цепочек не менее 10 то мы выбранные числа будут удовлетворять условиям задачи
как давно не писал доказательства задач.... но что-то типа этого должно быть

ssz1977

Всем спасибо!
Оставить комментарий
Имя или ник:
Комментарий: