пересечения из нечетного числа элементов (комбинаторика)

[маткиб]

Множество $A$ будем называть $(n,T)$-периодическим, если
$A=\{i\in\mathbb{N}:\ 1\leq i\leq n,\ i\equiv b\mod T\}$
для некоторого $b$.

Доказать, что при любом достаточно большом натуральном $n$ для любого подмножества $\{1,\ldots,n\}$, состоящего из не более, чем $n^{1/3}$ элементов, существует $(n,T)$-периодическое множество, $T\leq n^{1/2}$, пересекающее данное множество по нечётному числу элементов.

[maxal]

Странная задача.

Случай нечетного числа элементов в подмножества легко решается из соображений четности: достаточно зафиксировать любое $T\leq \sqrt{n}$ и пробежаться по всем различным $b$. Понятно, что $(n,T)$-периодические множества $A_{n,T,b_1}$ и $A_{n,T,b_2}$ дизъюнктны при $b_1\not\equiv b_2\pmod{T}$, и в то же время семейство $\left\{A_{n,T,b}\right\}_{b=0}^{T-1}$ покрывает все множество $\{1,\ldots,n\}.$ Поэтому одно из $A_{n,T,b}$ обязано пересекаться с выбранным подмножеством по нечетному числу элементов.

В общем же случае можно доказать большее - а именно, что для выбранного подмножества найдется $(n,T)$-периодическое множество, пересекающееся с выбранным подмножеством ровно по одному элементу. Доказательство от противного:
Предположим для некоторого выбранного подмножества $X\subset\{1,\ldots,n\}$ искомого $(n,T)$-периодического множества не существует. Пусть $x\in X$ - произвольный фиксированный элемент. Тогда каждое из чисел $T=1,2,\dots,\lfloor n^{1/2}\rfloor$ является делителем разности $y-x$ для некоторого $y\in X$, $y\ne x$, так как в противном случае $A_{n,T,x}$ дает искомое $(n,T)$-периодическое множество (причем $A_{n,T,x}\cap X=\{ x\}$). Отсюда немедленно следует оценка

$$\pi(n^{1/2})-\pi(n^{1/3})\leq 2|X| \leq 2 n^{1/3},$$

так как простые числа в интервале $(n^{1/3},n^{1/2})$ могут делить одну и ту же разность максимум вдвоем (то есть никакие три простых из этого интервала не могут делить одну и ту же разность). Из этой оценки получается другая оценка:

$$\pi(n^{1/2})\leq 2 n^{1/3} + \pi(n^{1/3}) \leq 3 n^{1/3},$$

которая, очевидно, не может выполняться для бесконечно большого числа различных $n$, что противоречило бы основной теореме о распределении простых. Полученное противоречие доказывает, что начиная с некоторого $n$, искомое $(n,T)$-периодическое множество обязательно найдется.

[маткиб]

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

Эта задача - вариация на тему леммы Вэлианта-Вазирани (L. G. Valiant, V. V. Vazirani, "NP is as easy as detecting unique solutions").