2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 пересечения из нечетного числа элементов (комбинаторика)
Сообщение08.07.2008, 12:50 


04/10/05
272
ВМиК МГУ
Множество $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}$, пересекающее данное множество по нечётному числу элементов.

 Профиль  
                  
 
 
Сообщение08.07.2008, 20:47 
Модератор
Аватара пользователя


11/01/06
5660
Странная задача.

Случай нечетного числа элементов в подмножества легко решается из соображений четности: достаточно зафиксировать любое $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)$-периодическое множество обязательно найдется.

 Профиль  
                  
 
 
Сообщение08.07.2008, 20:59 


04/10/05
272
ВМиК МГУ
Всё правильно (в идейном плане, в подробности не вникал). Самое основное здесь - как раз догадаться, что надо доказывать про 1 элемент. А то, что в условии сказано про нечётность, может навести на ложный путь - использование линейной алгебры.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group