diff options
Updated formatting and date
2 files changed, 12 insertions, 12 deletions
| -rw-r--r-- | Year 1/Discrete math/Homework1.pdf | bin | 34662 -> 34125 bytes | |||
| -rw-r--r-- | Year 1/Discrete math/Homework1.tex | 24 |
diff --git a/Year 1/Discrete math/Homework1.pdf b/Year 1/Discrete math/Homework1.pdf Binary files differindex 0ea2b7f..b4ea5a7 100644 --- a/Year 1/Discrete math/Homework1.pdf +++ b/Year 1/Discrete math/Homework1.pdf diff --git a/Year 1/Discrete math/Homework1.tex b/Year 1/Discrete math/Homework1.tex index 914931e..b6b8bcb 100644 --- a/Year 1/Discrete math/Homework1.tex +++ b/Year 1/Discrete math/Homework1.tex @@ -22,7 +22,7 @@ \title{\vspace{-2cm}Домашно №1 по Дискретни Структури на специалност Компютърни науки, 2 поток, зимен семестър 2020/2021г.} \author{Камен Димитров Младенов, Група 6} -\date{16 Ноември 2021} +\date{15 Ноември 2021} \begin{document} @@ -32,11 +32,11 @@ Нека от всеки каубой да начертаем права линия до най-близкия друг каубой, които линии да означим с $d_1, d_2, d_3, ..., d_n$ където $d_1 < d_2 < d_3 < ... < d_n$. \newline -I. случай: Всичките линии са свързани последователно в една дълга кривяща се линия. Нека да означим каубоите в краищата на $d_n$ с $c_{2021}$ и $c_{2020}$. Каубой $c_{2021}$ няма да бъде застрелян, понеже най-близкия му каубой ще е $c_{2020}$, обаче за $c_{2020}$ най-близкия каубой ще е на другия край на $d_{n-1}$. \newline +\textbf{I. случай:} Всичките линии са свързани последователно в една дълга кривяща се линия. Нека да означим каубоите в краищата на $d_n$ с $c_{2021}$ и $c_{2020}$. \colorbox{yellow}{Каубой $c_{2021}$ няма да бъде} \colorbox{yellow}{застрелян}, понеже най-близкия му каубой ще е $c_{2020}$, обаче за $c_{2020}$ най-близкия каубой ще е на другия край на $d_{n-1}$. \newline -II. случай: Всички линии са отделени, тоест имаме само двойки застреляли се каубои. Понеже $2021$ е нечетна цифра, то ние ще имаме един каубой който не може да участва в двойка застреляни. Тоест, точно този каубой няма да бъде застрелян. \newline +\textbf{II. случай:} Всички линии са отделени, тоест имаме само двойки застреляли се каубои. Понеже $2021$ е нечетна цифра, то ние ще имаме един каубой който не може да участва в двойка застреляни. Тоест, точно този \colorbox{yellow}{каубой няма да бъде застрелян}. \newline -III. случай: Някои линиии са свързани в кривящи се линии, други са отделени. Всяка кривяща се линия може да се сведе до I. случай, следователно има поне един незастрелян каубой. +\textbf{III. случай:} Някои линиии са свързани в кривящи се линии, други са отделени. Всяка кривяща се линия може да се сведе до I. случай, следователно има \colorbox{yellow}{поне един незастрелян} \colorbox{yellow}{каубой}. \paragraph{\colorbox{yellow}{Задача 2.} Решение:} @@ -44,7 +44,7 @@ III. случай: Някои линиии са свързани в кривящ Общият дискомфорт в тази ситуация ще бъде $|h_1 - h_2| + |h_2 - h_3| + ... + |h_{n-1} - h_n|$. Понеже височините на хората са в нарастващ ред, то това е еквивалентно на $(h_2 - h_1) + (h_3 - h_2) + ... + (h_n - h_{n-1}) = \cancel{h_2} - h_1 + \cancel{h_3} - \cancel{h_2} + ... + h_n - \cancel{h_{n-1}} = h_n - h_1$.\newline -Обаче, ние искаме да ги наредим в кръг, което означава че към общия дискомфорт на нареждането в редица трябва да добавим и дискомфортът между първия и последния. Тоест, $h_n - h_1 + |h_1 - h_n|$. От $h_n > h_1$, следва че това е еквивалентно на $h_n - h_1 + h_n - h_1 = 2 \left( h_n - h_1 \right)$.\newline +Обаче, ние искаме да ги наредим в кръг, което означава че към общия дискомфорт на нареждането в редица трябва да добавим и дискомфортът между първия и последния. Тоест, $h_n - h_1 + |h_1 - h_n|$. От $h_n > h_1$, следва че това е еквивалентно на $h_n - h_1 + h_n - h_1 = \colorbox{yellow}{$2 \left( h_n - h_1 \right)$}$.\newline \begin{minipage}{0.5\textwidth} Пример за минимален общо дискомфорт е нареждане по височина на петима човека с височини $170, 174, 180, 190, 200$. Минималния общ дискомфорт при формулата е \newline $2 \cdot (200 - 170) = 2 \cdot 30 = 60$, равен с този от фигурата: $4 + 6 + 10 + 10 + 30 = 60$. @@ -71,19 +71,19 @@ III. случай: Някои линиии са свързани в кривящ \paragraph{\colorbox{yellow}{Задача 3.} Решение:} \hfill\newline \noindent -а) Нека $a,b,c,d,e,f \in \mathbb{N} ^ {>0}$ и $(a,b),(c,d),(e,f) \in \mathbb{N} ^ {>0} \times \mathbb{N} ^ {>0}$ \newline +\textbf{а)} Нека $a,b,c,d,e,f \in \mathbb{N} ^ {>0}$ и $(a,b),(c,d),(e,f) \in \mathbb{N} ^ {>0} \times \mathbb{N} ^ {>0}$ \newline \noindent -I. Разглеждаме за рефлективност +\textbf{I.} Разглеждаме за рефлективност \begin{align*} (a,b)R(a,b) \iff ab = ba \quad \text{вярно от комутативност на умножението на } \mathbb{N} ^ {>0} \end{align*} -II. Разглеждаме за симетричност +\textbf{II.} Разглеждаме за симетричност \begin{align*} & (a,b)R(c,d) \iff ad = bc \qquad\qquad (c,d)R(a,b) \iff cb = da \\ & bc = cb \text{ вярно от комутативност на умножението на } \mathbb{N} ^ {>0} \implies ad = da \end{align*} -III. Разглеждаме за транзитивност +\textbf{III.} Разглеждаме за транзитивност \begin{align*} & (a,b)R(c,d) \iff ad = bc \implies \frac{d}{c} = \frac{b}{a} \qquad\qquad (c,d)R(e,f) \iff cf = de \implies \frac{f}{e} = \frac{d}{c} \\ & \implies \frac{f}{e} = \frac{b}{a} \quad af = be \iff (a,b)R(e,f) @@ -91,7 +91,7 @@ III. Разглеждаме за транзитивност \colorbox{yellow}{От I., II. и III. следва че $R$ е релация на еквивалентност}\newline \noindent -б) +\textbf{б)} \begin{align*} (a,b)R(c,d) \iff ad = bc \quad \frac{a}{b} = \frac{c}{d} \end{align*} @@ -101,7 +101,7 @@ III. Разглеждаме за транзитивност \paragraph{\colorbox{yellow}{Задача 4.} Решение:} \hfill\newline \noindent -а) Щом S е крайно, значи съществува +\textbf{а)} Щом S е крайно, значи съществува \begin{align*} & \text{произволно $w$ за което } f(w) = x \text{,} \\ & \text{произволно $z$ за което } f(z) = w \quad \left( \;\; f\left( f(z) \right) = x \;\;\right) \text{,} \\ @@ -112,7 +112,7 @@ III. Разглеждаме за транзитивност Имайки предвид индуктивната дефиниция, следва че имаме $f^n(y) = x$ за някакво $n > 1$. Обаче, по дефиниция, обратната фунцкяи $f^{-1}(y) = x$. \newline Тоест, \colorbox{yellow}{$f^n(y) = f^{-1}(y)$ за някакво $n > 1$}. \newline \noindent -б) Ако $g: \mathbb{N} \rightarrow \mathbb{N}$ \colorbox{yellow}{дивергира към безкрайност} $\left( \text{примерно } g(x) = \left\{\begin{array}{cc} +\textbf{б)} Ако $g: \mathbb{N} \rightarrow \mathbb{N}$ \colorbox{yellow}{дивергира към безкрайност} $\left( \text{примерно } g(x) = \left\{\begin{array}{cc} x + 1 & x \geq 1 \\ x & x < 1 \end{array}\right. \right)$ то нужният брой образувания докато стигнем до $f\left( f\left( ... \left( f(y) \right) ... \right) \right) = x$ ще бъде безкрайно голям. Тоест, нашият $n$ в $f^n(y) = x$ ще бъде безкрайно голям и няма да съществува. |