Принцип Дирихле (монотонная подпоследовательность)

[nbyte]

Здравствуйте.
Никак немогу понять теорему. (возможно потомучто нам дали неособо хорошую формулировку)

Цитата:

Теорема Допустим $n,m \in N$ и $a_1,a_2,…,a_{(mn+1)}$ любая последовательность множества реальных чисел из $(mn+1)$ элемента. Тогда в ней существует монотонно возрастающее подмножество из $(m+1)$ элемента или монотонно убывающее подмножество из $(m+1)$ элемента.
Возможны и оба варианта.

Подскажите пожалуйста как её можно понять или какойнибудь учебник в котором описывается есть эта теорема.

Добавлено спустя 3 минуты 20 секунд:

(У меня тут проблема с формулой
Немогу a_(mn+1) в нижний регистр поместить.
Как тут сделать?)

[Xaositect]

nbyte в сообщении #210985 писал(а):

(У меня тут проблема с формулой
Немогу a_(mn+1) в нижний регистр поместить.
Как тут сделать?)

a_{mn+1}

[vlad239]

Допустим это не так. Сопоставим каждому элементу пару чисел - длину максимальной возрастающей последовательности, начиная с этого числа, и длину максимальной убывающей. Если утверждение неверно, то все эти пары попадают в интервал $(1,1)-(m,n)$. Тогда там найдутся две одинаковых. Сравните соответствующие числа - будет противоречие.

Берите $mn-1$ в фигурные скобки.

Влад.
P.S. Да. Я не знаю, что такое реальные числа. Вряд ли это лияет на решение.

[Xaositect]

nbyte в сообщении #210985 писал(а):

реальных чисел

действительных!

[nbyte]

А уже понял. Жалко, что раньше не понял.
Спасибо вам что подсказали.

[VAL]

nbyte писал(а):

Никак немогу понять теорему. (возможно потомучто нам дали неособо хорошую формулировку)

Цитата:

Теорема Допустим $n,m \in N$ и $a_1,a_2,…,a_{(mn+1)}$ любая последовательность множества реальных чисел из $(mn+1)$ элемента. Тогда в ней существует монотонно возрастающее подмножество из $(m+1)$ элемента или монотонно убывающее подмножество из $(m+1)$ элемента.
Возможны и оба варианта.

Вам уже подсказали и Вы уже поблагодарили за помощь...
А, между тем, верно предположение о не слишком хорошей формулировке. Формулировка настолько "неособо хороша", что просто неверна.

Во-первых, в условии ничего не говорится том, обязаны ли элементы последовательности быть попарно рпзличны. А то ведь можно все одинаковые взять. Неубывающую последовательность из таких чисел построить можно, а возрастающую... увы!

Во-вторых, что это за "монотонно возрастающее множество". Множество вообще по определению неупорядочено. Наверное, речь должна идти о подпоследовательностях.

Наконец, в-третьих. Пусть $m=2, n=1$. Попробуйте-ка выделить из последовательности $1, 3, 2$ возрастающую или убывающую подпоследовательность из трех элементов.
Вот если бы возрастающая была из $m+1$ элемента, а убывающая из $n+1$...

[Dandan]

Да, правильная формулировка:
... существует неубывающая подпоследовательность из $m+1$ элемента или убывающая из $n+1$
решение vlad239 как раз такую формулировку и подразумевает