Задача про мощности

[Юстас]

$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\}$.

[Руст]

Пусть мощность 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 для конечных множеств, что и доказывает утверждение.

[er]

Руст писал(а):

Это доказывает, что |A+B|>=|A|+|B|-1 для конечных множеств, что и доказывает утверждение.

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

[Руст]

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

[maxal]

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