2014 dxdy logo

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

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




 
 Множество из n действительных чисел
Сообщение07.01.2010, 19:07 
Доказать, что для любого множества из $n$ ненулевых действительных чисел существует такое его подмножество $M$, что для любых $a, b \in M$ $a+b\notin M$, причём $|M|>\frac n 3$.

 
 
 
 Re: Множество из n действительных чисел
Сообщение08.01.2010, 09:59 
Аватара пользователя
Я знаю такое док-во.

Во-первых, не теряя общности, можно считать, что все числа целые. Действительно, возьмём порождённую нашими числами группу по сложению. Это конечно порождённая абелева группа без кручения, т. е. $\mathbb Z^r$ при некотором $r\in\mathbb N$, при этом наши числа заключены в некотором "кубике" $|x_\nu|\le A$, $A\in\mathbb N$. Если число из нашего множества представляется вектором $\overline x=(x_1,\ldots,x_r)$, то поставим ему в соответствие целое число $\sum_{\nu=1}^r x_\nu(2A+1)^{\nu-1}$. Получим множество из $n$ целых чисел. Понятно, что достаточно решить задачу для него.

Во-вторых, возьмём большое простое число вида $p=3k+2$ и отождествим наши $n$ чисел с элементами $\mathbb F_p=\mathbb Z/p\mathbb Z$. Т. е. на самом деле доказываем утверждение для $\mathbb F_p$.

Подготовительная работа закончилась, теперь начинается собственно доказательство. Пусть $A\subseteq\mathbb F_p^*$ --- наше множество. Рассмотрим случайное множество $M(\xi)=\bigl\{a\in A\mid \xi a\in\{k+1,k+2,\ldots,2k+1\}\bigr\}$, где $\xi$ равномерно распределено на $\mathbb F_p^*$ (напомню, что $p=3k+2$). Воспользовавшись линейностью матожидания, легко посчитать средний размер множества $M(\xi)$: $\mathbf E|M(\xi)|=\frac{(k+1)n}{3k+1}>n/3$. Соответственно, при некотором $\xi$ выполнено $|M(\xi)|>n/3$. Это и есть наше множество $M$.

Блин, набил всю эту простыню и нашёл ссылку: ссылка.

 
 
 
 Re: Множество из n действительных чисел
Сообщение09.01.2010, 11:17 
Аватара пользователя
и на нашем форуме уже было: post125959.html#p125959

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


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