из аспирантских домашек

[Профессор Снэйп]

TOTAL писал(а):

maxal писал(а):

1) Пусть $A$ - конечное множество ненулевых целых чисел. Докажите, что существует подмножество $B\subset A$ такое, что $|B|>\frac{|A|}{3}$ и $B$ свободно от сумм, то есть $\forall x,y,z\in B\quad x+y\ne z$.

Во м-во $B$ берём более трети от чисел делящихся на 3 (по индукции) и все числа с остатком 1 при делении на 3 (или с остатком 2, если таких больше). Если все числа делятся на 3, то надо сначала вынести за скобки общую степень тройки.

Непонятно, почему выбранное таким образом множество $B$ будет свободно от сумм.

Вот берём $x,y \in B$. Если эти числа дают одинаковые остатки при делении на $3$, то по выбору $B$ сумма $x+y$ действительно не лежит в $B$. Ну а если, к примеру, $x$ делится на $3$, а $y$ не делится. Что тогда?

[TOTAL]

Профессор Снэйп писал(а):

TOTAL писал(а):

maxal писал(а):

1) Пусть $A$ - конечное множество ненулевых целых чисел. Докажите, что существует подмножество $B\subset A$ такое, что $|B|>\frac{|A|}{3}$ и $B$ свободно от сумм, то есть $\forall x,y,z\in B\quad x+y\ne z$.

Во м-во $B$ берём более трети от чисел делящихся на 3 (по индукции) и все числа с остатком 1 при делении на 3 (или с остатком 2, если таких больше). Если все числа делятся на 3, то надо сначала вынести за скобки общую степень тройки.

Непонятно, почему выбранное таким образом множество $B$ будет свободно от сумм.

Оно не будет свободно, ведь maxal уже опроверг мое "решение", я согласен с опровержением.

[maxal]

На правах подсказки: известное мне решение не является конструктивным. Возможно, найти конструктивное решение гораздо сложнее.

И, кстати, вы заметили там задачку под номером 2)? Или все вслед за Рустемом ее бойкотируют из-за недостаточной сложности?

[maxal]

Ну что ж, видимо пора давать решение.
Цитирую из книги Alon N., Spenser J. — The probabilistic method:



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

Напоминаю также вторую задачу:

Задача 2. Докажите, что для любого натурального $n$ и любой раскраски ребер полного графа $K_n$ в 2 цвета в нём обязательно найдется одноцветное остовное дерево.

[Kid Kool]

maxal писал(а):

Задача 2. Докажите, что для любого натурального $n$ и любой раскраски ребер полного графа $K_n$ в 2 цвета в нём обязательно найдется одноцветное остовное дерево.

Так это ж тривиально: индукция: выкинули вершину, в оставшемся графе нашли черное остовное поддерево. Если из выкинутой вершинв выходит хоть одно черное ребро, то ее можно добавить к полученному остовному дереву. Иначе белое остовное дерево образуется выкинутой вершиной и всеми выходящими из нее ребрами.