\documentclass[11pt,a4paper]{report}
\usepackage[a4paper, left=20mm, right=20mm, top=30mm, bottom=20mm]{geometry}
\usepackage{amsmath,amsfonts,amssymb,amsthm,epsfig,epstopdf, float, tikz, titling,url,array}
\usepackage[T2A,T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{xparse}
\usepackage[shortlabels]{enumitem}
\usepackage[]{algorithm2e}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=cyan,
}

\def\E{\mathbb{E}}
\def\Var{\mathrm{Var}}
\def\Cov{\mathrm{cov}}
\def\Corr{\mathrm{corr}}
\def\salg{\mathcal{F}}
\def\prob{\mathcal{P}}
\def\borel{\mathcal{B}}
\def\cantor{\mathcal{C}}

\def\eps{\varepsilon}
\def\Real{\mathbb{R}}
\def\Proj{\mathbb{P}}
\def\Hyper{\mathbb{H}}
\def\Integer{\mathbb{Z}}
\def\Natural{\mathbb{N}}
\def\Complex{\mathbb{C}}
\def\Rational{\mathbb{Q}}

\usepackage{stackengine,graphicx,amssymb}
\stackMath
\newcommand\frightarrow{\scalebox{1}[.3]{$\rule[.45ex]{2ex}{1.5pt}%
        \kern-.2ex{\blacktriangleright}$}}
