Независимость и доказательства существования

По каждому из 100 видов работ в фирме имеется ровно 8 специалистов. Сотрудник может быть специалистом по нескольким видам работ; распределение специалистов по видам работ известно тому, кто назначает выходные. Каждому сотруднику нужно дать выходной в субботу или в воскресенье. Докажите, что это можно сделать так, чтобы и в субботу, и в воскресенье для каждого вида работ на работе был специалист по нему. (Это задача 1.6.7.)

По каждому из нескольких видов работ в фирме имеется ровно 8 специалистов. (Теперь видов работ не обязательно 100.) Каждый вид работ имеет общих специалистов не более чем с 30 другими видами. Каждому сотруднику нужно дать выходной в субботу или в воскресенье. Докажите, что это можно сделать так, чтобы и в субботу, и в воскресенье для каждого вида работ на работе был специалист по нему.

По кругу стоит 200 студентов из 10 групп, в каждой из которых 20 студентов. Докажите, что можно в каждой группе выбрать по старосте так, чтобы никакие два старосты не стояли рядом.

То же для 1600 студентов из 100 групп, в каждой из которых 16 студентов.

Докажите, что можно раскрасить первые 8 натуральных чисел в 2 цвета так, чтобы не было одноцветной арифметической прогрессии длины 3.

Докажите, что можно раскрасить первые 15 миллионов натуральных чисел в 2 цвета так, чтобы не было одноцветной арифметической прогрессии длины 32.

Докажите, что для любого $M \in \mathbb {R}$ можно так раскрасить все вещественные числа в 2 цвета, чтобы для любого $x \in \mathbb {R}$ числа $x$ и $x+M$ были разных цветов.

Докажите, что для любых различных 25 чисел $M_1,\ldots ,M_{25} \in \mathbb {R}$ можно раскрасить все вещественные числа в 3 цвета так, чтобы для любого $x \in \mathbb {R}$ среди чисел $x+M_1,\ldots ,x+M_{25}$ были числа каждого из трёх цветов.

В множестве всех клеток шахматной доски подмножество клеток в первых трёх её строках с подмножеством клеток в последних четырёх её столбцах.

Подмножества $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4\right\}$ и $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4\right\}$.

Подмножества $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4,5,6\right\}$ и $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4,5,6\right\}$.

Подмножество чисел, делящихся на 5, и подмножество чисел, делящихся на 7.

Подмножество чисел, делящихся на 15, и подмножество чисел, делящихся на 21.

Подмножество чисел, делящихся на 15, и подмножество чисел, делящихся на 5.

Подмножество чисел, делящихся на 10, и подмножество чисел, делящихся на 7.

Подмножество раскрасок, для которых $\left\{ 1,2,\ldots ,8\right\}$ одноцветно, и подмножество раскрасок, для которых $\left\{ 11,12,\ldots ,18\right\}$ одноцветно.

Подмножество раскрасок, для которых $\left\{ 1,2,\ldots ,8\right\}$ неодноцветно, и подмножество раскрасок, для которых $\left\{ 11,12,\ldots ,18\right\}$ неодноцветно (ср. с задачей 6.2.1 (2)).

Подмножество раскрасок, для которых $\left\{ 1,2,\ldots ,8\right\}$ одноцветно, и подмножество раскрасок, для которых $\left\{ 6,7,\ldots ,13\right\}$ одноцветно.

Обязательно ли найдётся богатый здоровый умный горожанин, если в городе доля богатых горожан больше $\dfrac {2}{3}$, доля здоровых больше $\dfrac {2}{3}$ и доля умных больше $\dfrac {2}{3}$?

Тот же вопрос, если в городе есть богатый горожанин, есть здоровый горожанин и есть умный горожанин, богатство, здоровье и ум попарно независимы, и доля богатых здоровых умных среди богатых здоровых такая же, как и доля умных среди всех жителей. (Вместе с условием попарной независимости последнее называется независимостью в совокупности.)

Тот же вопрос, если в городе богатых горожан больше половины, здоровых больше половины, умных больше половины, богатство и ум независимы, здоровье и ум независимы.

Пусть $A_1,A_2,A_3,A_4$ — подмножества 720-элементного множества, в каждом из которых более 480 элементов. Если $A_k$ и $A_{k+1}$ независимы для любого $k=1,2,3$, то $A_1\cap A_2\cap A_3\cap A_4 \neq \emptyset$.

