Dump some shit

8 files changed, 545 insertions, 12 deletions

diff --git a/alg/alg-2.tex b/alg/alg-2.tex
new file mode 100644
index 0000000..8e33dbb
--- /dev/null
+++ b/alg/alg-2.tex
@@ -0,0 +1,124 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{алг-2}}
+\title{Алгебра 2}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{50pt}
+\clearpage
+
+\dmquestion{1}
+
+    Рассмотрим группу $D_4$. Пусть $H_1$ - группа из симметрий относительно горизонтальной и вертикальной осей симметрий квадрата. В ней находятся $e$, две указанных симметрии и поворот на $\pi$. Методом пристального взгляда убеждаемся, что она нормальна в $D_4$. Теперь возьмем в качестве $H_2$ только одну симметрию. Она нормальна в $H_1$, но не нормальна в $D_4$ например потому, что не коммутирует с любой из диагональных симметрий.
+
+\dmquestion{2}
+
+    Рассмотрим $f = h_1 h_2 h_1^{-1} h_2^{-1}$.
+
+    $H_1$ нормальна, поэтому $h_2 h_1^{-1} h_2^{-1} \in H_1$. Также, $H_1$ - подгруппа и $h_1 \in H_1$,
+        значит, $f = h_1 (h_2 h_1^{-1} h_2^{-1}) \in H_1$.
+
+    $H_2$ нормальна, поэтому $h_1 h_2 h_1^{-1} \in H_2$. Также, $H_2$ - подгруппа и $h_2 \in H_2$,
+        значит, $f = (h_1 h_2 h_1^{-1}) h_2^{-1} \in H_2$.
+
+    Так как $H_1 \cap H_2 = \{e\}$, то $f = e$, поэтому $h_1 h_2 = h_2 h_1$.
+\dmquestion{3}
+
+    \newcommand{\GL}{\mathrm{GL}_n(\mathbb{R})}
+    \newcommand{\SL}{\mathrm{SL}_n(\mathbb{R})}
+
+    Пусть $M \in \GL$
+    принадлежит центру $\GL$.
+
+    Возьмем $A_i$ -- матрицу элементарного преобразования, которая умножает $i$-ю строку на $2$ при умножении на нее слева и столбец при умножении на нее справа.
+
+    тогда так как $M \in Z(\GL)$, то $MA_i = A_iM$.
+    Такое равенство выполняется для всех $1 \leqslant i \leqslant n$ тогда, и только тогда, когда в $M$ ненулевые элементы стоят только на диагонали.
+
+    Теперь возьмем $B_{ij}$ -- матрицу, которая меняет строки $i$ и $j$.
+
+    Умножив $M$ на нее справа и слева получим,
+    что $i$-ый и $j$-й элементы диагонали равны.
+
+    Перебрав $i$ и $j$ получим, что все элементы на диагонали равны. Поэтому $M$ имеет вид $\lambda E$. А такие матрицы коммутируют с любыми.
+
+    Для $\SL$ ситуация почти аналогичная, только нам надо брать матрицы преобразования с единичным определителем:
+
+    Для первого шага нужно преобразование, которое умножает одну строку на $2$, а другую на $\frac{1}{2}$. Так мы получим, что все матрицы из центра - диагональные. А для второго шага надо брать матрицу, которая меняет местами две пары строк. Но так как перестановочные матрицы уже не коммутируют, то по строкам мы выполняем преобразование в одном порядке, а по столбцам - в другом:
+
+    Пусть мы хотим менять строки перестановкой $(12)(23)$, тогда мы меняем столбцы перестановкой $(23)(12)$:
+
+\clearpage
+
+    По строкам:
+    \[
+        \begin{bmatrix}
+            1 &   &  \\
+              & 2 &  \\
+              &   & 3\\
+        \end{bmatrix}
+        \overset{(23)}{\mapsto}
+        \begin{bmatrix}
+            1 &   &  \\
+              &   & 3\\
+              & 2 &  \\
+        \end{bmatrix}
+        \overset{(12)}{\mapsto}
+        \begin{bmatrix}
+              &   & 3\\
+            1 &   &  \\
+              & 2 &  \\
+        \end{bmatrix}
+    \]
+
+    По столбцам:
+    \[
+        \begin{bmatrix}
+            1 &   &  \\
+              & 2 &  \\
+              &   & 3\\
+        \end{bmatrix}
+        \overset{(12)}{\mapsto}
+        \begin{bmatrix}
+              & 1 &  \\
+            2 &   &  \\
+              &   & 3\\
+        \end{bmatrix}
+        \overset{(23)}{\mapsto}
+        \begin{bmatrix}
+              &   & 1\\
+            2 &   &  \\
+              & 3 &  \\
+        \end{bmatrix}
+    \]
+
+    Отсюда получаем, что все элементы на диагонали равны, а значит
+    \[
+        Z(\SL) = \begin{cases}
+        \{E\}, &n = 2k + 1\\
+        \{E, -E\}, &n = 2k
+        \end{cases}
+    \]
+
+\dmquestion{4}
+
+    Воспользуемся тем фактом, что группа целых чисел - циклическая
+    \[
+        (\mathbb{Z}, + ) = \cycle{1}
+    \]
+
+    и любая подгруппа имеет вид $(k\mathbb{Z}, + )$.
+
+    Пусть $(\mathbb{Z}, + ) \overset{\phi}{\simeq} (m\mathbb{Z}, + ) \times (n\mathbb{Z}, + )$.
+    Но так как $\phi$ -- гомоморфизм, то
+    $
+        \cycle{1} \mapsto \cycle{\phi(1)}
+    $.
+
+    Но тогда в образе $\phi$ обе координаты всегда пропорциональны, а это явно не вся группа, если ни один из множителей не $\{e\}$. Противоречие.
+
+\end{document}
diff --git a/alg/alg-3.tex b/alg/alg-3.tex
new file mode 100644
index 0000000..e2cce12
--- /dev/null
+++ b/alg/alg-3.tex
@@ -0,0 +1,75 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{алг-3}}
+\title{Алгебра 3}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{50pt}
+\clearpage
+
+\dmquestion{1}
+
+    Различных базисов в $B$ всего два: $(\pm a, \ldots, \pm a)$,
+    а так как в базисе всего один элемент, то он сразу согласован с $\ \ u_1 = |a|, \ \  e_1 = (\pm 1, \ldots \pm 1)$.
+
+    В $\mathbb{Z}^n$ для элемента $(\pm 1, \ldots, \pm 1)$ мы можем выбрать еще элементов до базиса:
+    \begin{align*}
+        &(1, 0, \ldots, 0)\\
+        &(0, 1, \ldots, 0)\\
+        &\quad \quad \ \ \vdots\\
+        &(0, \ldots, 1, 0)
+    \end{align*}
+
+    Понятно, что это базис и понятно, как получить все остальные - домножить на обратимую над $\mathbb{Z}$ матрицу.
+    Мы не могли брать в качестве базисного элемент $(b, \dots b)$, где $b$ - какой-то делитель $a$,
+    потому что если бы он был в базисе $\mathbb{Z}^n$, то матрица перехода к нему от стандартного базиса была бы необратимой над $\mathbb{Z}$, а значит это не был бы базис.
+
+\dmquestion{2}
+
+    \begin{align*}
+        \begin{bmatrix}
+            5 & 5 & 2\\
+            11 & 8 & 5\\
+            17 & 5 & 8
+        \end{bmatrix} \simeq
+        \begin{bmatrix}
+            1 & 5 & 2\\
+            1 & 8 & 5\\
+            1 & 5 & 8
+        \end{bmatrix} \simeq
+        \begin{bmatrix}
+            1 & 0 & 0\\
+            1 & 3 & 3\\
+            1 & 0 & 6
+        \end{bmatrix} \simeq
+        \begin{bmatrix}
+            1 & 0 & 0\\
+            0 & 3 & 3\\
+            0 & 0 & 6
+        \end{bmatrix} \simeq
+        \begin{bmatrix}
+            1 & 0 & 0\\
+            0 & 3 & 0\\
+            0 & 0 & 6
+        \end{bmatrix} \simeq
+    \end{align*}
+
+    Тогда
+    \[
+        A/B \simeq
+        \mathbb{Z}_1 \times \mathbb{Z}_3 \times \mathbb{Z}_6 =
+        \{0\} \times \mathbb{Z}_3 \times \mathbb{Z}_6 \simeq
+        \mathbb{Z}_3 \times \mathbb{Z}_6
+    \]
+
+\dmquestion{3}
+
+    Рассмотрим группу строго убывающих по модулю последовательностей целых чисел с операцией покоординатного сложения (считаем, что координат бесконечное число).
+    Такое множество счетно, потому что последовательностей, начинающихся с определенного числа конечное число, целые числа счетны, а счетное обьединение конечных или счетных множеств счетно. Ну и это группа с нейтральным элементом $\{0\}$. Так как количество координат бесконечно, а каждый элемент имеет только конечное количество ненулевых координат, то и конечной порождающей системы нет.
+
+
+\end{document}
diff --git a/alg/alg-4.tex b/alg/alg-4.tex
new file mode 100644
index 0000000..7e21970
--- /dev/null
+++ b/alg/alg-4.tex
@@ -0,0 +1,107 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{алг-4}}
+\title{Алгебра 4}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{30pt}
+\clearpage
+
+\dmquestion{1}
+
+    \newcommand{\Z}{\mathbb{Z}}
+
+    Решим уравнение $2x = 0, \ \ x \in \Z_2 \oplus \Z_4 \oplus \Z_3$:
+    из $\Z_2$ мы можем взять любой элемент,
+    из $\Z_4$ можем взять $\{0, 2\}$,
+    из $\Z_3$ только $0$. Тогда уравнению удовлетворяют $4$ элемента.
+    Каждый из этих элементов имеет порядок или $1$ или $2$, но порядок $1$ имеет только нейтральный, поэтому из этих четырех нам не подходит только один. Поэтому элементов порядка $2$ всего $3$: $(0, 2, 0), \ (1, 0, 0), \ (1, 2, 0)$
+
+    Аналогично, $3x = 0$ имеет два ненулевых решения: $(0, 0, 1), \ (0, 0, 2)$
+
+    $4x = 0$ имеет $8$ решений, из которых $4$ удовлетворяют уравнению $2x = 0$, поэтому их порядок никак не больше $2$, поэтому элементов порядка $4$ всего $4$.
+
+    Уравнению $6x = 0$ удовлетворяют $12$ элементов, но из них:
+    один нейтральный, три имеют порядок $2$, и еще $2$ имеют порядок $3$,
+    поэтому элементов порядка $6$ всего $6$ штук.
+
+    Ответ: $3, 2, 4, 6$.
+
+\dmquestion{2}
+
+    $H$ изоморфна либо $\Z_3 \oplus \Z_{25}$, либо $\Z_3 \oplus \Z_5 \oplus \Z_5$, но в первом случае группа циклическая, что противоречит условию, значит $H \simeq \Z_3 \oplus \Z_5 \oplus \Z_5$.
+
+    По теореме с лекции, любая подгруппа порядка $5$ или $15$ - это $\Z_5$ или $\Z_5 \oplus \Z_3$ соответственно. В частности, это значит, что такие подгруппы циклические, и порождены одним элементом порядка $5$ или $15$ соответственно.
+
+    Как в первой задаче, находим количество элементов нужных порядков.
+    Их будет соответственно $24$ и $48$.
+    Но в подгруппе порядка $5$ есть $4$ разных порождающих, потому что они все имеют порядок $5$,
+    а в подгруппе размера $15$ есть $\varphi(15) = 8$ разных порождающих.
+    Поэтому разных подгрупп порядка $5$: $\frac{24}{4} = 6$, а порядка $15$: $\frac{48}{8} = 6$.
+
+\dmquestion{3}
+
+    Перейдем к другому базису: запишем порождающие $B$ в строки и снизу припишем координаты представителя:
+    \begin{align*}
+        &\begin{pmatrix}
+            2 & 1 & -50\\
+            4 & 5 & 60\\
+            \hline
+            32 & 0 & 31
+        \end{pmatrix} \sim
+        \begin{pmatrix}
+            1 & 2 & -50\\
+            5 & 4 & 60\\
+            \hline
+            0 & 32 & 31
+        \end{pmatrix} \sim
+        \begin{pmatrix}
+            1 & 0 & -50\\
+            5 & -6 & 60\\
+            \hline
+            0 & 32 & 31
+        \end{pmatrix} \sim\\
+        \sim&\begin{pmatrix}
+            1 & 0 & -50\\
+            0 & -6 & 310\\
+            \hline
+            0 & 32 & 31
+        \end{pmatrix} \sim
+        \begin{pmatrix}
+            1 & 0 & 0\\
+            0 & -6 & 310\\
+            \hline
+            0 & 32 & 31
+        \end{pmatrix} \sim
+        \begin{pmatrix}
+            1 & 0 & 0\\
+            0 & 6 & -310\\
+            \hline
+            0 & 32 & 31
+        \end{pmatrix} \sim\\
+        \sim&\begin{pmatrix}
+            1 & 0 & 0\\
+            0 & 6 & 2\\
+            \hline
+            0 & 32 & 1695
+        \end{pmatrix} \sim
+        \begin{pmatrix}
+            1 & 0 & 0\\
+            0 & 2 & 6\\
+            \hline
+            0 & 1695 & 32
+        \end{pmatrix} \sim
+        \begin{pmatrix}
+            1 & 0 & 0\\
+            0 & 2 & 0\\
+            \hline
+            0 & 1695 & -5053
+        \end{pmatrix}
+    \end{align*}
+
+    Получается, что $A/B \simeq \{0\} \oplus \Z_2 \oplus \Z$, а так как последняя координата ненулевая, то $\mathrm{ord}((32e_1 + 31e_3) + B) = \infty$
+\end{document}
diff --git a/calc/sol0413.tex b/calc/sol0413.tex
new file mode 100644
index 0000000..c90ffa5
--- /dev/null
+++ b/calc/sol0413.tex
@@ -0,0 +1,120 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{матан-0413}}
+\title{Матанализ 0413}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{50pt}
+\clearpage
+
+\dmquestion{3b}{\[
+    \lim_{\substack{x \to +\infty \\ y \to +\infty}} \brac{xy}{x^2 + y^2}^{x^2}
+\]}
+
+    Так как обе переменные стремятся к $+\infty$, то можно считать, что $x > 0, y > 0$.
+
+    Перейдем к полярным координатам:
+    \begin{align*}
+        x &= r \cos \phi\\
+        y &= r \sin \phi
+    \end{align*}
+
+    \[
+        \lim_{\substack{x \to +\infty \\ y \to +\infty}} \brac{xy}{x^2 + y^2}^{x^2} =
+        \lim_{\substack{x \to +\infty \\ \phi \in [0, 2\pi)}} (\sin\phi\cos\phi)^{x^2}
+    \]
+
+    Теперь ограничим функцию с обеих сторон в предположении
+    $\phi \in \left(0, \frac{\pi}{2}\right)$:
+    \[
+        0 \leqslant
+        (\sin\phi\cos\phi)^{x^2} =
+        \left(\frac{1}{2}\sin 2\phi\right)^{x^2} \leqslant
+        \brac{1}{2}^{x^2}
+    \]
+
+    Поэтому
+
+    \[
+        0 \leqslant
+        \lim_{\substack{x \to +\infty \\ y \to +\infty}} \brac{xy}{x^2 + y^2}^{x^2} \leqslant
+        \lim_{x \to +\infty} \brac{1}{2}^{x^2} = 0
+    \]
+
+    Значит и наш предел существует и равен $0$.
+
+\dmquestion{4d}
+    \[
+        \lim_{\substack{x \to 1 \\ y \to 0}} \frac{\log(1 + x - e^y)}{x^2 - xe^y}
+    \]
+
+    \[
+        z = x - e^y, z \to 0
+    \]
+
+    \[
+        \lim_{\substack{x \to 1 \\ y \to 0}} \frac{\log(1 + x - e^y)}{x^2 - xe^y} =
+        \lim_{\substack{x \to 1 \\ z \to 0}} \frac{\log(1 + z)}{xz} =
+        \lim_{\substack{x \to 1 \\ z \to 0}} \frac{z - \frac{z^2}{2} + o(z^2)}{xz} =
+        \lim_{\substack{x \to 1 \\ z \to 0}} \frac{1 - \frac{z}{2} + o(z)}{x} = 1
+    \]
+
+\dmquestion{8}
+\[
+    f(x, y) = \sin\brac{\pi}{1 - x^2 - y^2}
+\]
+
+    Я хочу доказать, что функция не является равномерно непрерывной.
+    Для простоты рассмотрим интервал $y = 0, 0 < x < 1$. мне надо доказать, что
+    \[
+        \exists \varepsilon > 0 :
+        \forall \delta > 0 :
+        \exists x_1, x_2 :
+        |x_1 - x_2| < \delta, |f(x_1, 0) - f(x_2, 0)| \geqslant \varepsilon
+    \]
+
+    Пусть $\varepsilon = 1$. Тогда $\forall \delta$ надо предъявить нужные $x_1$ и $x_2$:
+
+    Пусть для некоторого $n \geqslant 1$
+    \begin{align*}
+        x_1 &= \sqrt{1 - \frac{1}{\frac{1}{2} + 2n}}\\
+        x_2 &= \sqrt{1 - \frac{1}{-\frac{1}{2} + 2n}}\\
+    \end{align*}
+
+    При подстановке в $f(x_i, 0)$ получится:
+    \[
+        \sin\brac{\pi}{1 - x_i^2)} =
+        \sin\brac{\pi}{1 - \br{1 - \frac{1}{\pm\frac{1}{2} + 2n}}} =
+        \sin\br{\pi\br{\pm\frac{1}{2} + 2n}} = \pm 1
+    \]
+
+    Значит, $|f(x_1, 0) - f(x_2, 0)| = 2 > \varepsilon$.
+
+    \bigskip\bigskip
+
+    Теперь надо подобрать $n$ так, чтобы расстояние между $x_1$ и $x_2$ было меньше $\delta$.
+
+    По построению видно, что $0 < x_1 < x_2 < 1$. Поэтому достаточно найти такой $n$, что $1 - x_1 < \delta$. отсюда будет следовать, что $|x_2 - x_1| < \delta$.
+
+    Пусть $0 < \delta < 1$, иначе $1 - x_1 < 1 \leqslant \delta$ и все доказано.
+
+    \begin{align*}
+        1 - x_1 &< \delta\\
+        1 - \delta &< x_1\\
+        (1 - \delta)^2 &< x_1^2 = 1 - \frac{1}{\frac{1}{2} + 2n}\\
+        1 - 2\delta + \delta^2 &< 1 - \frac{1}{\frac{1}{2} + 2n}\\
+        - 2\delta + \delta^2 &< - \frac{1}{\frac{1}{2} + 2n}\\
+        2\delta - \delta^2 &> \frac{1}{\frac{1}{2} + 2n}\\
+        \delta(2 - \delta) &> \frac{1}{\frac{1}{2} + 2n}\\
+        &\explain{0 < \delta < 1 \implies \delta(2 - \delta) > 0}\\
+        \frac{1}{2} + 2n &> \frac{1}{\delta(2 - \delta)}\\
+        2n &> \frac{1 - \frac{\delta(2 - \delta)}{2}}{\delta(2 - \delta)}
+    \end{align*}
+
+    При таком $n$ расстояние между $x_1$ и $x_2$ меньше $\delta$, но расстояние между значениями функции больше $\varepsilon$, что и требовалось.
+
+\end{document}
diff --git a/calc/sol0420.tex b/calc/sol0420.tex
new file mode 100644
index 0000000..628ac5a
--- /dev/null
+++ b/calc/sol0420.tex
@@ -0,0 +1,80 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{матан-0420}}
+\title{Матанализ 0420}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{50pt}
+\clearpage
+
+\dmquestion{1c}{\[
+    f(x, y, z) = \frac{z}{x^2 + y^2}
+\]}
+
+    \begin{align*}
+        \fractial{f}{x} &= -\frac{2 x z}{(x^2 + y^2)^2}\\[8pt]
+        \fractial{f}{y} &= -\frac{2 y z}{(x^2 + y^2)^2}\\[8pt]
+        \fractial{f}{z} &= \frac{1}{x^2 + y^2}\\
+    \end{align*}
+    \[
+        \dif f =
+            -\frac{2 x z}{(x^2 + y^2)^2} \dif x
+            -\frac{2 y z}{(x^2 + y^2)^2} \dif y
+            +\frac{1}{x^2 + y^2} \dif z
+    \]
+
+\dmquestion{5}
+
+    Нормаль к плоскости из условия: $n = (1, -4, 6)$.
+
+    Пусть $F = x^2 - 2y^2 - z^2 - 12 = 0, \nabla F = (2x, -4y, -2z)$.
+
+    Нам требуется решить систему
+    \[
+        \begin{cases}
+            \nabla F (x_0, y_0, z_0)\  \|\  n\\[6pt]
+            F(x_0, y_0, z_0) = 0
+        \end{cases}
+    \]
+
+    Из первого:
+    \[
+        y_0 = 2x_0, \qquad -\frac{1}{3}z_0 = 2x_0, \quad z_0 = -6x_0
+    \]
+
+    Второе:
+    \[
+        x_0^2 - 8x_0^2 - 36x_0^2 - 12 = 0
+    \]
+    \[
+        -43x_0^2 = 12
+    \]
+
+    Но такого в $\mathbb{R}$ не бывает, поэтому у поверхности нет точек, в которых касательная плоскость параллельна плоскости из условия.
+
+\dmquestion{15b}{\[
+    x^y = y^x
+\]}
+\clearpage
+
+\dmquestion{16c}{\[
+    x + y + z = e^z
+\]}
+
+    Продифференцируем обе части равенства по $x$
+    \[
+        1 + \fractial{z}{x} = \fractial{z}{x} e^z
+    \]
+    \[
+        \fractial{z}{x} = \frac{1}{e^z - 1}
+    \]
+
+    Аналогично по $y$, 
+    \[
+        \fractial{z}{y} = \frac{1}{e^z - 1}
+    \]
+\end{document}
diff --git a/intro.sty b/intro.sty
index 174403a..8f87d9a 100644
--- a/intro.sty
+++ b/intro.sty
@@ -38,18 +38,6 @@
     headsep=.1in
 }
 
