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

[maxal]

Буду сюда потихоньку выкладывать самые интересные задачки (в основном по теории чисел, теории графов, комбинаторике и криптографии) из своих пыльных архивов. Начну, пожалуй, с "классики":

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

1*) Можете ли вы усилить это утверждение до $|B|>|A|\left(\frac{1}{3}+\epsilon\right)$ для какого-нибудь $\epsilon > 0$ или хотя бы до $|B|>\frac{|A|}{3}+m$ для какого-нибудь целого $m>0$ ?
_________________

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

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

maxal писал(а):

1*) Можете ли вы усилить это утверждение до $|B|>|A|\left(\frac{1}{3}+\epsilon\right)$ или хотя бы до $|B|>\frac{|A|}{3}+\epsilon$ для какого-нибудь $\epsilon > 0$ ?

Фраза "хотя бы" в условии выглядит, на мой взгляд, довольно странно. Возьмите $\varepsilon < 1/3$ и тогда неравенства

$$ |B| > \frac{|A|}{3} $$

и

$$ |B| > \frac{|A|}{3} + \varepsilon $$

будут эквивалентны, ибо числа $|A|$, $|B|$ --- целые.

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

А что обозначает знак после условия задачи? Значит ли это, что ответ неизвестен Вам самому?

[maxal]

Во втором случае имелось в виду целое число на самом деле. Сейчас исправлю. А знак будет означать повышенную сложность или открытую проблему (или и то, и другое в зависимости от вариантов). В данном случае ответ мне неизвестен, что впрочем не означает, что это на самом деле открытая проблема

[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, то надо сначала вынести за скобки общую степень тройки.

[Руст]

maxal писал(а):

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

1*) Можете ли вы усилить это утверждение до $|B|>|A|\left(\frac{1}{3}+\epsilon\right)$ для какого-нибудь $\epsilon > 0$ или хотя бы до $|B|>\frac{|A|}{3}+m$ для какого-нибудь целого $m>0$ ?
_________________
.

Насколько помнится, эта задача из "Кванта", если не ошибаюсь от моего сокурсника Гриши Гальперина. В условии об А можно убрать слова "ненулевых целых". Когда то решал эту задачу, насколько помню максимальное возможное значение (гарантированное для любого А) мощности B есть $|B|=[\frac{|A|}{2}].$
Соответственно с "ненулевых" должно получится $|B|=[\frac{|A|+1}{2}].$

[maxal]

TOTAL писал(а):

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

Ну так может получиться решение $x+y=z$, где $x$ делится на $3$, а $y$ и $z$ дают один и тот же остаток при делении 3.

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

Руст, скорее всего, ты путаешь с какой-то другой задачей. Ну или приведи ссылку на Квант, или свое решение.

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

Хочу уточнить условие.

maxal писал(а):

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

Числа $x,y,z$ обязаны быть различными или это не обязательно?

[maxal]

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

Числа $x,y,z$ обязаны быть различными или это не обязательно?

Не обязаны. Возможно равенство $x=y$, например.

Добавлено спустя 11 минут:

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

Когда то решал эту задачу, насколько помню максимальное возможное значение (гарантированное для любого А) мощности B есть $|B|=[\frac{|A|}{2}].$

Вот пример множества, из которого нельзя выбрать половину элементов, не получив тройку $x+y=z$:

$$\{ 1,2,3,4,5,6,7,8,9,10,11,14,18,22 \}$$

[Руст]

Действительные числа можно привести к целым, заменив на достаточно большое число порядка $\frac{1}{min |a_i|\not =0}$. Отрицательные положительными переходя к модулям, так как $x+y=z$ эквивалентно $x=(-y)+z,-x-y=-z,....$ (так, что перенесением на другие стороны останутся только положительные).
Рассмотрим записи всех натуральных чисел $a_i$ в двоичной системе исчисления и выберем подмножество $B_i$, у которых в записи i-го бита 1 а i-1 бит 0 (если i=0 другого условия нет, так как i-1 бит после запятой и так равен 0). Очевидно, что множества $B_i$ удовлетворяют требуемым условиям. Легко доказать, что мощность хотя бы одного из $B_i$ не меньше n/2.
Вторая задача слишком тривиальная, что я даже не стану писать решение.

[maxal]

Рустем, ищи ошибку. Вот из этого множества нельзя выбрать бессуммную половину:

$$\{ 1,2,3,4,5,6,7,8,9,10,11,14,18,22 \}$$

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

P.S. А сложные задачки еще будут. Вот только с 1) разберемся
Хотя, на тебя, конечно, не угодишь

[worm2]

Думаю, что maxal и Руст решают разные задачи.
Очевидно, в постановке Руста запрещены тройки (x, y, z), где x = y:

Цитата:

...выберем подмножество $B_i$...

Т.о. $\{1, 3, 5, 7, 9, 11, 22\}$ --- решение задачи Руста, но не задачи maxalа (11+11=22).

[maxal]

Выше я уже явно ответил на вопрос Профессора Снэйпа о возможном равенстве $x=y$ - да, они могут быть равны!
Какие же тут могут быть разночтения?

[Руст]

Перебирать все подмножества из семи элементов (всего 3432) трудно. Но утверждение, что хотя бы одно из $B_i$ имеет мощность больше n/2 явно ошибочное. $B_i$ можно строит предварительно умножив каждое число на некоторое фиксированное. Кажется и это не даст половину. Проще в качестве $B_i(a)=\{a_j\in A|(a*a_j)_{x_i=1}\}$ рассмотреть числа, такие что i - ый бит в троичной записи $x_i$ равен 1.

[worm2]

Ну, например, вот ещё цитата, свидетельствующая о таком понимании задачи:

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

В условии об А можно убрать слова "ненулевых целых"...

Эта цитата появилась до того, как Вы уточнили.

[maxal]

Рустем, можно воспользоваться компом для проверки. Но в любом случае, поверьте мне на слово, что доказать оценку на относительный размер $B$ большую чем $\frac{1}{3}$ - это (как минимум) очень сложная задача. Поэтому предлагаю сосредоточится на базовой задаче 1).

А всякие обобщения на нецелые числа и т.п., безусловно, возможны, но они погоды не делают. Вся соль заключена именно в целочисленном варианте. Поэтому лучше пока не обобщать.

worm2, ну теперь-то разобрались - и ладно