\documentclass[11pt,oneside,a4paper]{article}
\usepackage[margin=2cm]{geometry}
\usepackage{fancyhdr}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{graphicx}
\usepackage{hyperref}

\usepackage{mathtext}
\usepackage[T1,T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,bulgarian]{babel}
\usepackage{setspace}

%\usepackage{array}

%\usepackage[chapter]{algorithm}
%\usepackage[noend]{algpseudocode}
%\usepackage{float}
%\floatname{algorithm}{Алгоритъм}

%\usepackage{myalg}

\setlength{\parindent}{10pt} 
\setlength{\parskip}{1ex}

\begin{document}

\begin{center}
\begin{spacing}{2}
Изпит по Дискретни структури, 16.02.2017г.
\end{spacing}
Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Група:\_\_\_\_\_\_\_ 
\end{center}

\begin{center}
\begin{tabular}{|l|c|c|c|c|c||c|}
\hline
Задача & 1 & 2 & 3 & 4 & 5 & Общо \\ 
\hline
\hline
получени точки & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & \\
\hline
максимум точки &  4 & 6 & 4 & 8 & 8 & 30 \\
\hline
\end{tabular}
\end{center}

\paragraph{Задача 1.} %\mbox{}\\
Дадени са шест естествени числа.\\
Докажете, че разликата на две от тях се дели на 5.

\paragraph{Задача 2.} Колко са различните цикли с дължина $4$ в пълния двуделен граф $K_{3,3}$?\\
Обосновете отговора си.

%Дайте кратко описание на $R'$ и опишете класовете \`{и} на еквивалентност. 

\paragraph{Задача 3.}  В една от групите на специалност Компютърни науки, втори поток, има 25 студенти.
Изпита по алгебра издържали 14 студенти, по ДИС -- 11, по УП -- 14.

   След второ, по-подробно проучване било установено, че
   алгебра и ДИС издържали 8 студенти, алгебра и УП -- 9,
   ДИС и УП -- 7, а 5 студенти си взели и трите изпита.
   Колко студенти са скъсани и по трите учебни дисциплини ?


\paragraph{Задача 4.} Даден е неориентиран граф $G(V,E)$ с върхове $V=\{1,2,\ldots ,10\}$ и
ребра \\
$E=\{(1,2),(1,3),(1,9),(2,4),(2,6),(3,4),(3,5),(4,8),(5,6),(5,7),(6,10),(7,8),(7,9),(8,10),(9,10)\}$.\\
Дайте обоснован отговор на въпросите:

(a - 4 точки) Двуделен ли е графът $G(V,E)$?

(b - 4 точки) Има ли хамилтонов цикъл в $G(V,E)$?

\paragraph{Задача 5.} %\mbox{}
Двоичната функция $f(x,y,z)$ е определена с редицата стойности $f=(10111110)$.

(a - 4 точки) Намерете минимална дизюнктивна нормална форма на $f(x,y,z)$.

(b - 4 точки) Шеферова ли е функцията $f$?

\newpage

\end{document}

\paragraph{Задача 6} Таблицата на $f$ изглежда така:

\begin{displaymath}
\begin{array}{ccc|c}
x & y & z &  f\\
\hline
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0  
\end{array}
\end{displaymath}


Построяваме елементарните конюнкции съгласно теоремата на Бул и ги поставяме в първата колона на таблицата на импликантите по-долу. 
%Импликантите ще записваме като 4-буквени поредици от символите $0,1,e$, като $e$ съответства на липсваща промелива, $0$ на отрицание на съответната промелива, а $1$ на промелива без отрицание. 

След пресмятане на всички импликанти получаваме (със $*$ са отбелязани погълнатите имликанти):

\begin{displaymath}
\begin{array}{c|c|c}
 I_3  &  I_2 & \\
\hline
\overline{x}\overline{y}\overline{z}* & \overline{x}\overline{y} &  \\
\overline{x}\overline{y}z* & \overline{x}\overline{z}  & \\
\overline{x}y\overline{z}* & \overline{y}z \\
x\overline{y}z* & y\overline{z} \\
xy\overline{z}* &   \\
\end{array}
\end{displaymath}

