\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{verbatim}

%\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}
Писмен изпит по ДС за КН 1-ви поток, 13.02.2015г.
\end{spacing}
Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Група:\_\_\_\_\_\_\_ 
\end{center}

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

\emph{Забележка:} За отлична оценка са достатъчни 100 точки!

%\paragraph{Задача 1} Нека $n \in N^{+}$ и $a_n = 2 + 8 + 24  + \ldots + n2^n$. Намерете формула за $a_n$, чрез дефиниране на линейно рекурентно уравнение за $a_n$ и го решете, използвайки подходящи начални условия.

\paragraph{Задача 1} Нека $n \in N^{+}$ и $U = \{1, 2,\ldots, 2n\}$. Да се докаже, че за всяко множество $A \subset U$, за което $|A| = n + 1$, съществува $k\in U, \; k < 2n$, 
такова че $k\in A$ и $(k + 1) \in A$.

\paragraph{Задача 2} Точките от една окръжност са оцветени в два цвята. Докажете, че
           съществува равнобедрен триъгълник с едноцветни върхове, лежащи на окръжността.

\emph{Упътване:} Впишете правилен петоъгълник в окръжността и разсъждавайте за цветовете на върховете му.


\paragraph{Задача 3}  Нека $G(V,E)$ е краен неориентиран граф и $v \in V$ e негов срязващ връх (след отстраняването на $v$ и ребрата, инцидентни с него, броят на свързаните компоненти на $G$ се увеличава). Нека $G_1$ е графът, получен от $G$ чрез отстраняване на $v$ и ребрата, инцидентни с него. Докажете, че допълнителният граф на $G_1$ е свързан.

\begin{comment}
\paragraph{Задача 6} Нека графът $B_n$ e $n$-мерният двоичен куб 
(върховете са всички $n$-мерни двоични вектори, два върха са свързани, ако векторите им се различават на точно една позиция). Дайте обосновани отговори на следните въпроси: 

а) Колко ребра има най-късият път от връх $\alpha=00\ldots 0$ до връх $\beta=11\ldots 1$? 

б) Какъв е броят на всички най-кратки пътища от връх $\alpha$ до връх $\beta$?  
\end{comment}

\paragraph{Задача 4} Напишете съвършената ДНФ и полинома на Жегалкин на булевата функция\\
 $f(x,y,z)=(x\to y)\land (x\oplus z)$.

\paragraph{Задача 5} Докажете, че съвършената ДНФ на двоичната функция \\
$f(x_1,x_2\ldots x_n) = x_1 \oplus x_2 \oplus \ldots \oplus x_n$ е единственото представяне на тази функция чрез ДНФ.

\paragraph{Задача 6} Да се намерят всички минимални дизюнктивни нормални форми на двоичната функция $f(x,y,z)$ с единично множество $N_f=\{0, 1, 2, 5, 6\}$.

%\end{document}

\newpage

\paragraph{Примерни решения}


\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*}


\end{document}
\paragraph{Задача 1} Да означим израза с $f(n)=2^{3n}-7n-1$. 

Очевидно $f(0)=0$ се дели на $49$.

Нека допуснем, че $f(n)$ се дели на $49$.
\begin{align*}
f(n+1)&=2^{3(n+1)}-7(n+1)-1\\
      &=2^{3n+3}-7n-7-1\\
      &=2^{3}2^{3n}-7n-8\\
      &=8.2^{3n}-8(7n+1)+8(7n+1)-7n-8\\
      &=8(2^{3n}-7n-1)+56n+8-7n-8\\
      &=8f(n)+49n
\end{align*}

Представихме $f(n+1)$  като сума на $8f(n)$ и $49n$. Двете събираеми се делят на $49$, следователно и $f(n+1)$ се дели на $49$.

Получихме, че ако $f(n)$ се дели на $49$, то $f(n+1)$ също се дели на $49$.

От принципа на индукцията следва, че за всяко $n\geq 0$ изразът $f(n)=2^{3n}-7n-1$ се дели на $49$.

\paragraph{Задача 2} Оставяме на читателя тази лесна задача $\ldots$

\paragraph{Задача 3} Нека $f, g$ и $h$ са функции от $F$.

$\forall x\in \{a,b,c,d\} \quad f(x) \equiv f(x) \pmod 2$, следователно $fRf$, тоест $R$ е рефлексивна. 

$\forall x\in \{a,b,c,d\} \quad (f(x) \equiv g(x) \pmod 2) \to (g(x) \equiv f(x) \pmod 2)$, следователно $fRg \to gRf$, тоест $R$ е симетрична. 

$\forall x\in \{a,b,c,d\} \quad ((f(x) \equiv g(x) \pmod 2) \land (g(x) \equiv h(x) \pmod 2)) \to (f(x) \equiv h(x) \pmod 2)$, 
следователно $(fRg)\land(gRh) \to fRh$, тоест $R$ е транзитивна. 

От трите разсъждения по-горе следва, че $R$ е релация на еквивалентност.

Нека съпоставим на $f\in F$ редицата $B(f)=\alpha_1 \alpha_2 \alpha_3 \alpha_4$,
където $\alpha_1=f(a) \pmod 2, \; \alpha_2=f(b) \pmod 2, \; \alpha_3=f(c) \pmod 2, \; \alpha_4=f(d) \pmod 2$.

Очевидно $B(f)$ е редица от нули и единици. Произволни $f\in F, \; g\in F$ имат съвпадащи редици $B(f)$ и $B(g)$ точно когато $fRg$. 

Следователно изображението $B$ съпоставя една и съща булева редица
$\alpha_1 \alpha_2 \alpha_3 \alpha_4$ на всички функции от един клас
на еквивалентност на $R$ и различни булеви редици на функции от различни класове.

Изображението $B$ поражда биекция между класовете на еквивалентност на $R$ и булевите редици с дължина 4, 
следователно броят на класовете е $2^4$.

Броят на функциите $f\in F$ е $7^4$ (това са всички редици от 4 елемента, като всеки елемент има 7 възможни стойности). 
 

\paragraph{Задача 4} Нека с $A_k$ означим множеството от поредици, съвпадащи с отключващата поредица на точно $k$ места.

Очевидно ще можем да отключим повредения сейф само с поредица от $A_4, A_5, A_6$ или $A_7$ и тия множества не се пресичат.

Следователно броят на отключващите поредици е $n=|A_4|+|A_5|+|A_6|+|A_7|$.

Броят на елементите на $A_4$ е $\binom{7}{4}9^3$, защото можем по $\binom{7}{4}$ начина да изберем 4-те позиции, 
за които знаем кода, и по $9^3$ начина да сбъркаме в останалите 3 позиции.

Аналогично $A_5$ има $\binom{7}{5}9^2$ елемента, $A_6$ има $\binom{7}{6}9$ елемента, $A_7$ има $\binom{7}{7}=1$ елемент.

Броят на всички отключващи поредици е:

\[n=\binom{7}{4}9^3+\binom{7}{5}9^2+\binom{7}{6}9+1\]

Оставяме на читателя да пресметне конкретната числова стойност на $n$.
 
Има хипотеза, че $n=27280$, но не съм го пресмятал, един приятел ми го каза. 


\paragraph{Задача 5} Да означим с $A_1, A_2, A_3$ множествата студенти, спортуващи съответно плуване, бягане и волейбол.

Прилагаме принципа за включване и изключване:

$|A_1 \cup A_2 \cup A_3|=|A_1|+|A_2|+|A_3|-|A_1 \cap A_2|-|A_1 \cap A_3| - |A_2 \cap A_3|+|A_1 \cap A_2 \cap A_3|$

От условието на задачата знаем всички събираеми в дясната част на горното равенство, заместваме:

$|A_1 \cup A_2 \cup A_3|=23+26+24-16-15-17+9=34$

Следователно от всички $35$ студенти $34$ спортуват поне един от трите вида спорт, а един не спортува (възможно е да играе шах или бридж).


\paragraph{Задача 6} Очевидно $R_1=F_1=1$ и $R_2=F_2=1$. 

За $n>2$ можем да опростим рекурентното равенство за $R_n$:
\begin{align*}
R_n&=R_0+\ldots+R_{n-2}\\
R_n&=(R_0+\ldots+R_{n-3})+R_{n-2}\\
R_n&=R_{n-1}+R_{n-2}
\end{align*}

Опростяването следва от равенството $R_{n-1}=R_0+\ldots+R_{n-3}$, валидно за $n>2$ 
(то се получава като заменим $n$ с $n-1$ в рекурентното равенство за $R_n$).

Следователно редиците $R_n$ и $F_n$ имат еднакви рекурентни равенства за $n>2$.

Очевидно, след като имаме равенство в двете редици на членове с номера $1$ и $2$ и изчисляваме следващите членове с 
еднакви рекурентни равенства, ще получаваме еднакви членове и за номера $3,\; 4$ и т.н.

Формалното доказателство на равенството на всички членове с номера над $1$ следва да се извърши с индукция:  

Ползваме равенствата $R_1=F_1=1$ и $R_2=F_2=1$ като база за индукция.

От равенствата $R_n=R_{n-1}+R_{n-2}$ и $F_n=F_{n-1}+F_{n-2}$, верни за $n>2$,
следва твърдението:

\[(\forall k \; (n>k>0) \to (R_k=F_k)) \to R_n=F_n\]

Разказано с думи, то изглежда така: Ако за $k=1,2\ldots n-1$ има съвпадение на $R_k$ и $F_k$, 
от рекурентните равенства следва, че $R_n=F_n$.  

От принципа на пълната индукция следва твърдението на задачата $\forall n \; (n>0) \to (R_n=F_n)$. 



\end{document}


