Алгебраические методы

Если в каждом подмножестве из $\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$.

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

$n = 2$;

$n = 4$;

$n = 8$;

$n = 16$;

$n = 12$.

У матрицы Адамара любые два столбца ортогональны.

Матрица является матрицей Адамара тогда и только тогда, когда её элементы равны $\pm 1$ и любые две строки ортогональны.

Для матриц Адамара достигается верхняя оценка в теореме Адамара 7.2.1. (Название матрицы Адамара получили благодаря этому результату.)

Если существует матрица Адамара $n \times n$ и $n > 2$, то $n$ делится на $4$.

Докажите, что $S_{d}$ не зависит от $d \neq 0$.

Найдите $S_{d}$ для каждого $d \in \mathbb {Z}_{p}$.

$n = 2a$, если существует матрица Адамара $a \times a$;

$n = ab$, если существуют матрицы Адамара $a \times a$ и $b \times b$;

$n = p+1$, где $p$ — простое число вида $4k-1$;

$n = 2p+2$, где $p$ — простое число вида $4k+1$.

умножение строчки или столбца на $-1$;

перестановка строчек или столбцов местами.

Какие из матриц из задачи 7.2.6 эквивалентны?

Любая матрица Адамара эквивалентна некоторой нормализованной.