1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
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}
|
