2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Задача про мощности
Сообщение02.08.2006, 18:49 
Заслуженный участник


01/12/05
458
$A, B \subset \mathbb{Z}_2^K$. Известно, что для некоторого N$|A|+|B|>2^N$. Доказать, что
$|A+B|\geqslant 2^N$, где $A+B=\{a+b|a\in A, b\in B\}$.

 Профиль  
                  
 
 
Сообщение03.08.2006, 15:02 
Заслуженный участник


09/02/06
4382
Москва
Пусть мощность A больше или равно мощности B, тогда $|A|\ge 2^N$, когда мощность N бесконечна, следовательно $|A+B|\ge |A|\ge 2^N$. Если мощность N конечна и мощность B равно 1, то так же ничего доказывать. Упорядочим элементы $Z_2^K$: x>= y тогда и только тогда, когда носитель у содержится в носителе х.
Этот порядок позволяет установить, что множества $A+\{x\}\not =A+\{y\}$ не совпадают. Берём минимальный элемент x0 по этому упорядочению в B. Подножество $A+\{x0\}$ множества A+B имеет мощность |A|. Далее при каждом добавлении элементов в множество B по росту множество A+B увеличивается по крайней мере на один новый элемент. Если добавленный в В элемент у больше любого из предыдущих элементов, то взяв максимальный элемент a из A/B получим новый элемент. В противном случае она несравнима с добавленными элементами начиная с некоторого. При этом взяв некоторый минимальный элемент а, убеждаемся, что а+у ранее не встречался. Это доказывает, что |A+B|>=|A|+|B|-1 для конечных множеств, что и доказывает утверждение.

 Профиль  
                  
 
 
Сообщение03.08.2006, 21:47 


06/03/06
150
Руст писал(а):
Это доказывает, что |A+B|>=|A|+|B|-1 для конечных множеств, что и доказывает утверждение.


Ну, это то не верно. Пусть $K$ конечно и $A=B =\mathbb{Z}_2^K$.

 Профиль  
                  
 
 
Сообщение03.08.2006, 22:13 
Заслуженный участник


09/02/06
4382
Москва
Да вы правы, я не рассмотрел случай A/B пусто, когда новые элементы не добавляются, но в этом случае уже имеющихся элементов $2^N$. Вообщем, требуется улучшать доказательство для конечной мощности.

 Профиль  
                  
 
 
Сообщение04.08.2006, 00:45 
Модератор
Аватара пользователя


11/01/06
5660
Вот тут есть решение: http://community.livejournal.com/ru_math/337300.html

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group