Линейно-алгебраический метод в комбинаторике

Если в каждом подмножестве из $\mathscr {F}$ нечётное число элементов, а в пересечении любых двух подмножеств из $\mathscr {F}$ чётное число элементов, то $\left|\mathscr {F}\right| \leq n$.

Постройте пример, когда эта оценка достигается.

Если в пересечении любых двух подмножеств из $\mathscr {F}$ ровно $q$ элементов и в каждом подмножестве из $\mathscr {F}$ более $q$ элементов, то $\left|\mathscr {F}\right| \leq n$.

Если $q > 0$ и в пересечении любых двух подмножеств из $\mathscr {F}$ ровно $q$ элементов, то $\left|\mathscr {F}\right| \leq n$.

Существуют $2^{k}$ подмножеств $2k$-элементного множества, в каждом из которых чётное число элементов и в пересечении любых двух из которых чётное число элементов.

Больше чем $2^{k}$ подмножеств в условиях п. (1) быть не может.

Наибольшее число точек в $\mathbb {R}^{n}$ с равными попарными расстояниями равно $n+1$.

Постройте $\dfrac {n(n-1)}{2}$ точек в $\mathbb {R}^{n}$, попарные расстояния между которыми принимают только два различных значения.

Для $a \in \mathbb {R}$ и точек $v = (v_{1}, \ldots , v_{n}) \in \mathbb {R}^{n}$, $x = (x_{1}, \ldots , x_{n}) \in \mathbb {R}^{n}$ обозначим $P_{v}(x) := \left|x-v\right|^{2} - a^{2}$. Если попарные расстояния между $k$ точками $u_{1}, \ldots , u_{k} \in \mathbb {R}^{n}$ равны $a$, то многочлены $P_{u_{1}}, \ldots , P_{u_{k}}$ линейно независимы над $\mathbb {Q}$.

Если попарные расстояния между $k$ точками в $\mathbb {R}^{n}$ принимают только два различных значения, то $k \leq \dfrac {(n+1)(n+4)}{2}$.

Среди любых $327$ попарно пересекающихся $9$-элементных подмножеств $25$-элементного множества найдутся два подмножества, в пересечении которых ровно $3$ или ровно $6$ элементов.

Среди любых $327$ точек в $V_{25,9}$ есть две, скалярное произведение которых лежит в $\left\{ 0,3,6\right\}$.

Для любого $\overrightarrow {a} \in V_{25,9}$ раскроем скобки в произведении

где $x_{1}, x_{2}, \ldots , x_{25}$ — переменные. С каждым из полученных одночленов проведём следующую операцию: для каждого $i$, если в одночлене есть множитель $x_{i}^{2}$, заменим этот множитель на $1$. Полученный многочлен обозначим $F_{\overrightarrow {a}}(x_{1}, \ldots , x_{25})$. Докажите, что если скалярное произведение никаких двух векторов среди $\overrightarrow {a}_{1}, \ldots , \overrightarrow {a}_{s} \in V_{25,9}$ не делится на $3$, то многочлены $F_{\overrightarrow {a}_{1}}, \ldots , F_{\overrightarrow {a}_{s}}$ линейно независимы над $\mathbb {Q}$.

Укажите $326$ многочленов, линейными комбинациями которых с рациональными коэффициентами можно получить каждый многочлен $F_{\overrightarrow {a}}$, $\overrightarrow {a} \in V_{25,9}$.

Среди любых $107$ пятиэлементных подмножеств $14$-элементного множества найдутся два подмножества, в пересечении которых ровно $2$ элемента.

То же для $93$ подмножеств.

То же для $92$ подмножеств.

Невозможно раскрасить в $21$ цвет все пятиэлементные подмножества $14$-элементного множества так, чтобы любые два пятиэлементных подмножества, пересекающиеся ровно по двум элементам, были разноцветны.

Для простого $p$ и целого $t$ число $G(t) := (t-1)(t-2)\ldots (t-p+1)$ делится на $p$ тогда и только тогда, когда $t$ не делится на $p$.

Пусть $p$ простое и $n = 4p$. Обозначим

Обозначим $G(t) := (t-1)(t-2)\ldots (t-p+1)$. Для любого $\overrightarrow {a} \in M$ раскроем скобки в произведении $G(\overrightarrow {a} \cdot (1, x_{2}, \ldots , x_{n}))$, где $x_{2}, \ldots , x_{n}$ — переменные. В каждом из полученных одночленов для каждого $i$ будем заменять $x_{i}^{2}$ на $1$, пока это возможно. Полученный многочлен обозначим $F_{\overrightarrow {a}}(x_{2}, \ldots , x_{n})$.

Докажите, что если скалярное произведение никаких векторов среди $\overrightarrow {a}_{1}, \ldots , \overrightarrow {a}_{s} \in M$ не равно нулю, то многочлены $F_{\overrightarrow {a}_{1}}, \ldots , F_{\overrightarrow {a}_{s}}$ линейно независимы над $\mathbb {Q}$.

Существуют $n$ и ограниченное подмножество в $\mathbb {R}^{n}$, которое невозможно разбить на $n+1$ непустых частей меньшего диаметра.

Если $t$ простое, то среди любых $1 + \sum \limits_{j=0}^{t-1} \dbinom {n}{j}$ различных подмножеств $n$-элементного множества, в каждом из которых $k$ элементов, найдутся два подмножества, число элементов в пересечении которых делится на $t$.

То же, только задано целое $q$ и «делится на $t$» заменено на «сравнимо с $q$ по модулю $t$».

Если множество рёбер графа $K_{n}$ является объединением множеств рёбер $s$ полных двудольных графов, не пересекающихся по рёбрам, то $s \geq n-1$.

Постройте набор двудольных графов, на котором эта оценка достигается.