Пусть $n \geqslant 2$ и $A_1,A_2,\ldots ,A_n$ — подмножества конечного множества, доля каждого из которых больше $1-\dfrac {1}{n-1}$. Если $A_k$ и $A_{k+1}$ независимы для любого $k=1,2,\ldots ,n-1$, то $A_1\cap A_2\cap \ldots \cap A_n \neq \emptyset$.

попарно независимых, но для которых $A$ не является независимым от набора $B_1, B_2$;

не являющихся попарно независимыми, но для которых $A$ независимо от набора $B_1, B_2$.

Локальная лемма Ловаса в симметричной форме. Пусть $A_1,\ldots ,A_n$ — подмножества конечного множества. Если для некоторого $d$ и любого $k$ доля подмножества $A_k$ не меньше $1-\dfrac {1}{4d}$ и существует набор из не менее чем $n-d$ подмножеств $A_j$, от которого $A_k$ не зависит, то $A_1\cap \ldots \cap A_n \neq \emptyset$.

При $d > 2$ утверждение п. (1) верно, если заменить $1-\dfrac {1}{4d}$ на $1-\dfrac {1}{e(d+1)}$.

Если $a_k=1$ при любом $k\leqslant 0$ и для некоторого $d\geqslant 2$ выполнено $a_{k+1}\geqslant a_k-\dfrac {a_{k-d}}{4d}$ при любом $k\geqslant 0$, то $a_k > 0$ при любом $k$.

$k \geqslant 10$;

$k=9$

Для любого разбиения множества вершин цикла длины $16n$ на $n$ множеств по 16 вершин можно выбрать по вершине из каждого множества так, что между выбранными $n$ вершинами нет рёбер.

То же для $11n$ вершин.

В графе степень каждой вершины не превосходит $\Delta$. Все вершины раскрашены в $r$ цветов. Вершин каждого цвета не менее $2e\Delta +1$. Тогда можно выбрать $r$ вершин разных цветов, никакие две из которых не соединены ребром.

Каждую $k$-элементную арифметическую прогрессию в $\left\{ 1,2,\ldots ,n\right\}$ пересекает не более $k^2\left[\dfrac {n}{k-1}\right]$ других таких прогрессий.

Для любого натурального $k$ существует раскраска первых $\left[\dfrac {2^{k-3}(k-1)}{k^2}\right]$ натуральных чисел в 2 цвета, для которой нет одноцветной $k$-элементной арифметической прогрессии.

Каждую $k$-элементную арифметическую прогрессию в $\left\{ 1,2,\ldots ,n\right\}$ пересекает не более $nk$ других таких прогрессий.

Для любого натурального $k$ существует раскраска первых $\left[\dfrac {2^{k-3}}{k}\right]$ натуральных чисел в 2 цвета, для которой нет одноцветной $k$-элементной арифметической прогрессии.

Если $X\subset \mathbb {R}$ — конечное множество и $m,r$ — натуральные числа, для которых $4rm(m-1)\left(1-\dfrac {1}{r}\right)^m < 1$, то для любого $m$-элементного подмножества $M\subset \mathbb {R}$ существует раскраска множества $\mathbb {R}$ в $r$ цветов такая, что для любого $x\in X$ множество $x+M := \left\{ x+a : a\in M\right\}$ содержит точки каждого из $r$ цветов.

То же для $X=\mathbb {Z}$.

То же для $X=\mathbb {R}$.

Если $\dbinom {n}{2}\dbinom {k}{n-2}+1 < 2^{\binom {n}{2}-1}/e$, то $R(n,n) > k$, где $R(n,n)$ — число Рамсея (п. 4.1).

$R(n,n) \gtrsim \sqrt{2}e^{-1}n2^{n/2}$. (Ср. с задачей 4.1.5.)

Локальная лемма Ловаса. *Пусть $A_1,\ldots ,A_n$ — подмножества конечного множества, $J_1,\ldots ,J_n\subset \left\{ 1,\ldots ,n\right\}$ и $\gamma_1,\ldots ,\gamma_n\in (0,1)$. Пусть также для любого $k$

• доля подмножества $A_k$ не меньше $1-(1-\gamma_k)\displaystyle \prod_{j\notin J_k}\gamma_j$;

• множество $A_k$ не зависит от набора $\left\{ A_j : j\in J_k\right\}$.

Тогда доля пересечения $\displaystyle \bigcap_{k=1}^{n}A_k$ не меньше $\displaystyle \prod_{k=1}^{n}\gamma_k > 0$.*

Существует такое $c>0$, что $R(3,n) > cn\sqrt{n}$ для любого $n$.