Did almost all exercises from discrete math homework

2 files changed, 113 insertions, 0 deletions

diff --git a/Year 1/Discrete math/Homework1.pdf b/Year 1/Discrete math/Homework1.pdf
new file mode 100644
index 0000000..80f362a
--- /dev/null
+++ b/Year 1/Discrete math/Homework1.pdf
diff --git a/Year 1/Discrete math/Homework1.tex b/Year 1/Discrete math/Homework1.tex
new file mode 100644
index 0000000..5a6544e
--- /dev/null
+++ b/Year 1/Discrete math/Homework1.tex
@@ -0,0 +1,113 @@
+% Document MUST be built with XeLaTeX!
+\documentclass[11pt,a4paper]{article}
+
+\usepackage[margin=2.5cm]{geometry}
+
+% Поддръжка на български език
+% Thanks to https://tex.stackexchange.com/a/136926
+\usepackage{fontspec}
+\defaultfontfeatures{Ligatures=TeX}
+\setmainfont{CMU Serif}
+\setsansfont{CMU Sans Serif}
+
+\usepackage[bulgarian,english]{babel}
+
+\usepackage{amsmath}            % Математически символи
+\usepackage{amsfonts}           % Още математически символи
+\usepackage{hyperref}           % Линкове
+\usepackage{cancel}             % Зачертаване
+\usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове
+\usepackage{tikz}
+
+\title{\vspace{-2cm}Домашно №1 по Дискретни Структури на специалност Компютърни
+науки, 2 поток, зимен семестър 2020/2021г.}
+\author{Камен Димитров Младенов, Група 6}
+\date{16 Ноември 2021}
+
+\begin{document}
+
+\maketitle
+
+\paragraph{\colorbox{yellow}{Задача 1.} Решение:}
+
+[TODO]
+
+\paragraph{\colorbox{yellow}{Задача 2.} Решение:}
+
+Нека да наредим $h1, h2, h3, ..., h_n$ в редица с нарастващ ред на височина, тоест $h1 \; h2 \; h3 \; ... \; h_n$. Тогава, за всеки двама съседни човека, дискомфортът (и разликата във височините им) ще е възможно най-малка и следователно общия дискомфорт ще е най-малък.\newline
+
+Общият дискомфорт в тази ситуация ще бъде $|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_1 - h_n| + $минимален дискомфорт на редица $ = |h_1 - h_n| + h_n - h_1$. От $h_n > h_1$, това е еквивалентно на $h_n - h_1 + h_n - h_1 = 2 \left( h_n - h_1 \right)$.\newline
+
+Тоест, минималния общ дискомфорт при нареждане на хора на (кръгла) маса е $2 \left( h_n - h_1 \right)$ и то може да се постигне с подреждане по височина в нарастващ ред по часовниковата (или обратно на часовниковата) стрелка.
+
+\begin{minipage}{0.5\textwidth}
+Пример за това е петима човека с височини $170, 174, 180, 190, 200$. Минималния общ дискомфорт при формулата е $2(200 - 170) = 2 \cdot 30 = 60$. На фигурата минималния общ комфорт е $4 + 6 + 10 + 10 + 30 = 60$.
+\end{minipage}
+\begin{minipage}{0.05\textwidth}
+	\hfill
+\end{minipage}
+\begin{minipage}{0.4\textwidth}
+\begin{tikzpicture}
+	\draw[thick] (0,0) circle (2cm);
+	\draw[fill=lime] (90 : 2) circle (0.5cm) node {$170$};
+	\node at (126 : 2.3) {4};
+	\draw[fill=lime] (162 : 2) circle (0.5cm) node {$174$};
+	\node at (198 : 2.3) {6};
+	\draw[fill=lime] (234 : 2) circle (0.5cm) node {$180$};
+	\node at (270 : 2.3) {10};
+	\draw[fill=lime] (306 : 2) circle (0.5cm) node {$190$};
+	\node at (342 : 2.3) {10};
+	\draw[fill=lime] (18 : 2) circle (0.5cm) node {$200$};
+	\node at (54 : 2.3) {30};
+\end{tikzpicture}
+\end{minipage}
+
+\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
+
+\noindent
+I. Разглеждаме за рефлективност
+\begin{align*}
+	(a,b)R(a,b) \iff ab = ba \quad \text{вярно от комутативност на умножението на } \mathbb{N} ^ {>0}
+\end{align*}
+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. Разглеждаме за транзитивност
+\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)
+\end{align*}
+\colorbox{yellow}{От I., II. и III. следва че $R$ е релация на еквивалентност}\newline
+
+\noindent
+б)
+\begin{align*}
+	(a,b)R(c,d) \iff ad = bc \quad \frac{a}{b} = \frac{c}{d}
+\end{align*}
+Следователно, всеки клас на еквивалентност е от вида $\left\{ (a,b) \mid \frac{a}{b} = r \right\}$ за $r \in \mathbb{Q} ^ {>0}$. То тогава, индекса на еквивалентност е безкрайност ($[R] = \infty$). \newline
+Множеството от всички класове на еквивалентност е \colorbox{yellow}{неизброимо безкрайно}, понеже всеки клас на еквивалентност е безкрайно голям, а множество от безкрайности не е изборимо $\left( \left\{ \left\{ (a,b) \mid \frac{a}{b} = r \right\} \mid r \in \mathbb{Q} ^ {>0} \right\} \subset 2 ^ {\mathbb{N} ^ {>0}  \times \mathbb{N} ^ {>0}} \right)$.
+
+\paragraph{\colorbox{yellow}{Задача 4.} Решение:} \hfill\newline
+
+\noindent
+а) Щом S е крайно, значи съществува
+\begin{align*}
+	& \text{някакво $w$ за което } f(w) = x \text{,} \\
+	& \text{някакво $z$ за което } f(z) = w \quad \left( \;\; f\left( f(z) \right) = x  \;\;\right) \text{,} \\
+	& \text{някакво $s$ за което } f(s) = z \quad \left( \;\; f\left( f\left( f(s) \right) \right) = x \;\;\right) \\
+	& \text{и така натаък. След краен брой подобни образувания, } \\
+	& \text{ще стигнем до някакво } f(y) = t \quad \left( \;\; f\left( f\left( ... \left( f(y) \right) ... \right) \right) = x \;\;\right)
+\end{align*}
+Имайки предвид индуктивната дефиниция, следва че имаме $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}{дивергира към безкрайност} (примерно $g(x) = 2x$ или $g(x) = 2 ^ x$), то нужният брой образувания докато стигнем до $f\left( f\left( ... \left( f(y) \right) ... \right) \right) = x$ ще бъде безкрайно голям. Тоест, нашият $n$ в $f^n(y) = x$ ще бъде безкрайно голям и няма да съществува (без значение колко голямо $n$ вземем, то винаги ще е твърде малко).
+
+\end{document}
\ No newline at end of file