diff options
author | syn <isaqtm@gmail.com> | 2020-01-28 00:39:06 +0300 |
---|---|---|
committer | syn <isaqtm@gmail.com> | 2020-01-28 00:39:06 +0300 |
commit | fd0f78f4de5ced34aa68b73dd37910b0db8307bd (patch) | |
tree | b80cd6c254c308764f6e996de3dfbbd24e2448f5 | |
download | tex2-fd0f78f4de5ced34aa68b73dd37910b0db8307bd.tar.gz |
Init commit
-rw-r--r-- | dm-14.tex | 113 | ||||
-rw-r--r-- | intro.tex | 68 | ||||
-rw-r--r-- | sol0120.tex | 372 |
3 files changed, 553 insertions, 0 deletions
diff --git a/dm-14.tex b/dm-14.tex new file mode 100644 index 0000000..cb48628 --- /dev/null +++ b/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{\text{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\\ + \braced{ \frac{99n + \frac{n}{2}}{100n} }^{\frac{n}{2}} Q_n = + \braced{ \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/intro.tex b/intro.tex new file mode 100644 index 0000000..02dc951 --- /dev/null +++ b/intro.tex @@ -0,0 +1,68 @@ +\usepackage[sfdefault,condensed,scaled=0.9]{roboto} +\usepackage{inconsolata} +\setmonofont[Scale=0.9]{Inconsolata} + +\setlength\headheight{13.6pt} + +\usepackage{ + amsmath, amsthm, amssymb, mathtools, commath, + graphicx, xcolor, + fancyhdr, hyperref, enumerate, framed +} +\usepackage[shortlabels]{enumitem} + +\flushbottom +\usepackage[bottom]{footmisc} +\renewcommand{\baselinestretch}{1.06} % Adjust line spacing +\usepackage{geometry}\geometry{letterpaper, % Set page margins + left=0.7in, right=0.7in, + top=0.8in, bottom=0.9in, + headsep=.1in +} + +\setlength\FrameSep{0.75em} +\setlength\OuterFrameSep{\partopsep} + +\newenvironment{cframed}[1][gray] + {\def\FrameCommand{\fboxsep=\FrameSep\fcolorbox{#1}{white}} + \MakeFramed {\advance\hsize-\width \FrameRestore}} + {\endMakeFramed} + +\newcommand{\question}[2]{ + \bigskip\bigskip + \begin{cframed} + \noindent \textbf{#1} + #2 + \end{cframed} +} + +\newcommand{\braced}[1]{\left( #1 \right)} + +\DeclarePairedDelimiter\ceil{\lceil}{\rceil} +\DeclarePairedDelimiter\floor{\lfloor}{\rfloor} + +\DeclareMathOperator{\tg}{tg} +\DeclareMathOperator{\ctg}{ctg} +\DeclareMathOperator{\probop}{Pr} +\DeclareMathOperator{\expectop}{E} + +\newcommand{\probability}[1]{\probop \boldsymbol{[}#1\boldsymbol{]}} +\newcommand{\expected}[1]{\expectop \boldsymbol{[}#1\boldsymbol{]}} + +\newcommand{\sinx}{\sin x} +\newcommand{\cosx}{\cos x} +\newcommand{\tgx}{\tg x} +\newcommand{\todo}{\texttt{todo!}} + + +\newcommand{\osmall}[1]{\overline{o}\left( #1 \right)} + +\hypersetup{colorlinks=true, linkcolor=magenta} + +% -- Left/right header text and footer (to appear on every page) -- +\pagestyle{fancy} +\renewcommand{\footrulewidth}{0.4pt} +\renewcommand{\headrulewidth}{0.4pt} + +\cfoot{} +\rfoot{\thepage} diff --git a/sol0120.tex b/sol0120.tex new file mode 100644 index 0000000..10ecfbb --- /dev/null +++ b/sol0120.tex @@ -0,0 +1,372 @@ +\documentclass[10pt,a5paper]{article} +\usepackage[svgnames, rgb]{xcolor} + +\input{intro} + +\lhead{\color{gray} Шарафатдинов Камиль 192} +\rhead{\color{gray} ДЗ к 27.01 (\texttt{sol0113 + sol0120})} +\title{ДЗ на 27.01} +\author{Шарафатдинов Камиль БПМИ-192} +\date{билд: \today} + + +% -- Here bet dragons -- +\begin{document}\thispagestyle{empty} + +\maketitle +\clearpage +\setcounter{page}{1} + +\question{Лемма 1}{ + \[ + \int \frac{dx}{x^s} = \frac{1}{(1 - s)x^{s - 1}} + C + \] +} + \[ + \braced{ \frac{1}{(1 - s)x^{s - 1}} + C }' = + -\frac{0 - (1 - s)(s - 2)x^{s - 2}}{(1 - s)^2 x^{2s - 2}} = + \frac{1}{x^s} \qed + \] + +\question{Лемма 2}{ + \[ + \int \frac{dx}{(x^2 + a^2)^2} = \frac{1}{2a^2} \braced{ + \frac{x}{x^2 + a^2} + \frac{1}{a}\arctan\frac{x}{a} + } + C + \] +} + + \begin{align*} + \braced{ + \frac{1}{2a^2} \braced{ + \frac{x}{x^2 + a^2} + \frac{1}{a}\arctan\frac{x}{a} + } + }' = + \frac{1}{2a^2} \braced{ + \frac{x^2 + a^2 - 2x^2}{(x^2 + a^2)^2} + \frac{1}{x^2 + a^2} + } = + \frac{1}{2a^2} \braced{ + \frac{2a^2}{(x^2 + a^2)^2} + } = + \frac{1}{(x^2 + a^2)^2} \qed + \end{align*} + +\question{(seminar0113) 7.3}{ + \[ + \int \frac{dx}{x^4 + 4} = \frac{ + \log | x^2 + 2x + 2 | + 2\arctan(x + 1) - + \log | x^2 - 2x + 2 | + 2\arctan(x - 1) + }{16} + \bar{C} + \] +} + + \[ + x^4 + 4 = (x - (1 + i))(x - (i - 1))(x - (-i - 1))(x - (-i + 1)) = + (x^2 + 2x + 2)(x^2 - 2x + 2) + \] + + \[ + \frac{1}{x^4 + 4} = \frac{Ax + B}{x^2 + 2x + 2} + \frac{Cx + D}{x^2 - 2x + 2} + \] + + \[ + (Ax + B)(x^2 - 2x + 2) + (Cx + D)(x^2 + 2x + 2) \equiv 1 + \] + + С помощью давно забытой китайской техники решения систем уравнений получаем: + \[\begin{cases*} + A = \frac{1}{8}\\ + B = \frac{1}{4}\\ + C = -\frac{1}{8}\\ + D = \frac{1}{4}\\ + \end{cases*}\] + + \[ + \int \frac{1}{x^4 + 4} = + \frac{1}{8}\int \frac{x + 2}{x^2 + 2x + 2} dx + + \frac{1}{8}\int \frac{2 - x}{x^2 - 2x + 2} dx + \] + + \begin{minipage}{0.45\textwidth} + \setlength{\jot}{16pt} + \begin{gather*} + \int \frac{x + 2}{x^2 + 2x + 2} dx =\\ + \int \frac{x + 2}{(x + 1)^2 + 1} dx =\\ + \int \frac{(x + 1) dx}{(x + 1)^2 + 1} + \int \frac{dx}{(x + 1)^2 + 1} =\\ + =\begin{bmatrix} \frac{d(x^2 + 2x + 2)}{2} = (x + 1)dx \end{bmatrix} =\\ + \int \frac{\frac{1}{2}d( (x + 1)^2 + 1 )}{(x + 1)^2 + 1} + \arctan(x + 1) =\\ + = \frac{1}{2}\log | x^2 + 2x + 2 | + \arctan(x + 1) + C_1 + \end{gather*} + \end{minipage} + \begin{minipage}{0.45\textwidth} + \begin{tabular}{|p{\textwidth}} + \setlength{\jot}{16pt} + \begin{gather*} + \int \frac{2 - x}{x^2 - 2x + 2} dx =\\ + -\int \frac{x - 2}{(x - 1)^2 + 1} dx =\\ + -\int \frac{(x - 1) dx}{(x - 1)^2 + 1} + \int \frac{dx}{(x - 1)^2 + 1} =\\ + =\begin{bmatrix} \frac{d(x^2 - 2x + 2)}{2} = (x - 1)dx \end{bmatrix} =\\ + -\int \frac{\frac{1}{2}d( (x - 1)^2 + 1 )}{(x - 1)^2 + 1} + \arctan(x - 1) =\\ + = -\frac{1}{2}\log | x^2 - 2x + 2 | + \arctan(x - 1) + C_2 + \end{gather*} + \end{tabular} + \end{minipage} + + \begin{gather*} + \frac{1}{8}\int \frac{x + 2}{x^2 + 2x + 2} dx + + \frac{1}{8}\int \frac{2 - x}{x^2 - 2x + 2} dx =\\ + =\frac{1}{16}\braced{ + \log | x^2 + 2x + 2 | + 2\arctan(x + 1) - + \log | x^2 - 2x + 2 | + 2\arctan(x - 1) + } + \bar{C} + \end{gather*} + +\question{(seminar0113) 8.b}{ + \[ + \int \frac{x^5 - x}{x^8 + 1}dx = \frac{\sqrt{2}}{8} \braced{ + \log |x^4 - \sqrt{2} x^2 + 1| - \log |x^4 + \sqrt{2} x^2 + 1| + } + \bar{C} + \] +} + + \[ + \int \frac{x^5 - x}{x^8 + 1}dx = + \int \frac{x(x^4 - 1}{x^8 + 1}dx = + \begin{bmatrix} + u = x^2\\ + dx = \frac{du}{2x} + \end{bmatrix} = + \int \frac{x(u^2 - 1)}{u^4 + 1}\frac{du}{2x} = + \frac{1}{2} \int \frac{u^2 - 1}{u^4 + 1} du + \] + \[ + u^4 + 1 = \braced{u^2 + \sqrt{2} u + 1}\braced{u^2 - \sqrt{2} u + 1} + \] + \[ + \frac{u^2 - 1}{u^4 + 1} = + \frac{Au + B}{u^2 + \sqrt{2} u + 1} + + \frac{Cu + D}{u^2 - \sqrt{2} u + 1} + \] + + \[ + (Au + B)(u^2 - \sqrt{2}u + 1) + (Cu + D)(u^2 + \sqrt{2}u + 1) \equiv u^2 - 1 + \] + + Все тем же китайским методом: + \[\begin{cases*} + A = -\frac{\sqrt{2}}{2}\\ + B = -\frac{1}{2}\\ + C = \frac{\sqrt{2}}{2}\\ + D = -\frac{1}{2}\\ + \end{cases*}\] + + \newcommand{\invsq}{\frac{\sqrt{2}}{2}} + \[ + \int \frac{u^2 - 1}{u^4 + 1} du = + \invsq \int \frac{-u - \invsq}{u^2 + \sqrt{2} u + 1} du + + \invsq \int \frac{u - \invsq}{u^2 - \sqrt{2} u + 1} du + \] + + \begin{minipage}{0.45\textwidth} + \setlength{\jot}{16pt} + \begin{gather*} + \int \frac{-u - \invsq}{u^2 + \sqrt{2} u + 1} du =\\ + -\int \frac{u + \invsq}{u^2 + \sqrt{2} u + 1} du =\\ + -\frac{1}{2} \int \frac{d \braced{ u^2 + \sqrt{2} u + 1 }}{u^2 + \sqrt{2} u + 1} =\\ + -\frac{1}{2} \log |u^2 + \sqrt{2} u + 1| + C_1 + \end{gather*} + \end{minipage} + \begin{minipage}{0.45\textwidth} + \begin{tabular}{|p{\textwidth}} + \setlength{\jot}{16pt} + \begin{gather*} + \int \frac{u - \invsq}{u^2 - \sqrt{2} u + 1} du =\\ + \int \frac{u + \invsq}{u^2 - \sqrt{2} u + 1} du =\\ + \frac{1}{2} \int \frac{d \braced{ u^2 - \sqrt{2} u + 1 }}{u^2 - \sqrt{2} u + 1} =\\ + \frac{1}{2} \log |u^2 - \sqrt{2} u + 1| + C_2 + \end{gather*} + \end{tabular} + \end{minipage} + + \[ + \frac{1}{2} \int \frac{u^2 - 1}{u^4 + 1} du = + \frac{\sqrt{2}}{8} \braced{ + \log |u^2 - \sqrt{2} u + 1| - \log |u^2 + \sqrt{2} u + 1| + } + C_3 + \] + + Обратно к $x$: + \[ + \int \frac{x^5 - x}{x^8 + 1}dx = + \frac{\sqrt{2}}{8} \braced{ + \log |x^4 - \sqrt{2} x^2 + 1| - \log |x^4 + \sqrt{2} x^2 + 1| + } + \bar{C} + \] + +\clearpage +\question{(seminar0113) 13}{ + \[ + \int \frac{x \ dx}{(x^2 + 1)(x + 2)(x + 3)} = \frac{1}{20} \braced{ + -8 \log |x + 2| + 6 \log |x + 3| + \log (x^2 + 1) + 2\arctan x + } + \bar{C} + \] +} + \[ + \frac{x}{(x^2 + 1)(x + 2)(x + 3)} = + \frac{Ax + B}{x^2 + 1} + \frac{C}{x + 2} + \frac{D}{x + 3} + \] + + \[ + (Ax + B)(x + 2)(x + 3) + C(x^2 + 1)(x + 3) + D(x^2 + 1)(x + 2) \equiv x + \] + \[\begin{cases*} + A = 0.1\\ + B = 0.1\\ + C = -0.4\\ + D = 0.3\\ + \end{cases*}\] + + \begin{gather*} + \int -\frac{2}{5} \frac{dx}{x + 2} = -\frac{2 \log |x + 2|}{5} + C_1\\[16pt] + \int \frac{3}{10} \frac{dx}{x + 3} = \frac{3 \log |x + 3|}{10} + C_2\\[16pt] + \int \frac{1}{10} \frac{(x + 1) dx}{x^2 + 1} = + \frac{1}{10} \braced{ + \frac{1}{2}\int \frac{2x \ dx}{x^2 + 1} + \int \frac{dx}{x^2 + 1} + } = + \frac{1}{10} \braced{ + \frac{1}{2} \log (x^2 + 1) + \arctan(x) + } + C_3 + \end{gather*} + + \[ + \int \frac{x \ dx}{(x^2 + 1)(x + 2)(x + 3)} = \frac{1}{20} \braced{ + -8 \log |x + 2| + 6 \log |x + 3| + \log (x^2 + 1) + 2\arctan x + } + \bar{C} + \] + +\question{(seminar0120) 2.4}{ + \[ + \int \frac{dx}{x(x^2 + 1)^2} = -\frac{1}{2} \braced{ + -\log (x^2 + 1) + + \frac{1}{x^2 + 1} + + 2\log |x| + } + \bar{C} + \] +} + + \[ + \frac{1}{x(x^2 + 1)^2} = + \frac{Ax + B}{x^2 + 1} + \frac{Cx + D}{(x^2 + 1)^2} + \frac{E}{x} + \] + + \[ + (Ax + B)(x^2 + 1)x + (Cx + D)x + E(x^2 + 1)^2 \equiv 1 + \] + + \[\begin{cases*} + A = -1\\ + B = 0\\ + C = -1\\ + D = 0\\ + E = 1 + \end{cases*}\] + + \begin{gather*} + \int - \frac{x \ dx}{x^2 + 1} = + -\frac{1}{2} \int \frac{2x \ dx}{x^2 + 1} = + -\frac{1}{2} \log (x^2 + 1) + C_1\\[12pt] + \int - \frac{x \ dx}{(x^2 + 1)^2} = + -\frac{1}{2} \int \frac{2x \ dx}{(x^2 + 1)^2} = + \begin{bmatrix} + \displaystyle \int \frac{dx}{x^s} = \frac{1}{(1 - s)x^{s - 1}} + C + \end{bmatrix} = + \frac{1}{2(x^2 + 1)} + C_2\\[12pt] + \int \frac{dx}{x} = \log |x| + C_3 + \end{gather*} + + \[ + \int \frac{dx}{x(x^2 + 1)^2} = + -\frac{1}{2} \log (x^2 + 1) + + \frac{1}{2(x^2 + 1)} + + \log |x| + \bar{C} + \] + +\question{(seminar0120) 11}{ + \[ + \int \frac{dx}{(x^3 + 1)^2} + \] +} + + \[ + \frac{1}{(x^3 + 1)^2} = \frac{1}{(x + 1)^2(x^2 - x + 1)^2} = + \frac{A}{x + 1} + \frac{B}{(x + 1)^2} + \frac{Cx + D}{x^2 - x + 1} + \frac{Ex + F}{(x^2 - x + 1)^2} + \] + + \[ + A(x^2 - x + 1)^2(x + 1) + + B(x^2 - x + 1)^2 + + (Cx + D)(x + 1)^2(x^2 - x + 1) + + (Ex + F)(x + 1)^2 \equiv 1 + \] + \[\begin{cases*} + A = 2/9\\ + B = 1/9\\ + C = -2/9, \ \ + D = 1/3\\ + E = -1/3, \ \ + F = 1/3\\ + \end{cases*}\] + + \begin{align} + \int \frac{2dx}{9(x + 1)} &= \frac{2}{9} \log |x + 1| + C_1 &\\[8pt] + \int \frac{dx}{9(x + 1)^2} & = -\frac{1}{9(x + 1)} + C_2 & + \begin{bmatrix} + \text{Лемма 1} + \end{bmatrix}\\[8pt] + \int \frac{-2x + 3}{9(x^2 - x + 1)}dx &= + -\frac{1}{9} \braced{ + \int \frac{(2x - 1) dx}{x^2 - x + 1} - + \int \frac{2 dx}{\braced{ x - \frac{1}{2} }^2 + \frac{3}{4}} + }\nonumber \\[8pt] + &= + -\frac{1}{9} \braced{ + \log (x^2 - x + 1) - + \frac{4}{\sqrt{3}} \arctan \frac{2x - 1}{\sqrt{3}} + } + C_3\\[8pt] + \frac{1}{3} \int \frac{(1 - x)dx}{(x^2 - x + 1)^2} &= + -\frac{1}{6} \braced{ + \int \frac{(2x - 1)dx}{(x^2 - x + 1)^2} - + \int \frac{dx}{\braced{ \braced{ x - \frac{1}{2} }^2 + \frac{3}{4} }^2} + }\nonumber \\[8pt] + &= + -\frac{1}{6} \braced{ + -\frac{1}{x^2 - x + 1} + + \frac{2}{3} \braced{ + \frac{x}{x^2 - x + 1} + + \frac{2}{\sqrt{3}} \arctan\frac{2x - 1}{\sqrt{3}} + } + } + C_4 + &\begin{bmatrix} + \text{Лемма 1 на левую часть}\\ + \text{Лемма 2 на правую часть} + \end{bmatrix} + \nonumber \\[8pt] + &= \frac{1}{9} \braced{ + \frac{2x - 1}{x^2 - x + 1} - + \frac{2}{\sqrt{3}} \arctan \frac{2x - 1}{\sqrt{3}} + } + C_4 + \end{align} + + \begin{gather*} + \int \frac{1}{(x^3 + 1)^2} = + \int \frac{2dx}{9(x + 1)} + + \int \frac{dx}{9(x + 1)^2} + + \int \frac{-2x + 3}{9(x^2 - x + 1)}dx + + \frac{1}{3} \int \frac{(1 - x)dx}{(x^2 - x + 1)^2} =\\[16pt] + \frac{1}{9} \braced{ + 2\log |x + 1| - \frac{1}{x + 1} + - \log(x^2 - x + 1) + \frac{4}{\sqrt{3}}\arctan \frac{2x - 1}{\sqrt{3}} + - \frac{2x - 1}{x^2 - x + 1} - \frac{2}{\sqrt{3}}\arctan\frac{2x - 1}{\sqrt{3}} + } + C + \end{gather*} +\end{document}
\ No newline at end of file |