\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.12.2016г.
\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
максимум точки &  6 & 6 & 6 & 6 & 6 & 30 \\
\hline
\end{tabular}
\end{center}

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

\paragraph{Задача 1.} 
%Нека $x \in \mathbb{R}, x>0$, а $n \in \mathbb{N}, n>0$. Докажете, че $(1+x)^n\ge 1+nx$.
Докажете, че числото $n^3+2n$ се дели на 3 за $\forall n \in \mathbb{N}$.

\paragraph{Задача 2.} Дадена е релацията $R=\{(x,x+5)|x \in \mathbb{Z}\}$.

$R'$ е рефлексивно, симетрично и транзитивно затваряне на $R$, 
тоест тя е най-малката по включване релация на еквивалентност, такава че $R\subset R'$.

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

\paragraph{Задача 3.} Дефинирахме на лекции множеството $I_n\stackrel{def}{=}\{i|i \in \mathbb{N}, 1\le i \le n\}$.

Нека $A\subset I_{10}$ и $|A|=6$. 
Докажете, че $А$ има 2 елемента с нечетна сума.
%\emph{Упътване:} Ползвайте принципа на Дирихле.


\paragraph{\mbox{Задача 4.}}
Нарекохме пермутации всички биекции от вида $f:I_n \to I_n$.

При дадена пермутация $f$, определяме редицата $a_1,a_2,\ldots,a_n$ така:

$a_1=f(1)$ и $a_{i+1}=f(a_i)$ за $1 \le i < n$.

Наричаме $f$ циклична пермутация, когато всички членове на редицата $a_1,a_2,\ldots,a_n$ са различни.

\emph{Пример:} Нека $n=2$. 
Пермутацията $f(1)=1, f(2)=2$ не е циклична, защото $a_1=f(1)=1, a_2=f(a_1)=1$ 
и двата члена на редицата $a_1, a_2$ са равни.
%Пермутацията $g(1)=2, g(2)=1$ е циклична, защото $a_1=g(1)=2, a_2=g(a_1)=1$ 
%и двата члена на редицата $a_1, a_2$ са различни.

(a - 3 точки) Пребройте и опишете цикличните пермутации при $n=4$.

(b - 3 точки) Пребройте цикличните пермутации при произволно $n$.

\paragraph{\mbox{Задача 5.}} %\mbox{}
%Към естествените числа причисляваме и нулата. 
Какъв е броят на редиците от естествени числа $x_1,x_2,\ldots,x_k$, за които:

(a - 2 точки) $\displaystyle\sum_{i=1}^{k}x_i=n$, и $x_i\ge 0$.

(b - 4 точки) $\displaystyle\sum_{i=1}^{k}x_i=n$, и $x_i> 0$.

\newpage

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