1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
% 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{15 Ноември 2021}
\begin{document}
\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
\textbf{I. случай:} Всичките линии са свързани последователно в една дълга кривяща се линия. Нека да означим каубоите в краищата на $d_n$ с $c_{2021}$ и $c_{2020}$. \colorbox{yellow}{Каубой $c_{2021}$ няма да бъде} \colorbox{yellow}{застрелян}, понеже най-близкия му каубой ще е $c_{2020}$, обаче за $c_{2020}$ най-близкия каубой ще е на другия край на $d_{n-1}$. \newline
\textbf{II. случай:} Всички линии са отделени, тоест имаме само двойки застреляли се каубои. Понеже $2021$ е нечетна цифра, то ние ще имаме един каубой който не може да участва в двойка застреляни. Тоест, точно този \colorbox{yellow}{каубой няма да бъде застрелян}. \newline
\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
\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}
\colorbox{YellowGreen}{5т.}
\paragraph{\colorbox{yellow}{Задача 3.} Решение:} \hfill\newline
\noindent
\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
\textbf{I.} Разглеждаме за рефлективност
\begin{align*}
(a,b)R(a,b) \iff ab = ba \quad \text{вярно от комутативност на умножението на } \mathbb{N} ^ {>0}
\end{align*}
\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*}
\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)
\end{align*}
\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*}
Следователно, всеки клас на еквивалентност е от вида $\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
\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{,} \\
& \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
\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}
|