Сега строим таблица в която отбелязваме коя проста имликанта покрива единица на $f$:

\begin{displaymath}
\begin{array}{c|c|c|c|c|c|c|c}
 N_f & \overline{x}\overline{y} & \overline{x}\overline{z} & \overline{y}z & y\overline{z}  \\
\hline
000 & *    & *    &      &       \\
001 & *    &      &  *   &      \\
010 &      & *    &      &  *    \\
101 &      &      &  *   &       \\
110 &      &      &      &  *   
\end{array}
\end{displaymath}
 
Единиците $101$ и $110$ са покрити от единствените импликанти 
$\overline{y}z$ и $y\overline{z}$, следователно те са задължителни. 

Те двете не покриват единствено единицата $000$, 
можем да я покрием с коя да е от импликантите 
$\overline{x}\overline{y}$ и $\overline{x}\overline{z}$. 
Те са с еднакъв брой букви, следователно има две минимални ДНФ:

\begin{align*}
f(x,y,z) & = \overline{x}\overline{y} \lor \overline{y}z \lor y\overline{z}\\
f(x,y,z) & = \overline{x}\overline{z} \lor \overline{y}z \lor y\overline{z}\\
\end{align*}



\subsection*{Решения:}

\paragraph{\mbox{Задача 1.}} \mbox{}

Означаваме с $f(n)=n^3+2n$ изразът, който ни интерсува.

Първи начин (индукция): 

Очевидно $f(0)=0$ се дели на 3.
Нека $f(n)$ се дели на 3, тогава $f(n+1)=(n+1)^3+2(n+1)=n^3+3n^2+3n+1+2n+2=n^3+2n+3(n^2+n+1)$.
Получаваме $f(n+1)=f(n)+3(n^2+n+1)$, което се дели на 3, защото двете събираеми се делят на 3.

Втори начин (делимост):

Разглеждаме 3 възможни случая за $n$, в зависимост от остатъка при делене на 3.

(1) $n=3k$, тогава $f(n)=3k(n^2+2)$ се дели на 3.

(2) $n=3k+1$, тогава $f(n)=27k^3+27k^2+9k+1+6k+2$ се дели на 3.

(3) $n=3k+2$, тогава $f(n)=27k^3+54k^2+36k+8+6k+4$ се дели на 3.

\paragraph{\mbox{Задача 2.}} \mbox{}

%$R'$ е релация на еквивалентност, тъй като е рефлексивна, симетрична и транзитивна.

Да вземем произволно цяло число $x$ и да определим класа му на еквивалентност, тоест
кои други цели числа са свързани с него относно релацията $R'$:

(1) От $R \subset R'$ следва, че $(x,x+5)\in R'$, тоест $x+5 \in [x]$. 

(2) Понеже $R'$ е рефлексивно затваряне, следва че $x \in [x]$.

(3) Понеже $R'$ е симетрично затваряне, следва че $(y+5,y)\in R'$ за произволно $y$, 
заместваме $x=y+5$ и получаваме $x-5 \in [x]$.

(4) $R'$ е транзитивно затваряне. Ще докажем по индукция, че $x+5k \in [x]$ за всяко естествено $k$:

От (2) следва, че $x+5\times 0 \in [x]$.

Нека $(x,x+5k) \in R'$. От (1) $(x+5к,x+5k+5)\in R'$, и от транзитивноста на $R'$ следва
$(x,x+5(k+1))\in R'$. 

Аналогично доказваме, че $x-5k \in [x]$ за всяко естествено $k$.

Получаваме, че класът на еквивалентност $[x]$ се състои от всички цели числа, 
които при делене на 5 имат същия остатък, както и $x$.

Има 5 различни такива класове на еквивалентност -- множествата от цели числа, даващи съответно остатъци 0, 1, 2, 3 и 4 при делене на 5.



\paragraph{\mbox{Задача 3.}} \mbox{}

В множеството $I_{10}$ има точно 5 четни и точно 5 нечетни числа.

Но $A$ има 6 елемента, то ще съдържа поне едно четно число $a$ и поне едно нечетно число $b$
Сумата на двете $a+b$ е нечетна.


