1 files changed, 113 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}