Reorganize & alg-1

6 files changed, 590 insertions, 0 deletions

diff --git a/dm/dm-14.tex b/dm/dm-14.tex
new file mode 100644
index 0000000..313e693
--- /dev/null
+++ b/dm/dm-14.tex
@@ -0,0 +1,113 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-14 (\texttt{cw14\_plus})}
+\title{Дискретная математика 14}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\twocolumn
+\begin{center} \textbf{1} \end{center}
+
+    По условию, $\expected{\textrm{prize}} = 40$
+    Значит,
+    \[
+        \expected{\text{prize} \geqslant 5000} \leqslant \frac{40}{5000} < 0.01
+    \]
+
+    \qed
+
+\begin{center} \textbf{2} \end{center}
+
+    \begin{align*}
+        \expected{X} =
+        \sum_{x \in \Omega} p(x) f(x) =\\
+        \sum_{f(x) \geqslant 5} p(x) f(x) + \sum_{f(x) < 5} p(x) f(x) \geqslant\\
+        \sum_{f(x) \geqslant 5} p(x) f(x) \geqslant
+        \sum_{f(x) \geqslant 5} p(x) 5 =\\
+        5\sum_{f(x) \geqslant 5} p(x) =
+        5\ \frac{1}{2} = 2.5
+    \end{align*}
+
+    Для любого $ 2.5 \leqslant Y < \infty $ матожидание $f_Y$ равно $Y$, если:
+
+    \begin{align*}
+        \Omega &= \{1, 2\} \\
+        f_Y (1) &= 0 \\
+        f_Y (2) &= 2Y \\
+        p_Y (1) &= \frac{1}{2} \\
+        p_Y (2) &= \frac{1}{2} \\
+    \end{align*}
+
+
+\begin{center} \textbf{3} \end{center}
+    Обозначим выбор чисел как двоичное число размера 30.
+    Тогда почти к каждому слову есть другое, симметричное,
+    то есть для почти каждого выбора $C$ 10 чисел есть симметричный выбор $C'$.
+    Пусть в $C$ находятся числа
+    \[
+        \{c_1, \ldots, c_{10}\}
+    \]
+    Тогда в $C'$ находятся числа
+    \[
+        \{29 - c_1, \ldots, 29 - c_{10}\}
+    \]
+    И сумма чисел в $C \text{ и } C'$ равна
+    \[
+        10 \cdot (c_1 + \ldots + c_{10} + 29 - c_1 + \ldots + 29 - c_{10}) = 290
+    \]
+
+    Симметричное слово есть для любого, но для некоторых оно совпадает.
+    Заметим, что так происходит только когда само слово было палиндромом,
+    Но тогда сумма чисел в выборе, соответствующем такому слову равна 145.
+
+    Значит, матожидание суммы чисел равно 145.
+
+\begin{center} \textbf{4} \end{center}
+    Возьмем некоторое слово. Напишем перед ним букву b, а после - a.
+    Теперь расставим в получившейся конструкции перегородки между разными буквами.
+    Тогда количество подслов ab равно количеству перегородок, у которых слева стоит a, а справа - b. Заметим, что для таких перегородок соседние перегородки обязательно делят подслова ba (b слева, a справа), иначе наша перегородка имела бы слева букву b или справа букву a. Значит, количество слов с $n$ подсловами равно $ \binom{21}{2n + 1} $
+    Тогда матожидание равно
+    \[
+        \frac{\displaystyle \sum_{i = 1}^{10} \binom{21}{2i + 1} i }{2^{20}} = 4.75
+    \]
+    (Ничего лучше, чем посчитать на калькуляторе, я не придумал)
+
+\begin{center} \textbf{5} \end{center}
+    \[
+        \probability{X \geqslant 6} =
+        \probability{2^X \geqslant 2^6}
+    \]
+    По неравенству Маркова:
+    \[
+        \probability{2^X \geqslant 64} \leqslant \frac{5}{64} < \frac{1}{10}
+    \]
+    \qed
+
+\begin{center} \textbf{6} \end{center}
+    Всего функций $(100n)^n$, из них инъекций: $\displaystyle \frac{(100n)!}{(99n)!}$
+    
+    Так как нам нужно найти предел, можно рассмотреть только $n = 2k, k \in \mathbb{N}$ (просто чтобы $n$ делилось на $2$)
+    \begin{flalign*}
+        A_n = \frac{(100n)!}{(99n)! (100n)^n} &=\\
+        \frac{99n + 1}{100n} \cdot \ldots \cdot \frac{99n + n}{100n} &=\\
+        \frac{99n + 1}{100n} \cdot \ldots \cdot \frac{99n + \frac{n}{2}}{100n} \cdot Q_n &\leqslant \qquad\qquad Q_n < 1\\
+        \br{ \frac{99n + \frac{n}{2}}{100n} }^{\frac{n}{2}} Q_n =
+        \br{ \frac{99.5}{100} }^{\frac{n}{2}} Q_n = B_n
+    \end{flalign*}
+    $\displaystyle \lim_{n \to \infty} B_n = 0$, а так как $0 < A_n \leqslant B_n$, то 
+    $\displaystyle \lim_{n \to \infty} A_n = 0$, что и требовалось
+
+\end{document}
diff --git a/dm/dm-15.tex b/dm/dm-15.tex
new file mode 100644
index 0000000..db0de91
--- /dev/null
+++ b/dm/dm-15.tex
@@ -0,0 +1,146 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-15 (\texttt{cw15\_plus})}
+\title{Дискретная математика 15}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\twocolumn
+
+\dmquestion{1}
+    \[
+        99^{1000} = (-1)^{1000} = 1 \pmod{100}
+    \]
+
+\dmquestion{2}
+    \begin{align*}
+        x + 10y &=\\
+        &= x + 10y - 13x - 13y\\
+        &= -12x - 3y\\
+        &= -3(4x + y) \pmod{13}
+    \end{align*}
+
+    Так как $(3; 13) = 1$, то $x + 10y = 0 \pmod{13}$ тогда и только тогда,
+    когда $4x + y = 0 \pmod{13}$
+
+\dmquestion{3}
+    \begin{align*}
+        53x &= 1 &\pmod{42}\\
+        11x &= 1 + 42 \cdot 6 &\pmod{42}\\
+        11x &= 253 &\pmod{42}\\
+        x &= 23 &\pmod{42}
+    \end{align*}
+
+\dmquestion{4}
+    \begin{align*}
+        74x + 47y = 2900\\
+        27x = 2900  \pmod{47}\\
+        27x = 33    \pmod{47}\\
+        9x = 11     \pmod{47}\\
+        9x = -36    \pmod{47}\\
+        x = -4 = 43 \pmod{47}\\\\
+        74 \cdot 43 + 47y = 2900\\
+        47y = -282\\
+        y = -6
+    \end{align*}
+
+    Все решения имеют вид
+    \[
+        (x_0 + 47k; y_0 - 74k), \qquad k \in \mathbb{Z}
+    \]
+
+    Поэтому неотрицательных решений у этого уравнения нет
+
+\dmquestion{5}
+    \[
+        \frac{n^2 - n + 1}{n^2 + 1}
+    \]
+    
+    Предположим противное: пусть такая дробь сократима.
+    
+    Пусть существует $p > 1$ такое, что
+    \[
+        p \mid (n^2 + 1), p \mid (n^2 - n + 1)
+    \]
+    
+    Значит,
+    \[
+        n = (n^2 + 1) - (n^2 - n + 1) \text{ тоже делится на $p$.}
+    \]
+    
+    Значит, $p \mid n^2$.
+
+    Но $n^2 + 1 = 1 \pmod{p}$. Противоречие.
+
+\dmquestion{6}
+
+    \textbf{Лемма}
+    \[
+        3^m - 1 = 3^{m - n} - 1 \pmod{3^n - 1}
+    \]
+    
+    Доказательство:
+    \begin{align*}
+        3^{m - n}(3^n - 1) = 0 \pmod{3^n - 1}\\
+        3^m - 3^{m - n} = 0 \pmod{3^n - 1}\\
+        3^m = 3^{m - n} \pmod{3^n - 1}\\
+        3^m - 1 = 3^{m - n} - 1 \pmod{3^n - 1}\\
+        \qed
+    \end{align*}
+
+    По алгоритму Евклида и лемме (просто вычитаем одну степень из другой):
+    \begin{align*}
+        (3^{133} - 1, 3^{101} - 1) =\\
+        (3^{101} - 1, 3^{32} - 1) =\\
+        (3^{32} - 1, 3^5 - 1) =\\
+        (3^2 - 1, 3^5 - 1) =\\
+        (3^1 - 1, 3^2 - 1) =\\
+        (2, 8) = 2
+    \end{align*}
+
+\dmquestion{7}
+
+    \[
+        \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{p - 1} =
+        \frac{\frac{(p - 1)!}{1} + \frac{(p - 1)!}{2} + \ldots + \frac{(p - 1)!}{p - 1}}{(p - 1)!}
+    \]
+
+    Сгруппируем слагаемые в числителе так, чтобы их знаменатели в сумме равнялись $p$.
+    Так можно сделать, потому что их четное число.
+    \[
+        \frac{
+            \br{ \frac{(p - 1)!}{1} + \frac{(p - 1)!}{p - 1} } +
+            \br{ \frac{(p - 1)!}{2} + \frac{(p - 1)!}{p - 2} } + \ldots
+        }{(p - 1)!}
+    \]
+
+    Заметим, что каждая скобка тогда делится на $p$:
+    \begin{gather*}
+        \frac{(p - 1)!}{k} + \frac{(p - 1)!}{p - k} =\\[8pt]
+        (p - 1)! \br{ \frac{(p - k) + k}{k(p - k)}} =\\[8pt]
+        p\frac{(p - 1)!}{k(p - k)}
+    \end{gather*}
+
+    Так как это сумма факториалов, деленных на одно число, меньшее аргумента факториала, то это все еще целое число, а так как $p$ - простое и точно не делится на $k$ и $p - k$, то его можно вынести за скобку.
+
+    Тогда наша сумма представляется в виде
+
+    \[
+        \frac{p \cdot Q}{(p - 1)!}
+    \]
+
+    Так как в факториале нет множителей, делящих $p$, то $p$ останется в числителе, значит, числитель делится на $p$ \qed
+\end{document}
diff --git a/dm/dm-16.tex b/dm/dm-16.tex
new file mode 100644
index 0000000..054f0a2
--- /dev/null
+++ b/dm/dm-16.tex
@@ -0,0 +1,109 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-16 (\texttt{cw16\_plus})}
+\title{Дискретная математика 16}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\twocolumn
+
+\dmquestion{1}
+
+    $\varphi(n) < n$, поэтому в $n!$ точно есть множитель $\varphi(n)$.
+
+    Пусть $n! = \varphi(n) \cdot Q$
+
+    Тогда по теореме Эйлера (так как $(n, 2) = 1$)
+    \[
+        2^{n!} = 2^{\varphi(n) \cdot Q} = \br{ 2^{\varphi(n)} }^Q = 1^Q = 1 \pmod{n}
+    \]
+
+    Поэтому $2^{n!} - 1 \divby n$
+
+\dmquestion{2}
+
+    Посмотрим, какие остатки может иметь $a^{10}$ при делении на $11$:
+    Либо $a$ делится на $11$, тогда $a^{10} = a = 0 \pmod{11}$. Либо $a$ не делится на $11$ и тогда, так как $11$ - простое число, $a^{10} = 1 \pmod{11}$ по МТФ. Аналогично для других букв. Тогда сумма
+    \[
+        a^{10} + b^{10} + c^{10} + d^{10} + e^{10} + f^{10}
+    \]
+    по модулю $11$ может принимать любое значение от $0$ до $6$. Но по условию она равна $0$, поэтому и каждое слагаемое равно $0$ по модулю $11$.
+    Тогда каждая переменная делится на $11$ и $abcdef$ делится на $11^6$ \qed
+
+\dmquestion{3}
+    \[
+        7^2 = 49 = 1 \pmod{16}
+    \]
+    Поэтому $7^{7^7} = 7 \pmod{16}$, так как $7^7$ - нечетное число.
+    Тогда по теореме Эйлера
+    \[
+        7^{7^{7^7}} = 7^7 \pmod{17}
+    \]
+    \[
+        7^7 = 49^3 \cdot 7 = (-2)^3 \cdot 7 = -8 \cdot 7 = 12 \pmod{17}
+    \]
+
+\dmquestion{4}
+    \begin{align*}
+        x^2 = 1 \pmod{200}\\
+        x^2 - 1 = 0 \pmod{200}\\
+        (x + 1)(x - 1) = 0 \pmod{200}
+    \end{align*}
+
+    Если $x$ - нечетный, то такое произведение всегда делится на $8$,
+    а если четный, то не делится даже на $2$.
+
+    Если одна из скобок делится на $5$, то другая точно не делится.
+
+    Поэтому нам нужно решить такую систему:
+    \[
+        \begin{cases}
+            x = 1 \pmod{2}\\
+            \begin{sqcases}
+                x + 1 = 0 \pmod{25}\\
+                x - 1 = 0 \pmod{25}
+            \end{sqcases}
+        \end{cases}
+    \]
+    Решениями являются вычеты $\{49, 51, 99, 101, 149, 151, 199, 1\}$
+
+\dmquestion{5}
+    Число заканчивается на $0001$ тогда и только тогда, когда оно сравнимо с $1$ по модулю $10^4$.
+    По теореме Эйлера
+    \[
+        3^{\varphi(10000)} = 1 \pmod{10000}
+    \]
+
+\dmquestion{6}
+    \begin{align*}
+        x^2 = x \pmod{10^k}\\
+        x(x - 1) = 0 \pmod{10^k}
+    \end{align*}
+
+    Если $x$ делится на $2^n$, то $x - 1$ на $2$ не делится.
+    Поэтому, на $2^k$ делится либо $x$, либо $x - 1$. Аналогично с $5$.
+    Тогда есть 4 случая:
+    \begin{enumerate}
+        \item $x \divby 10^k \Rightarrow x = 0 \pmod{10^k}$
+        \item $x - 1 \divby 10^k \Rightarrow x = 1 \pmod{10^k}$
+        \item $x \divby 2^k, \quad x - 1 \divby 5^k$
+        \item $x \divby 5^k, \quad x - 1 \divby 2^k$
+    \end{enumerate}
+
+    В каждом из 3 и 4 пунктов есть ровно одно решение по модулю $10^k$ по китайской теореме об остатках. Решения не совпадают, потому что иначе $x$ и $x - 1$ должны бы были одновременно делиться на $2^k$. По тем же соображениям они не пересекаются и с пунктами 1 и 2.
+    \qed
+
+\end{document}
diff --git a/dm/dm-17.tex b/dm/dm-17.tex
new file mode 100644
index 0000000..8d5e101
--- /dev/null
+++ b/dm/dm-17.tex
@@ -0,0 +1,100 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-17 (\texttt{cw17\_plus})}
+\title{Дискретная математика 17}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\twocolumn
+
+\dmquestion{1}
+    
+    С семинара:
+    \[
+        (FG)' = F'G + G'F, \qquad \brac{1}{F}' = -\frac{F'}{F^{2}}
+    \]
+    Тогда:
+    \[
+        \brac{F}{G}' =
+        \br{ F \cdot \frac{1}{G} }' =
+        \frac{F'}{G} - \frac{G'F}{G^2} =
+        \frac{F'G - G'F}{G^2}
+    \]
+
+\dmquestion{2}
+    
+    Пусть $F = f_1 x + f_2 x^2 + \ldots$
+
+    Аналогично, $G = g_1 x + g_2 x^2 + \dots$
+
+    Тогда
+    \[
+        F(G(x)) = f_1 G(x) + f_2 G(x)^2 + \ldots
+    \]
+
+    Будем строить $G$ по коэффициэнтам:
+    \begin{align*}
+        f_1 g_1 &&&&= 1\\
+        f_1 g_2 &+ f_2 g_1 &&&= 0\\
+        f_1 g_3 &&+ f_3 g_1 &&= 0\\
+        f_1 g_4 &+ f_2 g_2 &&+ f_4 g_1 &= 0
+    \end{align*}
+
+    Тогда для каждого уравнения есть новый (ещё не определённый) коэффициент из первого члена ($f_1G(x)$), то есть если $f_1 \neq 0$, то мы всегда сможем продолжать строить функцию $G$ таким образом.
+
+    Если $f_1 = 0$, то:
+    \begin{enumerate}
+        \item $F \equiv 0$, тогда $\forall G: F(G(x)) \equiv 0$
+        \item $F \neq 0 $, тогда минимальная степень $x$ в выражении не меньше $2$,
+        для любой $G$.
+    \end{enumerate}
+
+    Поэтому $F$ ``обратима'' (т.е. $\exists G : F(G(x)) = x$)
+    тогда и только тогда, когда $f_1 \neq 0$.
+
+\newpage
+
+\dmquestion{4}
+    \begin{align*}
+        F &= (1, 1, 1, 1, 1, \ldots)\\
+        F' &= (0, 1, 2, 3, 4, \ldots)\\
+        F'' &= (0, 0, 2 \cdot 1, 3 \cdot 2, 4 \cdot 3, \ldots)\\
+    \end{align*}
+
+    Мы знаем, что $F = \frac{1}{1 - x}$.
+
+    Тогда $F' = \frac{1}{\br{ 1 - x }^2}$
+    и $F'' = 2\frac{1 - x}{(1 - x)^4} = 2\frac{1}{(1 - x)^3}$.
+
+    Также мы знаем, что если умножить функцию $G$ на $S = (1 + x + x^2 + \ldots)$, 
+    то мы получим функцию, у которой $i$-тый коэффициент равен сумме первых $i$ коэффициентов $G$
+
+    \[
+        K = \frac{F''}{1 - x} = \frac{2}{(1 - x)^4}
+    \]
+    \[
+        K^{(n)} = 2\br{ 4 \cdot 5 \cdot \ldots (n + 3)
+            \frac{(1 - x)^{n + 2}}{(1 - x)^{2(n + 3)}} } = \frac{2n!}{(1 - x)^{n + 4}}
+    \]
+    \[
+        \frac{K^{(n)}}{n!} = \frac{2(n + 3)!}{3!n!} = \frac{(n + 1)(n + 2)(n + 3)}{6}
+    \]
+    Это не совсем то, что мы хотели, потому что в $F''$ были два лишних нуля. Поэтому правильная формула выглядит так:
+    \[
+        \frac{(n - 1)n(n + 2)}{6} = \frac{n(n^2 - 1)}{6}
+    \]
+
+\end{document}
diff --git a/dm/dm-18.tex b/dm/dm-18.tex
new file mode 100644
index 0000000..e764814
--- /dev/null
+++ b/dm/dm-18.tex
@@ -0,0 +1,80 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-17 (\texttt{cw18\_plus})}
+\title{Дискретная математика 18}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\setlength{\columnsep}{1cm}
+\twocolumn
+\dmquestion{1}
+
+    Первый может на первом ходу взять четыре спички, а дальше играть по следующей стратегии:
+    если второй берет $k$ спичек, то первый следующим ходом должен будет взять $6 - k$ спичек. Он, очевидно, может так делать в любой момент, а так же после каждого хода первого количество спичек уменьшается на $6$. Значит, первый заберет последнюю спичку, а значит, второму спичек не останется и он проиграет.
+
+    Ответ: у первого.
+\dmquestion{2}
+
+    Пусть второй сделает четыре хода как-нибудь.
+
+    Пусть, для определенности, он всегда пишет $1$.
+    Тогда после пятого хода первого игрока на доске будет написано число $n$.
+    Одно из чисел $10n + 0, 10n + 1, 10n + 2, 10n + 3, 10n + 4, 10n + 5, 10n + 6$ обязательно делится на $7$, а значит, второй может написать соответствующую цифру и сделать число делящимся на $7$.
+
+    Ответ: у второго.
+\dmquestion{3}
+
+    Заметим, что если число на доске - нечетное, то у него есть только нечетные делители. Поэтому за один ход его можно сделать только четным. А если на доске написано четное число, то его всегда можно уменьшить на единичку, то есть, сделать нечетным.
+
+    Тогда первый может всегда делать число нечетным, а второй всегда будет вынужден делать его четным (после хода второго число на доске обязательно четное, поэтому первый может продолжать играть по этой стратигии). С каждым ходом число на доске уменьшается, поэтому когда-нибудь оно станет нулем и игра закончится. Так как четные числа появляются только после ходов второго игрока, то он и проиграет.
+
+    Ответ: у первого.
+\dmquestion{4}
+
+    Рассмотрим немножко другую игру (3 с семинара).
+    У первого всегда есть выигрышная стратегия:
+
+    Если количество минусов нечетно, то первым ходом он переправит минус посередине, а если четно, то два минуса посередине. Дальше он может действовать симметрично второму относительно центра (потому что первый не может ходить одновременно по обе стороны от середины). Значит, он всегда может сделать ход после второго, а значит он выиграет.
+
+    Теперь, рассмотрим нашу задачу. При $n = 1, 2$ у первого есть выигрышная стратегия - переправить все минусы. При $n > 2$ после любого хода первого второй может действовать как если бы они играли в рассмотренную выше игру (с последовательно выписанными оставшимися минусами) и выиграть. То есть при $n > 2$ у второго есть выигрышная стратегия.
+
+    Ответ: 1, 2.
+\dmquestion{5}
+
+    Докажем, что разбить выпуклый $n$-угольник можно только на $n - 2$ треугольника.
+
+    Для $n = 3$: треугольник уже разбит на один треугольник.
+
+    Пусть для $n - 1$ верно. Возьмем $n$-угольник и любое ребро из его разбиения на треугольники. Такое ребро делит его на два выпуклых многоугольника с количеством углов $k$ и $n - k + 2$. Тогда первый можно разбить только на $k - 2$ треугольников, а второй только на $n - k$ треугольников. Значит, разбить $n$-угольник можно только на $n - 2$ треугольника.
+
+    Значит, вне зависимости от ходов, при четных $n$ выигрывает первый, а при нечетных - второй.
+\dmquestion{6}
+
+    Пронумеруем вершины $v_1, \ldots, v_n$. Пусть у первого игрока уже есть связный (связанный ребрами красного цвета) граф на первых $k$ вершинах (назовем его $G_k$) и каждый игрок сделал $k - 1$ ход.
+
+    Так как граф полный, то $v_{k + 1}$ соединена с каждой из вершин в $G_k$.
+    
+    Так как второй игрок сделал $k - 1$ ходов, то есть ребро из $v_{k + 1}$ в $G_k$, которое не покрашено в синий цвет.
+    
+    А так как у первого игрока есть граф на $k$ вершинах, то в нем есть хотя бы $k - 1$ ребер. Значит, первый не красил ребра вне $G_k$, значит, есть ребро из $v_{k + 1}$ в $G_k$, которое еще никем не покрашено.
+
+    Значит, первый может покрасить это ребро в красный цвет и у него будет связный граф на первых $k + 1$ вершинах.
+
+    Так как в самом начале у первого есть связный граф из одной вершины, то он может продолжать действовать так, чтобы перед каждым его ходом у него был связный граф на первых вершинах. Значит, после $n - 1$ хода у него будет связный граф на $n$ вершинах, а второй к этому моменту сделает только $n - 2$ хода, поэтому у него точно не будет связного графа на $n$ вершинах.
+
+    Ответ: при любых $n \geq 2$.
+
+\end{document}
diff --git a/dm/dm-19.tex b/dm/dm-19.tex
new file mode 100644
index 0000000..6d77d4b
--- /dev/null
+++ b/dm/dm-19.tex
@@ -0,0 +1,42 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-19 (\texttt{cw19\_plus})}
+\title{Дискретная математика 19}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\setlength{\columnsep}{1cm}
+\twocolumn
+\dmquestion{1}
+    Заметим, что мы всегда можем выбрать два числа так, что они делят весь массив
+    на три примерно равные части, то есть такие,
+    что каждые две отличаются не более чем на 1.
+    Пусть мы умеем, запросив значение в этих числах, понимать в какой части
+    (или в каких двух подряд идущих частях) лежит максимум.
+    Тогда за 2 хода мы умеем уменьшать рассматриваемый массив в $\frac{3}{2}$ раза, а значит, мы сведем задачу к поиску максимума на массиве из менее чем трех элементов, а значит, решим задачу за менее чем $4\log_3 n$ ходов.
+
+\dmquestion{2}
+
+    Разобьем монеты на $\lfloor n/2 \rfloor$ пар (одна останется)
+    и сравним веса монет в каждой паре.
+    Если нашлась пара, в которой монеты имеют разный вес, то фальшивая в этой паре та, которая легче. Если монеты в каждой паре одинаковы по весу, то фальшивая - та, что осталась. Пар $\lfloor n/2 \rfloor$, поэтому сравнений столько же.
+
+\dmquestion{3}
+
+    Пусть мы справились за меньше, чем $\lfloor n/2 \rfloor$ взвешиваний. Тогда в сравнении могли поучаствовать не более, чем  $n - 3$ монеты. Значит, есть хотя бы три монеты, про которые никакой информации нет. Значит, если фальшивая была среди них, то по итогу взвешивания каждая из них может оказаться ответом, а наверняка выбрать среди них фальшивую мы не можем. Значит, нужно хотя бы $\lfloor n/2 \rfloor$ хода.
+
+
+\end{document}