diff options
Added grade and comments to discrete math homework1
2 files changed, 34 insertions, 1 deletions
| -rw-r--r-- | Year 1/Discrete math/Homework1.pdf | bin | 34125 -> 37937 bytes | |||
| -rw-r--r-- | Year 1/Discrete math/Homework1.tex | 35 |
diff --git a/Year 1/Discrete math/Homework1.pdf b/Year 1/Discrete math/Homework1.pdf Binary files differindex b4ea5a7..d7abc64 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 b6b8bcb..108cc0b 100644 --- a/Year 1/Discrete math/Homework1.tex +++ b/Year 1/Discrete math/Homework1.tex @@ -28,6 +28,9 @@ \maketitle +\noindent +\colorbox{RedOrange}{\parbox{\textwidth}{\; 45/100 Точки \qquad [Коментарите са под определените места]}} + \paragraph{\colorbox{yellow}{Задача 1.} Решение:} Нека от всеки каубой да начертаем права линия до най-близкия друг каубой, които линии да означим с $d_1, d_2, d_3, ..., d_n$ където $d_1 < d_2 < d_3 < ... < d_n$. \newline @@ -38,16 +41,29 @@ \textbf{III. случай:} Някои линиии са свързани в кривящи се линии, други са отделени. Всяка кривяща се линия може да се сведе до I. случай, следователно има \colorbox{yellow}{поне един незастрелян} \colorbox{yellow}{каубой}. +\noindent +\colorbox{RedOrange}{\parbox{\textwidth}{Според мен не е очевидно, че картината винаги може да се раздели на няколко подфигури от 1-ви случай и няколко от 2-ри случай. Това трябва да се докаже по-подробно. +Например може да тръгнеш от произволен връх и да покажеш, че или той се стреля взаймно +с друг каубой и никой друг не стреля по тях (2-ри случай), или се намира някъде във фигура от 1-ви случай. След това от нечетния брой каубои става ясно, че ще има поне една фигура от 1-ви случай и това решава задачата.}} + +\colorbox{YellowGreen}{10т.} + \paragraph{\colorbox{yellow}{Задача 2.} Решение:} Нека да наредим $h1, h2, h3, ..., h_n$ в редица с нарастващ ред на височина, тоест $h1 \; h2 \; h3 \; ... \; h_n$. Тогава, за всеки двама съседни човека, дискомфортът ще бъде възможно най-малкък и следователно общият дискомфорт също ще е най-малък. +\noindent +\colorbox{RedOrange}{\parbox{\textwidth}{Не е ясно какво се има впредвид под дискомфорт на човек. Също май не е вярно, че дискомфортът на всеки отделен човек ще е възможно най-малък. Ако имаш впредвид сборът от дискомфортът на двамата му съседи, то си представи, че имам човек x, за когото първите двама по-високи от него са почти на същата височина, а предходният по височина е значително по-нисък. Тогава за него би било по-изгодно да е заобиколен от двамата високи, но глобално това не води до оптимално решение.}} + Общият дискомфорт в тази ситуация ще бъде $|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 = \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$. + +\noindent +\colorbox{RedOrange}{\parbox{\textwidth}{Това е валиден пример, но трябва да се докаже, че наистина не може да се постигне по-нисък дискомфорт от дадения.}} \end{minipage} \begin{minipage}{0.05\textwidth} \hfill @@ -68,6 +84,8 @@ \end{tikzpicture} \end{minipage} +\colorbox{YellowGreen}{5т.} + \paragraph{\colorbox{yellow}{Задача 3.} Решение:} \hfill\newline \noindent @@ -95,9 +113,16 @@ \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}$. \newline +Следователно, всеки клас на еквивалентност е от вида $\left\{ (a,b) \mid \frac{a}{b} = r \right\}$ за $r \in \mathbb{Q} ^ {>0}$. + +\noindent +\colorbox{Goldenrod}{\parbox{\textwidth}{Това е така, но е добре да кажеш по-подробно защо множеството е изброимо (например $\mathbb{Q} ^ {>0}$ е безкрайно подмножество на клас $\mathbb{Q}$, а на $\mathbb{Q}$ еквивалентност сме показвали, е че изброимо).}} + +\noindent Множеството от всички класове на еквивалентност е \colorbox{yellow}{изброимо безкрайно}. Всеки клас на еквивалентност е изброим $\left( \left\{ (a,b) \mid \frac{a}{b} = r \right\} \subset \mathbb{N} ^ 2 \right)$ и можем да го изброим чрез всички на кратни на прости числа (които вече не са използвани). Тоест, за първия клас на еквивалентност можем да използваме всяко второ число, за втория клас - всяко трето число (като пропускаме тези, които са кратни и на 2) и така нататък. +\colorbox{YellowGreen}{25т.} + \paragraph{\colorbox{yellow}{Задача 4.} Решение:} \hfill\newline \noindent @@ -112,9 +137,17 @@ Имайки предвид индуктивната дефиниция, следва че имаме $f^n(y) = x$ за някакво $n > 1$. Обаче, по дефиниция, обратната фунцкяи $f^{-1}(y) = x$. \newline Тоест, \colorbox{yellow}{$f^n(y) = f^{-1}(y)$ за някакво $n > 1$}. \newline \noindent +\colorbox{RedOrange}{\parbox{\textwidth}{Това важи само за фиксирания елемент x. Ние искаме степен n, която да е валидна за всички x от S едновременно.}} + +\noindent \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$ ще бъде безкрайно голям и няма да съществува. +\noindent +\colorbox{RedOrange}{\parbox{\textwidth}{$f$ не е биекция! За кое x е вярно $f(x) = 1$? Щом f не е сюрекция, то не може да е и биекция. Ако искаш биекция в $\mathbb{N}$, която да не се затваря, то един вариант е $g(2k) = 2k-2 за k > 0; g(0) = 1; g(2k+1) = g(2k+3)$}} + +\colorbox{YellowGreen}{5т.} + \end{document}
\ No newline at end of file |
