ФРГ 1982

[krainik]

Нека [tex]\mathbb{A}=\{1,2,...,2n+1\}[/tex] и нека [tex]B\subset A[/tex] e такова множество, че не съществуват [tex]x,y,z\in B[/tex], такива че [tex]x+y=z[/tex]. Да се намери [tex]max|B|(|B|\equiv #B[/tex]).

[Реклама]

[Saposto_MM]

Очевидно може да имаме [tex]\|B\|=n+1[/tex] - взимаме [tex]B=\{1,3,\ldots,2n+1\}[/tex].
Сега ще докажем, че [tex]\|B\|=n+2[/tex] е невъзможно!
Нека [tex]a[/tex] е най-големият елемент на [tex]B[/tex]. Образуваме всички разлики на [tex]a[/tex], с другите елементи от [tex]B[/tex]. Получаваме общо [tex]n+1[/tex] различни числа. Но знаем, че числата вън от [tex]B[/tex] са [tex]n-1[/tex]. Тези [tex]n-1[/tex] ще покриват [tex]n-1[/tex] числа от получените [tex]n+1[/tex] разлики. Остават две непокрити числа и значи те ще са в множеството [tex]B[/tex]. Но тези две разлики, които ще са в множеството [tex]B[/tex] са разлики на числа от същото множество. Ако [tex]a[/tex] е четно една от тези разлики ще е [tex]a-\frac{a}{2}[/tex]. Другата разлика обаче ще е от вида [tex]a-b[/tex], където [tex]b\in B[/tex] и [tex]b\ne \frac{a}{2}[/tex]. Значи в [tex]B[/tex] ще имаме три различни числа [tex]a[/tex], [tex]b[/tex] и [tex]a-b[/tex], като очевидно сбора на [tex]b[/tex] и [tex]a-b[/tex] дава [tex]a[/tex], което е противоречие със свойствата на множеството [tex]B[/tex]. Когато [tex]a[/tex] е нечетно нещата са аналогични като нямаме проблема с [tex]a-\frac{a}{2}[/tex].