2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Принцип Дирихле (монотонная подпоследовательность)
Сообщение04.05.2009, 20:38 
Здравствуйте.
Никак немогу понять теорему. (возможно потомучто нам дали неособо хорошую формулировку)
Цитата:
Теорема Допустим $n,m \in N$ и $a_1,a_2,…,a_{(mn+1)}$ любая последовательность множества реальных чисел из $(mn+1)$ элемента. Тогда в ней существует монотонно возрастающее подмножество из $(m+1)$ элемента или монотонно убывающее подмножество из $(m+1)$ элемента.
Возможны и оба варианта.

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

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

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

 
 
 
 
Сообщение04.05.2009, 20:41 
Аватара пользователя
nbyte в сообщении #210985 писал(а):
(У меня тут проблема с формулой
Немогу a_(mn+1) в нижний регистр поместить.
Как тут сделать?)

Код:
a_{mn+1}

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

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

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

 
 
 
 
Сообщение04.05.2009, 20:42 
Аватара пользователя
nbyte в сообщении #210985 писал(а):
реальных чисел

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

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

 
 
 
 Re: Принцип Дирихле
Сообщение04.05.2009, 23:01 
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$...

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group