\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}
Второ домашно по Дискретни структури, 03.01.2020 г.
\end{spacing}
Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Група:\_\_\_\_\_\_\_ 
\end{center}

\begin{center}
\begin{tabular}{|l|c|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
максимум точки &  1 & 1 & 1 & 1 & 1 & 5 \\
\hline
\end{tabular}
\end{center}

\emph{Забележка:} Предайте домашното на вашия асистент най-късно на 17 януари, преди започване на упражнението на групата Ви !

\paragraph{Задача 1.} 
Решете рекурентното уравнение:

$R_n=3R_{n-1}-2R_{n-2}+2^n$ при начални условия $R_0=0, R_1=1$.


\paragraph{Задача 2.}  
Колко са редиците, съдържащи 20 нули и 10 единици, в
които няма съседни единици.
%Нека $T(V,E)$ е дърво, а $L_1$ и $L_2$ са прости пътища в него с максимална дължина (измерена в брой ребра).
%Докажете, че $L_1$ и $L_2$ имат общ връх.

\paragraph{Задача 3. } 
Нека $G(V,E)$ е неориентиран 4-регулярен граф (от всеки връх излизат точно 4 ребра).
В $G$  няма цикли с дължина 3. Докажете, че графът има поне 8 върха.
Постройте граф с горните свойства, който има точно 8 върха.

\paragraph{Задача 4.}
Нека $B_n(V,E)$ е графът на двоичния хиперкуб ($n>0$).
Постройте покриващо дърво за $B_n$, което има само две листа.

\paragraph{Задача 5.} Кои са булевите функции $f(x,y,z)$, такива, че:

(1) $\{f\}$ е пълно множество.

(2) $f(0,0,1)=f(0,1,0)=0$ и $f(1,0,1)=f(1,1,0)=1$.

%(3) Взети поотделно, $\{f_1\}$ и $\{f_2\}$ не са пълни множества.

\emph{Упътване:} Ползвайте критерия на Пост-Яблонски.

\end{document}

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

\paragraph{Задача 2.} Нека $n=(2k_1+1)+(2k_2+1)+(2k_3+1)$, където $k_1 \leq k_2 \leq k_3$. 

Тогава $n-3=2(k_1+k_2+k_3)$, или $k_1+k_2+k_3=(n-3)/2$.
Означаваме $m=(n-3)/2$ и търсим колко комбинации има за тройките $k_1 \leq k_2 \leq k_3$, такива че $k_1+k_2+k_3=m$.

Ако нямаше условието за разместване на трите числа (наредбата $k_1 \leq k_2 \leq k_3$), броят на комбинациите е $\binom{m+2}{2}$, защото тройките могат да бъдат разглеждани като комбинации с повторение, без наредба.

Нека $p=\binom{m+2}{2}$ са всички тройки със сума $m$, а $q$ е броят на тройките, 
за които $k_1 \leq k_2 \leq k_3$.

По-долу с $\lfloor x\rfloor $ означаваме цялата част на числото $x$.

Формулите за стойността на $q$ са:

$q=p/6 + \lfloor (m+2)/2 \rfloor /2$, ако $m$ не се дели на 3 и

$q=(p+2)/6 + \lfloor (m+2)/2 \rfloor /2$, ако $m$ се дели на 3.

Вижте \href{http://skelet.ludost.net/DS/problems/D2_p2_solution_14.01.2019.webm}{видео}, в което са обяснени идеите за извода на тези формули!
В края на видеото има грешка в знака за формулата за $q$, вместо $+$ пиша $-$.

Програма на C, която смята комбинациите при зададено $n$:

\begin{verbatim}
#include <stdio.h>

int main(void)
{
 int n,m,q,k1,k2;
 printf("Въведете положително нечетно число: ");
 scanf("%d",&n);
 m=(n-3)/2;
 printf("n=%d, m=%d\n",n,m);
 q=0;
 for (k1=0; k1<=m; k1++)
  for (k2=k1; k2<=m; k2++)
   if (m-k1-k2>=k2) q++; // к3>=к2
 printf("Брой комбинации: %d\n",q);
}  
\end{verbatim}

\paragraph{Задача 3.}
Вижте \href{http://skelet.ludost.net/DS/problems/D2_p3_solution_14.01.2019.webm}{видео} с решението.

\end{document}