\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}