-\newcommand{\question}[2]{
-    \def\FrameCommand{
-        \fboxsep=\FrameSep\fcolorbox{gray}{white}
-    }
-    \MakeFramed{
-        \advance\hsize-\width \FrameRestore
-    }
-        \noindent {\small \roboto \textbf{#1}}
-        #2
-    \endMakeFramed
-}
-
 \newcommand{\dmquestion}[1]{
     \begin{center}
         {
diff --git a/mathshit.sty b/mathshit.sty
index 0a64818..31e6398 100644
--- a/mathshit.sty
+++ b/mathshit.sty
@@ -35,6 +35,7 @@
 \newcommand{\br}[1]{\left( #1 \right)}
 \newcommand{\brac}[2]{ \br{ \frac{#1}{#2} } }
 \newcommand{\dbrac}[2]{ \br{ \dfrac{#1}{#2} } }
+\newcommand{\fractial}[2]{ \frac{\partial #1}{\partial #2} }
 \newcommand*{\qed}{\hfill\ensuremath{\blacksquare}}
 \newcommand*{\qedempty}{\hfill\ensuremath{\square}}
 
diff --git a/prog/prog-2.tex b/prog/prog-2.tex
new file mode 100644
index 0000000..f8268c0
--- /dev/null
+++ b/prog/prog-2.tex
@@ -0,0 +1,38 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{аисд-2}}
+\title{Алгоритмы и структуры данных 2}
+
+\usepackage{ctable}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{50pt}
+\clearpage
+
+\newcommand{\funcname}[1]{
+    {\incons
+        \textbf{#1}}
+}
+
+\newcommand{\len}[1]{\mathrm{len}\!\left( #1 \right)}
+
+\dmquestion{1}
+
+    Посчитаем минимальное количество вершин, которое может иметь дерево с таким свойством, назовем это число $n(h)$. У корня есть левое и правое поддеревья, высота которых отличается не более, чем на $1$, поэтому в них вершин не меньше $n(h - 1)$ и $n(h - 2)$ то есть всего вершин не меньше $n(h - 1) + n(h - 2) + 1$.
+    Теперь нам нужна какая-то база для $n$, пусть она будет такая: $n(1) = 1, \ \ n(2) = 2$. Тогда видно, что $n(h) > F_h$, где $F_k$ - k-тое число Фибоначчи. Но так как $F_k = \Theta(\phi^k)$, то, логарифмируя, получаем, что $\log_\phi n(h) \geqslant h$, где $\phi$ - некоторая константа.
+
+\dmquestion{2}
+
+    Так как $E$ и $H$ соединены ребром, то хотя бы одна из них черная, а значит, чтобы не нарушать черной высоты, $D$ должна быть черной. $A$ также должна быть черной всегда. Для все остальных вершин есть раскраски, в которых они как черного, так и красного цвета:
+
+    \medskip
+
+    \center \includegraphics[scale=0.25]{rbt.jpg}
+
+    { \color{lightgray} Я бы честно нарисовал в tikz, но нет времени :(}
+
+\end{document}