\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} Изпит по Дискретни структури, 15.02.2019г. \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 максимум точки & 5 & 6 & 5 & 6 & 8 & 30 \\ \hline \end{tabular} \end{center} \paragraph{Задача 1.} %\mbox{}\\ Редицата $a_0, a_1, \ldots a_n, \ldots$ е дефинирана с рекурентното уравнение: $a_0=0$ $a_n=a_{n-1}+n2^n$ за $n>0$ Решете уравненето и намерете формула за $a_n$. \paragraph{Задача 2.} %Фрагмент от теорема на Берж за максималното покритие Даден е неориентирания граф $G(V,E)$. Ребрата са боядисани в два цвята -- син и червен, като от всеки връх излиза най-много едно синьо и най-много едно червено ребро. Сините ребра са повече от червените. Докажете, че в $G$ има път със следните свойства: (1) От крайните върхове на пътя излиза точно по едно ребро. (2) Крайните ребра в пътя са сини. \paragraph{Задача 3.} Колко са двойките от вида $(k_1,k_2)$, където $k_1, k_2$ и $n$ са естествени числа, при ограничения $0\leq k_1 \leq k_2 \leq n$ ? \paragraph{Задача 4.} В магистърска програма $X$ има 17 студенти, а в магистърска програма $Y$ - 12 студенти. Всеки от тях трябва да избере и посещава точно един от общо 10 избираеми курса. По колко начина студентите могат да направят своя избор, ако: (а - 2 точки) няма никакви ограничения при избора; (б - 2 точки) няма курс, избран от всеки студент от програма $Y$; (в - 2 точки) всеки курс е избран от поне един студент; \paragraph{Задача 5.} %\mbox{} Намерете минимална дизюнктивна нормална форма и полинома на Жегалкин на булевата функция $f(x,y,z)$, определена с редицата стойности $f = (10111010)$. \newpage \section*{Решения} \paragraph{Задача 2.} Разглеждаме свързаните компоненти на графа. Тъй като от всеки връх излизат най-много 2 ребра, тези компоненти са цикли, прости пътища или изолирани върхове. Изолираните върхове не са интересни. Циклите се състоят от редуващи се сини и червени ребра. За да няма съседни едноцветни ребра, трябва циклите да са с четен брой ребра. Следователно броят на червените и сини ребра във всички цикли е еднакъв. Остават простите пътища, те също се състоят от редуващи се сини и червени ребра. Ако единия край на път е червен, броят на червените ребра е равен на сините (при друг син край) или по-голям (при друг червен край). След като общия брой на сините ребра е по-голям от червените, нужно е да има поне една компонента с повече сини ребра. Единствената възможност е прост път с два сини края. \paragraph{Задача 4.} В магистърска програма $X$ има 17 студенти, а в магистърска програма $Y$ - 12 студенти. Всеки от тях трябва да избере и посещава точно един от общо 10 избираеми курса. По колко начина студентите могат да направят своя избор, ако: а) няма никакви ограничения при избора; $10^{29}$ б) няма курс, избран от всеки студент от програма $Y$; $10^{17}(10^{12}-10)$ в) всеки курс е избран от поне един студент; $\sum_{i=0}^{10}\binom{10}{i}(-1)^i(10-i)^{29}$ (принцип на включване и изключване) \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 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}