Somewhat solved ex2 from dstr hw2

2 files changed, 17 insertions, 1 deletions

diff --git a/Year 1/Discrete math/Homeworks/Homework2.pdf b/Year 1/Discrete math/Homeworks/Homework2.pdf
index 93654b0..c7c89bd 100644
--- a/Year 1/Discrete math/Homeworks/Homework2.pdf
+++ b/Year 1/Discrete math/Homeworks/Homework2.pdf
diff --git a/Year 1/Discrete math/Homeworks/Homework2.tex b/Year 1/Discrete math/Homeworks/Homework2.tex
index 54c19d4..2c88c20 100644
--- a/Year 1/Discrete math/Homeworks/Homework2.tex
+++ b/Year 1/Discrete math/Homeworks/Homework2.tex
@@ -48,7 +48,23 @@
 	& = \sum_{X \subseteq \{ 1, ..., n \}} \prod_{y \in X} y + (n+1)\sum_{X \subseteq \{ 1, ..., n \}} \prod_{y \in X} y \xlongequal{\text{ИП}} (n+1)! + (n+1)(n+1)! = (n+1)!(n+1+1) = (n+2)!
 \end{align*}
 
-\paragraph{\colorbox{yellow}{Задача 2} Решение:} [TODO]
+\paragraph{\colorbox{yellow}{Задача 2} Решение:} Първо ще докажем с индукция по $n \in \mathbb{N}^+$, че за произволно попълване на квадратна таблица с размер $n$, броят на колоните с нечетна сума и броят на редовете с нечетна сума съвпадат по модул 2.
+
+\textbf{База: } $n = 1$, \quad Имаме една колона и един ред, които съвпадат по стойност. Ако редът е нечетен, то и колоната ще е нечетна и обратно.
+
+\textbf{Индукционно предположение: } Допускаме, че е изпълнено за поне едно $n$
+
+\textbf{Индукционна стъпка: } Разглеждаме таблица с размер $n+1$. Разделяме я на таблица с размер $n$ и ред и колона с размери $n+1$ (имат една обща клетка). Твърдението е вярно за $n$-размерната таблица (от ИП) и когато редът и колоната имат еднаква четност.
+
+Разглеждаме ако имат различна четност. Б.О.О. нека бройките в $n$-размерната таблица са нечетни, редът е четен и колоната нечетна. То тогава, четно количество от колоните ще станат нечетни, тоест броят на колоните ще е: нечетно - четно = нечетно. Бройката редове си остава нечетна, и се запазва нечетността.
+
+\hfill
+
+Можем да представим всяка хубава квадратна таблица с размер $n$ като квадратна таблица с размер $n-1$ с произволни стойности, към която са добавени ред и колона с размер $n$, чиито стойности допълват таблицата до хубава (ако сумата на реда е нечетно, слагаме 1-ца за да стане четно и так. нат.).
+
+Знаем, че при произволно попълване, брят на колоните и редовете с нечетни суми съвпада по четност. Аналогично, и броят на колони и редове с четни суми съвпада по четност (квадратна таблица). То тогава, тези добавени редове към $n-1$ таблицата ще имат еднаква четност.
+
+Следователно, броят на хубави таблици е броят начини да се построят $n-1$ размерни таблици, тоест $2^{(n-1)^2}$ ($2^{n-1}$ за всеки ред/колона, общо $n-1$ реда/колони).
 
 \paragraph{\colorbox{yellow}{Задача 3} Решение:} Б.О.О. $G$ е свързан граф (иначе, разглеждаме всяка свързана компонента като отделен граф).