diff options
Somewhat improved working on ex2 dstr hw2
1 files changed, 5 insertions, 5 deletions
| -rw-r--r-- | Year 1/Discrete math/Homeworks/Homework2.tex | 10 |
diff --git a/Year 1/Discrete math/Homeworks/Homework2.tex b/Year 1/Discrete math/Homeworks/Homework2.tex index 2c88c20..5079b69 100644 --- a/Year 1/Discrete math/Homeworks/Homework2.tex +++ b/Year 1/Discrete math/Homeworks/Homework2.tex @@ -54,17 +54,17 @@ \textbf{Индукционно предположение: } Допускаме, че е изпълнено за поне едно $n$ -\textbf{Индукционна стъпка: } Разглеждаме таблица с размер $n+1$. Разделяме я на таблица с размер $n$ и ред и колона с размери $n+1$ (имат една обща клетка). Твърдението е вярно за $n$-размерната таблица (от ИП) и когато редът и колоната имат еднаква четност. +\textbf{Индукционна стъпка: } Разглеждаме таблица $A$ с размер $n+1$. Разделяме я на таблица $B$ с размер $n$ и ред $r'$ и колона $c'$ с размери $n+1$ (имат една обща клетка). Твърдението е вярно за $B$ (от ИП) и за $r'$ и $c'$, когато имат еднаква четност. -Разглеждаме ако имат различна четност. Б.О.О. нека бройките в $n$-размерната таблица са нечетни, редът е четен и колоната нечетна. То тогава, четно количество от колоните ще станат нечетни, тоест броят на колоните ще е: нечетно - четно = нечетно. Бройката редове си остава нечетна, и се запазва нечетността. +Разглеждаме когато $r'$ и $c'$ имат различна четност. Б.О.О. нека колоните и редовете с нечетна сума в $B$ са нечетен брой, $r'$ е с четна сума и $c'$ е с нечетна сума. То тогава, четен брой колони от $B$ ще станат нечетни и броят на колоните ще е: нечетно - четно = нечетно. Аналогично, бройката редове също си остава нечетна. Следователно, взаимната нечетност се запазва. \hfill -Можем да представим всяка хубава квадратна таблица с размер $n$ като квадратна таблица с размер $n-1$ с произволни стойности, към която са добавени ред и колона с размер $n$, чиито стойности допълват таблицата до хубава (ако сумата на реда е нечетно, слагаме 1-ца за да стане четно и так. нат.). +Можем да представим всяка хубава $n$-мерна квадратна таблица като $(n-1)$-мерна квадратна таблица с произволни стойности, към която са добавени ред и колона с размер $n$, чиито стойности допълват редовете и колоните до "хубавост" (за ред с нечетна сума, слагаме 1-ца и т.н.). -Знаем, че при произволно попълване, брят на колоните и редовете с нечетни суми съвпада по четност. Аналогично, и броят на колони и редове с четни суми съвпада по четност (квадратна таблица). То тогава, тези добавени редове към $n-1$ таблицата ще имат еднаква четност. +Знаем, че при произволно попълване, броят на колоните и редовете с нечетни суми съвпада по четност. То тогава, добавените ред и колона към $(n-1)$-мерната таблица не променят "хубавостта". -Следователно, броят на хубави таблици е броят начини да се построят $n-1$ размерни таблици, тоест $2^{(n-1)^2}$ ($2^{n-1}$ за всеки ред/колона, общо $n-1$ реда/колони). +Следователно, броят на хубави таблици е броят начини да се построят $(n-1)$-мерни таблици, тоест $\answerbox{2^{(n-1)^2}}$. \paragraph{\colorbox{yellow}{Задача 3} Решение:} Б.О.О. $G$ е свързан граф (иначе, разглеждаме всяка свързана компонента като отделен граф). |