\paragraph{\mbox{Задача 4.}} \mbox{}

(a) Ще записваме съкратено една пермутация $f$ като редица от стойностите $(f(1), f(2) \ldots f(n))$.

При този съкратен запис $(2,3,4,1)$ означава $f(1)=2, f(2)=3, f(3)=4, f(4)=1$. 
Лесно се проверява, че  $(2,3,4,1)$ е една от цикличните пермутации при $n=4$.

Цикличните пермутации при $n=4$ са общо 6 на брой, те са:

$(2,3,4,1)$, $(2,4,1,3)$, $(3,4,2,1)$, $(3,1,4,2)$, $(4,3,1,2)$, $(4,1,2,3)$

(b) Броят на цикличните пермутации за произволно $n$ е $(n-1)!$ (всички пермутации са $n!$).

Има различни начини да се уверим в това, ето един от тях:

Да си представим, че турист иска да посети $n$ музея за един ден.
В началото на разходката си той посещава музей 1, който е близо до хотела, в който е отседнал. 
След разглеждането на всеки музей, туристът прави преход до друг музей, като всички посетени музеи са различни и накрая туристът се връща уморен в хотела. 

Нека с $a_0=a_n=1$ означим началния/крайния пункт на разходката на туриста (музей номер 1, или хотела на туриста).
Нека $a_i$ е номерът на музея, посетен след $i$-тия преход.

Множеството от двойки $(a_i,a_{i+1}), 0\le i <n$ е функция, да я означим с $f$.
Лесно се проверява, че $f:I_n\to I_n$ е циклична пермутация, а всяка циклична пермутация съответства на разходка на туриста из музеите.

Да преброим различните разходки. 
При първия преход търистът може да избере някой от $n-1$ непосетени музея.
При втория трябва да посети някой от оставащите $n-2$ непосетени музея. 
След това трябва да стигне до някой от оставащите $n-3$ непосетени музея и т.н., докато се върне в хотела. 

Броят на различните разходки ще е $(n-1)(n-2)\ldots 2.1=(n-1)!$, толкова са и цикличните пермутации на $n$ елемента.


\paragraph{\mbox{Задача 5.}} \mbox{}

(a) Броят на редиците е броят на комбинаторните конфигурации с повторение, без да отчитаме наредбата.

Избираме $n$ елемента от $k$ типа (цвята). 
$x_1$ е броят на елементите от първи тип (цвят), $x_2$ -- от втория цвят и т.н.

Знаем от лекции, че конкретна редица $x_1,x_2,\ldots,x_k$ биективно съответства на символен низ
от редуващи се '*' и '|'. 
Низът започва с $x_1$ звездички, следва разделител '|', после $x_2$ звезди, разделител и т.н.
Дължината на низа е $n+k-1$, броят на разделите е $k-1$.

Броят на редиците е $\binom{n+k-1}{k-1}$, 
точно колкото са начините да разположим $k-1$ разделителя в низ с дължина $n+k-1$.

(b) В този случай пак можем да съпоставим на всяка редица низ от '*' и '|', 
но искаме между всеки два разделителя да има поне една '*' (също и в началото и края на низа има звезда).

Нека разгледаме по-къс низ, като от всеки интервал звездички махнем една.
На всяка редица  $x_1,x_2,\ldots,x_k$ съпоставяме редица  $y_1,y_2,\ldots,y_k$, такава че $y_i=x_i-1$.
От условието $x_i>0$ следва $y_i\ge 0$.

Търсим броя на редиците $y_1,y_2,\ldots,y_k$.
Сумата на числата $\displaystyle\sum_{i=1}^{k}y_i=n-k$ и $y_i\ge 0$. 
Пак търсим броя на конфигурациите без наредба и с повторение.
Сега броят на елементите е $n-k$, а броят на конфигурациите е $\binom{n-1}{k-1}$.

В терминологията на низ от звездички и чертички, след изтриването на звездичка във всеки интервал,
низът се скъсява (изтрили сме точно $k$ звезди). 
Дължината на низа става $n-1$, броят на '|' остава $k-1$, 
а броят начини по които можем да разположим чертичките в низа е $\binom{n-1}{k-1}$.



\end{document}