\newcommand\darrow[1][]{\mathrel{\stackon[1pt]{\stackanchor[1pt]{\frightarrow}{\frightarrow}}{\scriptstyle#1}}}

\newcommand\independent{\protect\mathpalette{\protect\independenT}{\perp}}
\def\independenT#1#2{\mathrel{\rlap{$#1#2$}\mkern2mu{#1#2}}}
\renewcommand{\thesection}{\arabic{section}}

\theoremstyle{definition}
\newtheorem{task}{Задача}[section]
\newtheorem*{utask}{Задача}

\theoremstyle{definition}
\newtheorem{theorem}{Теорема}[section]
\newtheorem{lemma}{Лемма}[section]
\newtheorem{preposition}[section]{Утверждение}
\newtheorem*{corollary}{Следствие}

\theoremstyle{definition}
\newtheorem*{definition}{Определение}
\newtheorem{example}{Пример}[section]

\newcommand\mydots{\makebox[1em][c]{.\hfil.\hfil.}}
\renewcommand{\thesection}{\arabic{section}}

\begin{document}
    \setlength{\parindent}{1cm}
    \begin{utask}[6.2.14b]
        Пусть $ A_{1}, \dots, A_{n} $ — подмножества конечного множества $ M $, доля каждого из которых больше $\frac{7}{8} $. Пусть $ A_{1} $ независимо с $ A_{4} \cap A_{5} $. Тогда \[ |A_{1} \cap \ldots \cap A_{5}| > \frac{13}{16}\ |A_{2} \cap \ldots \cap A_{5}| \]
    \end{utask}
    \begin{proof}[Решение]
        Введём обозначение $ X_{k} := A_{k} \cap A_{k+1} \cap \ldots \cap A_{n} $.\\
        Докажем два вспомогательных утверждения.
        \begin{preposition}
            $ | X_{3} | > \frac{5}{6} |X_{4}| $.
        \end{preposition}
        \begin{proof} Имеем $  $
            $ |X_{4}| > \left (1 - \frac{2}{8}\right ) |M| = \frac{3}{4} |M| $ и
            $ | \overline{A_{3}} \cap X_{4} | <  | \overline{A_{3}} | < \frac{1}{8} |M| < \frac{1}{6} |X_{4}| $, откуда \[ |X_{3}| = |X_{4}| - |\overline{A_{3}} \cap X_{4}| > \frac{5}{6} |X_{4}| \].
        \end{proof}
        \begin{preposition}
            $ |\overline{A_{1}} \cap X_{4}| < \frac{3}{16} |X_{2}| $
        \end{preposition}
        \begin{proof}
            По задаче 6.2.14a имеем $ |X_{2}| > \frac{4}{5} |X_{3}| $. По утверждению 1 имеем $ |X_{3}| > \frac{5}{6} |X_{4}| $.\\
            Тогда, используя независимость $ A_{1} $ с $ X_{4} $, получаем оценку
            \[ |X_{2}| > \frac{4}{5} \cdot \frac{5}{6} | X_{4}| \ge \frac{4}{6} \cdot 8 |\overline{A_{1}} \cap X_{4}| = \frac{16}{3} |\overline{A_{1}} \cap X_{4}| \]
        \end{proof}
        \noindent Используя утверждение 2, получаем, что:
        \[ |X_{1}| = |X_{2}| - |\overline{A_{1}} \cap X_{2}| > |X_{2}| - |\overline{A_{1}} \cap X_{4}| > \left (1 - \frac{3}{16}\right ) |X_{2}| = \frac{13}{16} |X_{2}| \]
    \end{proof}
    \newpage
    \begin{utask}[14c]
        Пусть $\forall k \le n - 4: A_{k} $ независимо с $ A_{k+3} \cap \dots \cap A_{n} $, тогда $ A_{1} \cap \dots \cap A_{n} \neq \emptyset $.
    \end{utask}
    \begin{proof}[Решение]$  $\\
        \textbf{База индукции}: [14a, 14b] (отметим, что $ \frac{13}{16} > \frac{4}{5} $).\\
        \textbf{Предположение индукции}: $ X_{k+1} > \frac{4}{5} X_{k+2} $.\\
        \textbf{Шаг индукции}: $ X_{k} = X_{k+1} - \overline{A_{k}} X_{k+1} $.\\
        По предположению индукции и независимости $ \overline{A_{k}} $ с $ X_{k+3} $:
        \[ X_{k + 1} > \frac{4}{5} X_{k+2} > \left (\frac{4}{5}\right )^{2} X_{k+3} > \left (\frac{4}{5}\right )^{2} \cdot 8 \cdot \overline{A_{k}} X_{k+3} = \frac{128}{25} \overline{A_{k}} X_{k+3} \]
        т.е. $ \overline{A_{k}} X_{k+3} < \frac{25}{128} X_{k+1} $. Отсюда получаем:
        \[ X_{k} > X_{k+1} - \overline{A_{k}} X_{k+1} > X_{k+1} - \overline{A_{k}} X_{k+3} > \left (1 - \frac{25}{128}\right ) X_{k+1} = \frac{103}{128} X_{k+1} > \frac{4}{5} X_{k+1} \]
    \end{proof}
    \newpage
    \begin{utask}[6.2.18(a)]
        Даны число $ k \geqslant 10 $ и семейство $ k $-элементных подмножеств конечного множества $ M $. Если каждый элемент множества $ M $ содержится ровно в $ k $ подмножествах семейства, то существует раскраска множества $ M $ в два цвета, для которой каждое подмножество семейства содержит элементы обоих цветов (т.е. хроматическое число $ k $-однородного $ k $-регулярного гиперграфа равно двум при $ k\geqslant10 $).
    \end{utask}
    \begin{proof}
        Обозначим через $ S $ семейство $ k $-элементных подмножеств $ M $ из условия, через $ S_{x} $ — $ x $-ое из них, через $ A $ — множество всех раскрасок $ M $ в два цвета, через $ A_{x} $ — число таких из них, что подмножество $ S_{x} $ одноцветно. Всего раскрасок множества $ M $ — $ 2^n $ штук, где $ n := |M| $, откуда $ |A_{x}| = 2^{n-k+1} $. Тогда $ \frac{|A_{x}|}{|A|} = 2^{1-k} $.\\
        Теперь определим, со сколькими $ A_{y} $ зависимо каждое $ A_{x} $. Утверждается, что с теми и только с теми, с которыми есть пересечение по гиперребру. Поскольку каждый элемент лежит ровно в $ k $ множествах, получаем, что таких $ A_{y} $ не более $ k^2 $.\\
        Осталось только проверить, что $ A_{x} $ независимо от любого пересечения таких $ A_{y} $, что $ S_{x} \cap S_{y} = \emptyset $. Докажем, что это верно для любого $ r $:\\
        $ r = 2 $:
        \begin{gather*}
        S_{x} \cap S_{y} = \emptyset \implies A_{x} \independent A_{y}\\
        |A_{x}| = |A_{y}| = 2^{n-k+1},\ |A_{x} \cap A_{y}| = 2^{n - 2k + 2}\ (\text{т.к. } S_{x} \cap S_{y} = \emptyset)\\
        A_{x} \independent A_{y} \iff |A_{x} \cap A_{y}| |A| = |A_{x}| |A_{y}|\\
        |A_{x} \cap A_{y}||A| = 2^{2n-2k+2} = |A_{x}| |A_{y}|
        \end{gather*}
        $ r > 2 $: Докажем, что $ |A_{x} \cap A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| |A| = |A_{x}| |A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| $, т.е. что
        $$ |A_{x} \cap A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| = 2^{1-k} |A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| $$
        $ S_{x} \cap (S_{y_{1}} \cap \ldots \cap S_{y_{r+1}}) = \emptyset $, а значит можно отождествить все раскраски из $ A_{y_{1}} \cap \ldots \cap A_{y_{r+1}} $, которые совпадают на $ S_{x} $, а затем выбрать для $ S_{x} $ один из двух цветов, что соответствует умножению на $ 2^{1-k} $.
        Теперь можно заметить, что $ d \leqslant k^{2} $, применить ЛЛЛ в симметричной форме к $ \{\overline{A}_{x}\} $ и получить:
        $$ \frac{|\overline{A_{x}}|}{|A|} = 1 - \frac{|A_{x}|}{|A|} \geqslant 1 - \frac{1}{4d} $$
        Докажем более сильную оценку:
        \begin{gather*}
        \frac{|\overline{A_{x}}|}{|A|} = 1 - \frac{|A_{x}|}{|A|} \geqslant 1 - \frac{1}{4k^2} \geqslant 1 - \frac{1}{4d} \iff \frac{1}{4k^{2}} \geqslant \frac{|A_{x}|}{|A|} = \frac{1}{2^{k-1}}\\
        4k^{2} \leqslant 2^{k-1} \iff k^{2} \leqslant 2^{k-3} \text{ — верно } \forall k \geqslant 10
        \end{gather*}
        Значит пересечение множеств из $ \{\overline{A_{x}}\} $ непусто, т.е. существует раскраска, неодноцветная для каждого подмножества, что и требовалось доказать.
    \end{proof}
    \newpage
    \begin{utask}[6.2.22(a)]
        Если $ X \subset \Real $ — конечное множество и $ m, r > 1 $ — целые числа, для которых $ 4rm(m-1)\left (1 - \frac{1}{r}\right )^{m} < 1 $, то для любого $ m $-элементного подмножества $ M \subset \Real $ существует раскраска множества $ \Real $ в $ r $ цветов такая, что для любого $ x \in X $ множество $ x + M $ содержит точки каждого из $ r $ цветов.
    \end{utask}
    \begin{proof}
        Распишем только ту часть, которая про независимость от пересечений.\\
        Введём обозначения: $ A_{x} $ — множество всех раскрасок, при которых $ x + M $ не радужно.\\
        Тогда $$ \frac{|A_{x}|}{|A|} = r \left(\frac{r-1}{r}\right)^{m} $$
        \textbf{Утверждение:} $ A_{x} $ зависимо только с теми $ A_{y} $, при которых $ (x + M) \cap (y + M) \neq \emptyset $.\\
        Заметим, что здесь рассуждение \textbf{абсолютно такое же} как и в прошлой задаче, нужно только рассматривать в качестве объемлющего множества конечное $ X + M\ (n := |X + M|)  $ и его раскраски.
        \begin{itemize}
            \item \textbf{База}: $ (x + M) \cap (y + M) = \emptyset \implies A_{x} \independent A_{y} $.
            \begin{gather*}
            |A_{x}| = |A_{y}| = r^{n-m+1} (r-1)^{m},\ |A_{x} \cap A_{y}| = r^{n-2m+2}(r-1)^{2m}\ (\text{т.к. } (x + M) \cap (y + M) = \emptyset)\\
            A_{x} \independent A_{y} \iff |A_{x} \cap A_{y}| |A| = |A_{x}| |A_{y}|\\
            |A_{x} \cap A_{y}||A| = r^{2n-2m+2} (r-1)^{2m}  = |A_{x}| |A_{y}|
            \end{gather*}
            \item \textbf{Шаг}: Докажем, что $ |A_{x} \cap A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| |A| = |A_{x}| |A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| $, т.е. что
            $$ |A_{x} \cap A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| = r \left(\frac{r-1}{r}\right)^{m} |A_{y_{1}} \cap \ldots \cap A_{y_{r+1}}| $$
            Но это почти очевидно, поскольку $ (x + M) \cap ((y_{1} + M) \cap \ldots \cap (y_{r+1} + M)) = \emptyset $, а значит нужно отождествить все раскраски из $ A_{y_{1}} \cap \ldots \cap A_{y_{r+1}} $, которые совпадают на $ (x + M) $, а затем выбрать для $ (x + M) $ всеми возможными способами $(r-1)$ цветов.
        \end{itemize}
        Теперь, пользуясь тем, что $ d \leqslant m(m-1) $, можно применить ЛЛЛ к $ \{A_{x}\} $, свести к данному в условии неравенству и получить существование раскраски, разноцветной для всех $ x+M $.
    \end{proof}
    \begin{utask}
        $ W(2, k) > \frac{2^{k}(k-1)}{8k^2} $.
    \end{utask}
    \begin{proof}
        Пусть $ P $ — множество прогрессий длины $ k $ из множества $ \mathcal{R}_{W(2, k)} $, $ P_{x} $ —  $ x $-ая из них. $ A_{x} $ — множество тех раскрасок, при которых $ P_{x} $ одноцветна.\\
        Каждая прогрессия независима с пересечением любого семейства тех, с которыми не имеет общих элементов:
        Доказательство дословно такое же, как прежде, даже $ \frac{|A_{x}|}{|A|} = 2^{1-k} $\\
        Каждая $ k $-прогрессия пересекается не более чем с $ k^2 \frac{n}{k-1} $ другими, т.е. $ d < k^2 \frac{n}{k-1} $ (выбираем в первой прогрессии элемент, во второй — элемент и шаг).\\
        Отсюда из ЛЛЛ выводится нижняя оценка на $ n $.
    \end{proof}
    \newpage
    \begin{utask}[5.2.4(b*)]
        При данных $ n, k $ найти наибольшее $ s $, для которого найдётся $ (n, s, k) $ набор, имеющий ровно две минимальные с.о.п.
    \end{utask}
    \begin{proof}[Решение]$  $\\
        \textbf{Ответ}: $ s = {n\choose{k}} - 2 $\\
        Заметим для начала, что $ s < {n\choose{k}} - 1 $, поскольку $ \forall S \in {{\mathcal{R}_{n}}\choose{k}}: M := {{\mathcal{R}_{n}}\choose{k}} \setminus S$ имеет с.о.п. $ \mathcal{R}_{n} \setminus S $ мощности $ n-k $, причём это единственная с.о.п. такого размера (любая с.о.п. $ \sigma: |\sigma| \leqslant n-k $ не покрывает всякое $ k $-элементное подмножество из $ \mathcal{R}_{n}\setminus \sigma $).\\
        Приведём явную конструкцию: рассмотрим $ M := {{\mathcal{R}_{n}}\choose{k}} \setminus (\{1, 2, \ldots, k-1, k\} \cup \{1, 2, \ldots, k-1, k+1 \}) $.\\
        Утверждается, что у $ M $ всего две различные минимальные с.о.п.:
        $$ \sigma_{k} := \{k, k+2, k+3, \ldots, n\} \text{ и } \sigma_{k+1} := \{k+1, k+2, \ldots, n\} $$ Это действительно с.о.п., т.к. $ \mathcal{R}_{n} \setminus \sigma_{k} \not \in M,\ \mathcal{R}_{n} \setminus \sigma_{k+1} \not \in M $. Также размер всякой с.о.п. $ \sigma $ в $ M $ не меньше $ n-k $, поскольку иначе в $ \mathcal{R}_{n} \setminus \sigma $ можно выбрать $ k $-элементное подмножество, не пересекающееся с $ \sigma $.\\
        Докажем, что других с.о.п. нет. Пусть $ \sigma := \{a_{1}, \ldots, a_{n-k}\} $ — какая-то минимальная с.о.п. Тогда если $ \mathcal{R}_{n}\setminus \sigma  \in M $, то $ \sigma $ — не с.о.п., значит $ \sigma = \{k, k+2, \ldots, n \} $ либо $ \sigma = \{k+1, k+2, \ldots, n \} $.\\
    \end{proof}
    \newpage
    \begin{utask}[5.8.3(a)]
        При каком условии на двудольный граф можно разбить правую долю на две части таким образом, чтобы с каждой из этих долей существовало паросочетание, вовлекающее все вершины левой доли?
    \end{utask}
    \begin{proof}[Решение]
        \textbf{Ответ}: $ \forall L' \subset L: |N(L')| \geqslant 2|L'| $.\\
        \textbf{Доказательство}: Индукция по $ n := |L| $.
        \begin{itemize}
            \item \textbf{База}: $ n = 1 $ — тривиально.
            \item \textbf{Шаг}: $ n > 1 $.
            \begin{enumerate}
                \item $ \forall L' \subset L: |N(L')| > 2(|L'| + 1) $:\\
                Произвольную $ v \in L $ соединим рёбрами с произвольной парой соседей и вычеркнем вместе с ними, тогда в правой доле останется $ |N(L)| - 2 $ вершин. По условию $ |N(L \setminus \{v\})|> 2|L \setminus \{v\}| + 2 $, откуда следует, что к $ |L \setminus \{v\}| $ применимо п.и.
                \item $ \exists L' \subsetneq L: |N(L')| = 2|L'| + 1 $:\\
                Произвольным образом составим гарем для $ L' $. Осталось доказать, что к $ G(L'', N(L'') \setminus N(L')) $, где $ L'' := L \setminus L' $ применимо п.и. По условию $$ |N(L)| = |N(L')| + |N(L'') \setminus N(L')| = 2|L'| + 1 + |N(L'') \setminus N(L')| > 2|L'| + 2|L''| $$
                Отсюда получаем, что $ |N(L'') \setminus N(L')| \geqslant 2|L''| $, ч.т.д.
                \item $ \exists L' \subsetneq L: |N(L')| = 2|L'| $:
                произвольным образом составим гарем для $ L' $. Осталось доказать, что к $ G(L'', N(L'') \setminus N(L')) $, где $ L'' := L \setminus L' $ применимо п.и. По условию $$ |N(L)| = |N(L')| + |N(L'') \setminus N(L')| = 2|L'| + |N(L'') \setminus N(L')| > 2|L'| + 2|L''| $$
                Отсюда получаем, что $ |N(L'') \setminus N(L')| \geqslant 2|L''|+1 $, ч.т.д.
            \end{enumerate}
        \end{itemize}
    \end{proof}
    \begin{utask}[5.2.6(e)]
        Для всех достаточно больших $ n $ и $ k $ если $ \ln\ln k < \ln \frac{sk}{n} < \sqrt{k} < \sqrt[4]{n} $, то найдётся $ (n, s, k) $-набор, размер любой с.о.п. которого больше $ 0.99 \frac{n}{k} \ln\frac{sk}{n} $.
    \end{utask}
    \begin{proof}[Решение]
        Разберёмся с проблемной оценкой $ \frac{ {{n}\choose{k}} }{ {{n-l}\choose{k}} } < C e^{\frac{kl}{n}} $, где $ C > 0 $ — некоторая константа.\\
        \begin{gather*}
        \frac{ {{n}\choose{k}} }{ {{n-l}\choose{k}} } = \frac{ n! }{ k!(n-k)! } \frac{k! (n-k-l)!}{(n-l)!} = \frac{n}{n-l} \frac{n-1}{n-l-1} \ldots \frac{n-k+1}{n-l-k+1} =\\
        = \left (1 + \frac{l}{n-l}\right ) \left (1 + \frac{l}{n-l-1}\right ) \ldots \left (1 + \frac{l}{n-l-k+1}\right ) < \left (1 + \frac{l}{n-l}\right )^{k} < e^{\frac{kl}{n-l}} \overset{(
            *)}{<}\\
        < e^{\frac{kl}{n} + 2\frac{kl^2}{n^2}} \overset{(**)}{\leqslant} e^{\frac{kl}{n}+2} < 9 e^{\frac{kl}{n}}\\ (\ast) \text{ верно, т.к. } \frac{1}{n-l} < \frac{n+2l}{n^2} = \frac{1}{n} + \frac{2l}{n^2},\\
        \text{ поскольку } (n + 2l)(n - l) - n^2 = n^2 + nl - 2l^2 - n^2 = nl\left (1 - \frac{2l}{n}\right ) >\\> nl\left ( 1 - 2\frac{\frac{n}{k}\ln{\frac{sk}{n}}}{n} \right ) = nl\left ( 1 - 2\frac{\ln{\frac{sk}{n}}}{k} \right ) > nl\left ( 1 - \frac{2}{\sqrt{k}} \right ) > 0 \text{ при } k > 4, \\
        (\ast\ast) \text{ также верно, поскольку }
        \frac{kl^2}{n^2} \leqslant \frac{k \frac{n^2}{k^2}\ln^{2} \frac{sk}{n} }{n^2}   \leqslant 1, \text{ т.к. } \ln\frac{sk}{n} \leqslant \sqrt{k}.
        \end{gather*}
        Остальные шаги доказательства в книжке корректны, а другая константа ни на что не влияет.
    \end{proof}
    \newpage
    \graphicspath{ {~/Desktop/Homeworks/Semester 4/Дискран/} }
    \begin{utask}[4.4.2]
        При любой раскраске плоскости в три цвета найдутся две точки одного цвета на расстоянии 1.
    \end{utask}
    \begin{proof}
        Будем раскрашивать плоскость в красный, зелёный и синий цвета.\\
        Рассмотрим некоторую точку $ O $, раскрашенную, без ограничения общности, в красный цвет. Рассмотрим окружность радиуса $ \sqrt{3} $ с центром в точке O. Возможны два случая:
        \begin{enumerate}
            \item Все точки окружности красные. Тогда любая хорда длины 1 даёт пару одноцветных точек.
            \item На окружности есть синие или зелёные точки.
            Выберем любую такую точку и обозначим её через $ O' $. Без ограничения общности, будем считать, что она окрашена в синий цвет. Рассмотрим ромб $ OAO'A' $ со стороной 1, такой что $ \angle AOA' = \frac{\pi}{3} $ (см. рисунок). Тогда $ AOA' $ и $ AO'A' $ — равносторонние треугольники со стороной 1. Нетрудно заметить, что при любой раскраске точек $ A $ и $ A' $ один из этих треугольников содержит одноцветную пару вершин.
            \begin{figure}[H]
                \centerline{\includegraphics[scale=0.45]{ipr_geom.png}}
            \end{figure}
        \end{enumerate}
    \end{proof}
    \newpage
    \begin{utask}[7.2.3d]
        Если существует матрица Адамара $n \times n$ и $ n > 2 $, то $ n $ делится на 4.
    \end{utask}
    \begin{proof}
        Обозначим через $ H  $ матрицу Адамара из условия. Не ограничивая общности, будем считать, что матрица $ H $ нормализованная. Рассмотрим подматрицу
        $ T $ из трёх первых строк матрицы $ H $. Покажем, что уже из условия ортогональности её строк будет следовать, что $ n $ делится на 4. Обозначим через $ x, y, z $ и $ t $ количество столбцов матрицы $ T $ вида $ (1, -1, -1)^T,\ (1, -1, 1)^T\ (1, 1, -1)^T$ и $ (1, 1, 1)^T $ соответственно. Заметим, что других нет. Выражая теперь через $ x, y, z, t $ условия ортогональности строк матрицы $ T $, получим систему:\\
        $$ \begin{cases}
        x + y + z + t &= n,\\
        -x - y + z + t &= 0,\\
        -x + y - z + t &= 0,\\
        x - y -z + t &= 0;
        \end{cases} $$
        Сложив все уравнения системы, получаем $ 4t = n $, откуда следует, что $ n $ делится на 4.
    \end{proof}
\end{document}