Доказать 1) если n>k^2 то существует убывающая или возрастающая последовательность из k+1 чисел. 2) если n<k^2 то не существует убывающей или возрастающей последовательности из k+1 чисел.

задан 16 Янв 20:37

10|600 символов нужно символов осталось
0

Условие сформулировано неаккуратно. В первом пункте нужно говорить о подпоследовательностях (потому что просто последовательности всегда существуют). Утверждение второго пункта неверно, так как исходная последовательность может быть монотонной. Утверждать можно лишь то, что при n<=k^2 (неравенство нестрогое) можно построить пример, когда монотонных подпоследовательностей длиной k+1 не найдётся.

1) Для каждого из чисел рассмотрим наибольшую длину возрастающей подпоследовательности, которая этим числом оканчивается. Пусть эта длина равна m. Также пусть n -- наибольшая длина убывающей подпоследовательности, которая оканчивается тем же числом. Если монотонные подпоследовательности имеют длину <=k, то пара (m,n) принимает не более k^2 значений. По принципу Дирихле, у двух членов a и b пары повторятся. Если a < b, то возрастающую последовательность можно продолжить от a к b, и у второго из членов не получится m. Если a > b, то продолжаем убывающую последовательность, и у второго члена не может получиться n.

2) Пример из k^2 можно построить так. Разобьём числа от 1 до k^2 на k групп по k чисел в каждой. Эти группы расставим в противоположном порядке. В пределах каждой группы числа идёт по возрастанию. Например, при k=3 получится 7, 8, 9, 4, 5, 6, 1, 2, 3. Тогда монотонной последовательности длиной k+1 не найдётся. Убывающей нет потому, что из одной группы нельзя брать сразу два числа. Возрастающей нет, так как её числа можно брать только в пределах одной группы.

ссылка

отвечен 16 Янв 21:03

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,019
×480
×322

задан
16 Янв 20:37

показан
217 раз

обновлен
16 Янв 21:03

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru