\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}
Поправителен писмен изпит по ДС, 25.08.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\geq 2$ студенти. Те трябва да подготвят презентации на избрани от тях теми, разпределени в малки групи. Докажете, че независимо от числеността на курса:

(а -- 10т.) студентите могат да се разделят в групи от двама или трима души;

(б -- 10т.) студентите могат да се разделят в групи от двама или трима души, като има най-много две групи от по двама студенти.

\paragraph{Задача 2} Дадено е крайно множество $A$ и тотална функция $f: A \to A$, която е инекция. Докажете, че $f$ е биекция.

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

(а -- 10т.) Докажете, че $l$ е четно.

(б -- 10т.) Намерете минималния брой ребра, които при добавяне към $E$ ще превърнат $G$ 
в ойлеров граф.

\paragraph{Задача 4} Даден е равностранен триъгълник с дължина на страната 10. Докажете, че както и да се изберат пет точки от вътрешността на триъгълника, то между тях ще има поне две на разстояние, по-малко от 5. 

\emph{Упътване:} Използвайте наготово следното твърдение: всяка отсечка между две точки в произволен триъгълник е не по-дълга от най-голямата му страна; равенство се достига само когато точките са краищата на тази страна.  


\paragraph{Задача 5} Да се намери броят на булевите функции на $n$ променливи, за чиято съвършена дизюнктивна нормална форма е вярно следното:

(а -- 10т.) буквата $x_1$  се среща само с отрицание;

(б -- 10т.) има три събираеми и във всяко от тях има точно две букви с отрицания.


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

%\end{document}

\newpage

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


\paragraph{Задача 2 } 
%Дадено е крайно множество $A$ и тотална функция $f: A \to A$, която е инекция. 
%Докажете, че $f$ е биекция.
Нека $B=\{y : \exists x \in A, y=f(x)\}$ е множеството от значенията на $f$. 

Ако $A=B$, то $f$ е биекция. 

Ако $B$ е същинско подмножество на $A$, то има по-малко елементи и тогава, съгласно с принципа на Дирихле, поне два елемента на $A$ ще бъдат изобразени от $f$ в един елемент на $B$, което противоречи на условието, че $f$ е инекция.

\paragraph{Задача 4} Нека триъгълникът е $ABC$. 
Да означим с $A_1, B_1$ и $C_1$ средите на страните $BC, AC$ и $AB$ съответно
и да ги свържем с отсечки.

Получаваме разрязване на $\triangle ABC$ на четири еднакви равностранни триъгълника --
$\triangle A_1B_1C_1$, $\triangle AB_1C_1$, $\triangle A_1BC_1$ и $\triangle A_1B_1C$.  

Както и да избираме пет точки в $\triangle ABC$, поне две от тях ще попаднат в един от четирите малки триъгълника (следствие от принципа на Дирихле). 

Ползваме упътването за такава двойка точки. 
Дължината на свързващата ги отсечка ще е най-много 5 -- дължината на страната на съдържащия ги малък триъгълник. 
Равенство ще се достига само когато са върхове на този триъгълник, но това е невъзможно, защото са вътрешни за $\triangle ABC$, следователно разстоянието между тях е по-малко от 5.
 

\paragraph{Задача 5} При броенето ще правим разсъждения за таблицата, представяща възможна функция $f$ и вида на пълните елементарни конюнкции (за краткост ще ги наричам импликанти), за които $f$ приема стойност 1:

(А) Функция от този вид е $0$, когато $x_1=1$, т. е. за всички редове от втората половина на таблицата. В първата половина има $2^{n-1}$ реда и там $f$ може да приема произволни стойности. За всеки от тези $2^{n-1}$ реда стойността на $f$ е 0 или 1, 
следователно за $f$ има $2^{2^{n-1}}$ възможности.

Един от случаите е специален -- когато колоната от стойности на $f$ съдържа само нули, тя не може да се представи като СДНФ, защото има 0 импликанти. Като махнем този специален случай, броят на функциите, удовлетворяващи условието, е $2^{2^{n-1}}-1$.

(Б) Функция от този вид има точно 3 импликанти. 
Съответният ред за всяка от тези имликанти в таблицата на $f$ съдържа точно 2 нули и $n-2$ единици в низа, описващ стойностите на булевите променливи. 
Броят на всички такива редове е $\binom{n}{2}$. 

Можем да изберем 3 от тези $\binom{n}{2}$ реда по  $\dbinom{\binom{n}{2}}{3}$ начина, 
това е и броят на функциите, удовлетворяващи условието.

\end{document}