Summary Files Commits Branches @commit @diff @stats
path: root / Year 1 / Discrete math / Homeworks / Homework2.tex
diff options
context:
space:
mode:
Commit1a9b076955b4d303b3117e74e6931c188fe9d5ce (patch)
Author
 Syndamia <kamen.d.mladenov@protonmail.com>
2022-01-15 19:55:02 +0200
Committer
 Syndamia <kamen.d.mladenov@protonmail.com>
2022-01-15 19:55:02 +0200
Files76151b08dce75583754edd8b459e1734a884bc9b /Year 1/Discrete math/Homeworks/Homework2.tex
uni-projects-1a9b076955b4d303b3117e74e6931c188fe9d5ce.tar
uni-projects-1a9b076955b4d303b3117e74e6931c188fe9d5ce.tar.gz
uni-projects-1a9b076955b4d303b3117e74e6931c188fe9d5ce.zip
Parent3b982c559dc03fffec140cad5fb296c539cc479f (diff)
Added dstr hw2 grade and notes
1 files changed, 13 insertions, 3 deletions
-rw-r--r--Year 1/Discrete math/Homeworks/Homework2.tex16
diff --git a/Year 1/Discrete math/Homeworks/Homework2.tex b/Year 1/Discrete math/Homeworks/Homework2.tex
index 5079b69..404f679 100644
--- a/Year 1/Discrete math/Homeworks/Homework2.tex
+++ b/Year 1/Discrete math/Homeworks/Homework2.tex
@@ -38,7 +38,10 @@
\maketitle
-\paragraph{\colorbox{yellow}{Задача 1} Решение:} Ще докажем равенството по индукция за $n$:
+\noindent
+\colorbox{YellowGreen}{\parbox{\textwidth}{\; 85/100 Точки \qquad [Коментарите са под определените места]}}
+
+\paragraph{\colorbox{yellow}{Задача 1} Решение:} Ще докажем равенството по индукция за $n$: \hfill \colorbox{YellowGreen}{25т.}
\begin{align*}
& \textbf{База: } n = 1, \quad S(1) = \sum_{X \subseteq \{ 1 \}} \prod_{y \in X} y = \prod_{y \in \emptyset} y + \prod_{y \in {1}} y = 1 + 1 = 2 \quad (1+1)! = 2! = 2 \\
& \textbf{Индукционно предположение: } S(n) = (n+1)! \text{ е изпълнено за поне едно } n \in \mathbb{N}^+ \\
@@ -58,13 +61,16 @@
Разглеждаме когато $r'$ и $c'$ имат различна четност. Б.О.О. нека колоните и редовете с нечетна сума в $B$ са нечетен брой, $r'$ е с четна сума и $c'$ е с нечетна сума. То тогава, четен брой колони от $B$ ще станат нечетни и броят на колоните ще е: нечетно - четно = нечетно. Аналогично, бройката редове също си остава нечетна. Следователно, взаимната нечетност се запазва.
+\noindent
+\colorbox{RedOrange}{\parbox{\textwidth}{Не е съвсем така. Тук $r'$ и $c'$ се припокриват в долния десен ъгъл. Има значение дали там стои 0 или 1, понеже от това също зависи колко редовете и колоните на $B$ ще си променят четността.}}
+
\hfill
Можем да представим всяка хубава $n$-мерна квадратна таблица като $(n-1)$-мерна квадратна таблица с произволни стойности, към която са добавени ред и колона с размер $n$, чиито стойности допълват редовете и колоните до "хубавост" (за ред с нечетна сума, слагаме 1-ца и т.н.).
Знаем, че при произволно попълване, броят на колоните и редовете с нечетни суми съвпада по четност. То тогава, добавените ред и колона към $(n-1)$-мерната таблица не променят "хубавостта".
-Следователно, броят на хубави таблици е броят начини да се построят $(n-1)$-мерни таблици, тоест $\answerbox{2^{(n-1)^2}}$.
+Следователно, броят на хубави таблици е броят начини да се построят $(n-1)$-мерни таблици, тоест $\answerbox{2^{(n-1)^2}}$. \hfill \colorbox{YellowGreen}{20т.}
\paragraph{\colorbox{yellow}{Задача 3} Решение:} Б.О.О. $G$ е свързан граф (иначе, разглеждаме всяка свързана компонента като отделен граф).
@@ -76,6 +82,9 @@ $X$ е антиклика $\implies \forall x_1, x_2 \in X, x_1 \neq x_2 : (x_1,
Следователно $V \setminus X$ е покриване.
+\noindent
+\colorbox{RedOrange}{\parbox{\textwidth}{Това не е достатъчно ясно описано. Дефиницията за покриване се основава върху ребрата. Тоест трябва да избереш съвсем произволно ребро и да покажеш, че поне единият му край е във $V \setminus X$. Разглеждането на множество от върхове се отклонява от дефиницията на покриване.}}
+
\hfill
\textbf{II.} $V \setminus X$ е покриване $\implies$ $X \subseteq V$ е антиклика
@@ -86,7 +95,7 @@ $V \setminus X$ е покриване $\implies \forall (u, v)\in E : u \in V \s
Обаче по предположение, трябва $x_1 \in V \setminus X \lor x_2 \in V \setminus X$, противоречие!
-Следователно, $X$ е антиклика.
+Следователно, $X$ е антиклика. \hfill \colorbox{YellowGreen}{15т.}
\paragraph{\colorbox{yellow}{Задача 4} Решение:} Допускаме противното, тоест че съществува мост и всички върхове са от четна степен. Б.О.О. нека този мост да бъде $e \in E(G)$ с краища $m_1, m_2 \in V(G)$ и нека компонентите на $G - e$ да са $C_1$ и $C_2$.
@@ -103,5 +112,6 @@ $V \setminus X$ е покриване $\implies \forall (u, v)\in E : u \in V \s
\item Ако реброто $(v_1, v_2) \in V(G)$, то тогава то ще е ребро между компонентите $C_1$ и $C_2$ и $e$ няма да бъде мост.
\end{itemize}
+\hfill \colorbox{YellowGreen}{25т.}
\end{document} \ No newline at end of file