\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}
Първо домашно по Дискретни структури, 07.11.2019г.
%Първо домашно по Дискретни структури, условия и решения
\begin{spacing}{2}
\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{Забележка:} За отлична оценка са достатъчни 100 точки!

\paragraph{Задача 1.} 
Нека $R\subset A\times A$ е релация над крайното множество $A$,
такава, че\\
$\forall x \in A, \forall y \in A, x \neq y \rightarrow 
((x, y) \in R \vee (y, x) \in R$).

Докажете, че съществува верига, 
която съдържа всеки елемент на $A$ точно веднъж.

\emph{Упътване:} Ползвайте индукция.

\emph{Верига} наричаме крайна редица $a_0, a_1, \ldots a_l$ от елементи на $A$, 
такава, че за всяко $i, 0\leq i <l$ е изпълнено $(a_i,a_{i+1}) \in R$. 


\paragraph{Задача 2.} 
Нека точките с цели координати в равнината са оцветени с 8 цвята.
Докажете, че има две едноцветни точки на разстояние по-малко от 3.
%\emph{Упътване:} Ползвайте принципа на Дирихле.

\paragraph{Задача 3.} 
Колко от целите числа от 1 до 2019 включително не се делят 
нито на 3, нито на 7, нито на 13 ?

\paragraph{Задача 4.} 
На изпит при доцент Незнайков се явяват 13 студенти. 
Той си има квоти: решил е да постави четири двойки, 
три тройки, четири четворки и две петици 
(шестици доцентът по принцип не пише). 
По колко начина могат да бъдат разпределени оценките?
%Изчислете отговора докрай.

\paragraph{\mbox{Задача 5.}}
Нека $R \subset A \times A$ е рефлексивна и транзитивна релация.

За елементите на $A$ дефинираме релация $\sim$, такава че
 $x \sim y$, когато $(x,y) \in R$ и $(y,x) \in R$.

(a) Докажете, че $\sim$ е релация на еквивалентност.

Означаваме с $[a]=\{x|x \in A, a \sim x\}$ класът на еквивалентност на $a \in A$.  

Нека $F=\{[a]|a \in A\}$ е множеството от класовете на еквивалентност, породени от $\sim$.  

За елементите на $F$ дефинираме релация $\prec$, такава че $[a] \prec [b]$,
когато за някои $x \in [a], \; y \in [b]$ е изпълнено $(x,y) \in R$.

(b) Докажете, че $\prec$ е частична наредба.

\vspace{30pt}

\emph{Срок за предаване:} Предайте домашното на асистента на вашата група преди започване на упражнението през седмицата 25-29 ноември 2019 г.!


\end{document}

\newpage

\section*{Решения}

\paragraph{Задача 1.} \mbox{} %\\

Доказваме равенството по индукция: 

(a) Проверяваме го за $n=2$: 

\[(1-\frac{1}{2^2})=\frac{3}{4}=\frac{3+1}{2\times 2}\]


(b) Нека е изпълнено за $n$: 

\[(1-\frac{1}{2^2})(1-\frac{1}{3^2})\ldots(1-\frac{1}{n^2})=\frac{n+1}{2n}\]

Тогава:

\[(1-\frac{1}{2^2})(1-\frac{1}{3^2})\ldots(1-\frac{1}{n^2})(1-\frac{1}{(n+1)^2})=\]

\[\frac{n+1}{2n}(1-\frac{1}{(n+1)^2})=\frac{n+1}{2n}\frac{(n+1)^2-1}{(n+1)^2}=\]

\[\frac{(n+1)^2-1}{2n(n+1)}=\frac{n(n+2)}{2n(n+1)}=\frac{n+2}{2(n+1)}\]

Следователно даденото равенство е изпълнено за $n+1$.
От принципа на индукцията следва, че е вярно за всяко $n\ge 2$.


\paragraph{Задача 2.} \mbox{} %\\

Да означим дробната част на $i\alpha$ с ${\beta}_i=i\alpha-\lfloor i\alpha \rfloor$ за $i=1,2\ldots n$.

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

Всички числа ${\beta}_i$ са в интервала $[0,1)$. 

\emph{Разсъждение A:}

Ако за някое $i$ е изпълнено ${\beta}_i\le 1/n$, задачата е решена:

Получаваме
$0\le i\alpha-\lfloor i\alpha \rfloor \le 1/n$, 
или $\lfloor i\alpha \rfloor \le i\alpha \le \lfloor i\alpha \rfloor+1/n$,
тоест $i\alpha$ е на разстояние най-много $1/n$ от цялото число $\lfloor i\alpha \rfloor$.

\emph{Разсъждение B:}

%Остава да разгледаме случая ${\beta}_i > 1/n$, за всяко $i$.
Разделяме интервала $[0,1)$ на $n$ равни подинтервала -- $[0,1/n), [1/n,2/n), \ldots ,[{n-1}/n,1)$.

Числата ${\beta}_i$ са точно $n$ на брой, ако някое от тях е в подинтервала $[0,1/n)$, 
задачата е решена, съгласно \emph{Разсъждение A:}. 
Ако всичките са в останалите $n-1$ подинтервала, 
съгласно принципа на Дирихле поне две ще са в един подинтервал, тоест на разстояние по-малко от $1/n$. 

Нека тези две числа са ${\beta}_i \le {\beta}_j$, тогава:
\begin{equation}\label{eq1}
0\le {\beta}_j-{\beta}_i \le 1/n 
\end{equation}

\emph{Случай B.1:} Нека $i<j$, да означим $k=j-i$, очевидно $1\le k < n$:

В този случай ${\beta}_j-{\beta}_i = (j-i)\alpha+\lfloor i\alpha \rfloor-\lfloor j\alpha \rfloor$
и неравенството (\ref{eq1}) придобива вида:
\[ 0\le (j-i)\alpha+\lfloor i\alpha \rfloor-\lfloor j\alpha \rfloor \le 1/n \]

или
\[ \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor \le (j-i)\alpha \le \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor + 1/n \]

заместваме $k=j-i$ и получаваме:
\[ \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor \le k\alpha \le \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor + 1/n \]

Оказа се, че $k\alpha$ е на разстояние най-много $1/n$ от цялото число $\lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor$ (в този случай е над цялото число).

\emph{Случай B.2:} Нека $i>j$, да означим $k=i-j$, очевидно $1\le k < n$:

В този случай ${\beta}_j-{\beta}_i = (j-i)\alpha+\lfloor i\alpha \rfloor-\lfloor j\alpha \rfloor$
и неравенството (\ref{eq1}) придобива вида:
\[ 0\le (j-i)\alpha+\lfloor i\alpha \rfloor-\lfloor j\alpha \rfloor \le 1/n \]

или
\[ \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor \le (j-i)\alpha \le \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor + 1/n \]

заместваме $k=i-j$ и получаваме:
\[ \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor \le -k\alpha \le \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor + 1/n \]

умножаваме по $(-1)$:
\[ \lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor \ge k\alpha \ge \lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor - 1/n \]

Оказа се, че $k\alpha$ е на разстояние най-много $1/n$ от цялото число $\lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor$ (в този случай е под цялото число).

\paragraph{Задача 3.} 

\paragraph{Първи начин:} \mbox{}

Нека $m$ е строго положително естествено число. 
Представяме го в двоична бройна система като редица от нули и единици.
Нека в записа има $k+1$ единици, а номерацията на битовете е от дясно наляво и започваме от 0.

Обхождаме битовете отдясно наляво и при срещане на единица записваме позицията \`{и} в редица.
Нека най-дясната единица е на позиция $n_0$, следващата единица е на позиция $n_1$ и т.н. 
до старшата единица, която е най-вляво на позиция $n_k$. 

Описахме функция, да я обозначим $h$, която по числото $m$ строи редица $h(m)=(n_0,n_1\ldots n_k)$. 
Редицата е строго растяща (всички единици в двоичния запис са на различни позиции).
За различни числа ще получим различни редици (инекция), 
а за всяка редица можем да построим двоичен запис и число, което я поражда (сюрекция). 

\emph{Пример:} Нека $m=22$, двоичният му запис е $10110$, единици има на позиции 1, 2 и 4,
следователно  $h(22)=(1,2,4)$

Функцията $h$ не е тотална, тя не е дефинирана за числото 0. 
Нека $H(n)=h(n+1)$, новата функция $H$ е биекция от естествените числа към 
всички растящи редици и е решение на задачата.  

\paragraph{Втори начин:} \mbox{}

Нека $s=(n_0,n_1\ldots n_k)$ е растяща редица, 
дефинираме функцията $f_{+}(s)=2^{n_0}+2^{n_1}+ \ldots +2^{n_k}$.

На произволната редица $s$ функцията $f_{+}(s)$ съпоставя число $m=f_{+}(s)$.
Числото $m$ има единици в двоичния си запис точно на позиции $n_0,n_1\ldots n_k$, ако броим позициите от дясно на ляво, започвайки от 0 за младшия разряд в двоичния запис на $m$. 

Очевидно $f_{+}$ е биекция между $\mathbb{S}_+$ и строго положителните естествени числа.
На всяка редица съпоставя число, на различните редици съпоставя различни числа, а всяко положително число е образ на редица от $\mathbb{S}_+$.

Функцията $f(s)=f_{+}(s)-1=2^{n_0}+2^{n_1}+ \ldots +2^{n_k}-1$ 
ще е биекция от $\mathbb{S}_+$ към $\mathbb{N}$, обратната \`{и} функция $f^{-1}$ е решение на задачата.

\paragraph{Задача 4.} 

\paragraph{Първи начин:} \mbox{}

Нека $m$ е строго положително естествено число. 
Представяме го в двоична бройна система като редица от нули и единици.
Нека в записа има $k+1$ единици, а номерацията на битовете е от дясно наляво и започваме от 0.

Нека $n_0$ е броят нули надясно от най-младшата (най-дясна единица в двоичния запис).
Обхождаме единиците отдясно наляво и броим колко нули има между всеки две единици при обхождането.
Нека $n_1$ е броят нули между най-младшата единица до следващата вляво, 
$n_2$ е броят нули втората и третата единица и т.н. 
до $n_k$ -- броят нули между двете най-леви единици в записа. 

Описахме функция, да я обозначим $h$, която по числото $m$ строи редица $h(m)=(n_0,n_1\ldots n_k)$. 
За различни числа $m_1$ и $m_2$ ще получим различни редици $h(m_1)$ и $h(m_2)$ (инекция), 
а за всяка редица можем да построим двоичен запис и число, което я поражда (сюрекция). 

\emph{Пример:} Нека $m=22$, двоичният му запис е $10110$, дължините на интервалите нули са 1, 0 и 1,
следователно  $h(22)=(1,0,1)$

Функцията $h$ не е тотална, тя не е дефинирана за числото 0. 
Нека $H(n)=h(n+1)$, новата функция $H$ е биекция от естествените числа към 
всички редици и е решение на задачата.  

\paragraph{Втори начин:} \mbox{}


Нека $s=(n_0,n_1\ldots n_k)$ е произволна редица от естествени числа.
Дефинираме нова редица $s_{+}=(l_0,l_1\ldots l_k)$ индуктивно по $k$ така:

(1) $l_0=n_0$

(2) за $i>0$ нека $l_i=l_{i-1}+n_i+1$.

По-неформално, $l_i=n_0+n_1+1+n_2+1+\ldots + n_i+1$.
Очевидно $s_{+}=(l_0,l_1\ldots l_k)$ е строго растяща редица.

Функцията $g(s)=s_{+}$ е биекция, която на всяка редица $s\in \mathbb{S}$ 
съпоставя редица  $s_{+} \in \mathbb{S}_{+}$.

Да вземем функцията $f_{+}$ от решението на предната задача (втори начин).
Нека $m=f_{+}(g(s))$. 

Числото $m$ ще съдържа в двоичния си запис единици на позиции $l_0,l_1\ldots l_k$.
Редицата от броя на нулите между всеки две поредни единици в двоичния запис на $m$ ще е 
$n_0,n_1\ldots n_k$ (тук броим и нулите след последната единица, те са точно $n_0$).

Функцията $h(s)=f_{+}(g(s))-1$ е биекция от $\mathbb{S}$ към $\mathbb{N}$, обратната \`{и} функция е решение на задачата.

\paragraph{Задача 5.a} \mbox{}

От дефиницията на $\prec$ следва, че
$\{q_i\} \prec \{p_i\}$, когато някой член на $\{p_i\}$ е по-голям от всички членове на $\{q_i\}$.

Казано по друг начин, някой член на $\{p_i\}$ е строга горна граница на $\{q_i\}$.
Оттук директно следва антирефлексивността и антисиметричността на $\prec$.

Транзитивността също се очевидна:
от $\{q_i\} \prec \{p_i\} \prec \{r_i\}$ следва, че някое $r_{n_1}$ надвишава всички $\{p_i\}$.
Някое $p_{n_0}$ надвишава всички $\{q_i\}$, следователно $r_{n_1} > p_{n_0}> q_i$, 
или $r_{n_1} > q_i$ за всяко $i$, откъдето следва $\{q_i\} \prec \{r_i\}$. 

\paragraph{Задача 5.b} \mbox{}

Дефиницията на $\sim$ се състои от две отрицания.

Отрицанието на $\{q_i\} \prec \{p_i\}$ изглежда така:
за всяко $n_0$ съществува $j>n_0$, такова, че съществува $i$ за което $q_i \ge p_j$.
Неравенството $q_i \ge p_j$ влече $q_i > p_{n_0}$.

Казано по-просто, отрицанието на $\{q_i\} \prec \{p_i\}$ е:
за всяко $n$ съществува $i$, такова че $q_i > p_n$.

Дефиницията на $\{q_i\} \sim \{p_i\}$ е еквивалентна на твърдението: 
всеки член на $\{q_i\}$ е по-малък от някой член на $\{p_i\}$ и  
всеки член на $\{p_i\}$ е по-малък от някой член на $\{q_i\}$.

(1) $\{p_i\} \sim \{p_i\}$, защото всеки член $p_i$ е по-малък от $p_{i+1}$ (редиците са растящи).
Следователно  $\sim$ е рефлексивна.

(2) Симетричността на  $\sim$ следва от симетричната дефиниция.

(3) Транзитивност: 

Нека $\{q_i\} \sim \{p_i\} \sim \{r_i\}$. 

Избираме произволно $i_0$, за него съществува $i_1$, такова че $q_{i_0} < p_{i_1}$.
За $i_1$ съществува $i_2$, такова че $p_{i_1} < r_{i_2}$, следователно $q_{i_0} < r_{i_2}$. 

Избираме произволно $j_0$, за него съществува $j_1$, такова че $r_{j_0} < p_{j_1}$.
За $j_1$ съществува $j_2$, такова че $p_{j_1} < q_{j_2}$, следователно $r_{j_0} < q_{j_2}$.

От неравенствата $q_{i_0} < r_{i_2}$ и $r_{j_0} < q_{j_2}$ и 
зависимостите между съответните индекси следва $\{q_i\} \sim \{r_i\}$.

\paragraph{Задача 5.c} \mbox{}

Да разгледаме произволна редица $\{q_i\} \in \mathbb{S}_Q^+$. 
Тя е строго растяща редица от рационални числа.
Интересен е въпросът дали е ограничена.

Има два случая за $\{q_i\}$:

(случай 1) $\{q_i\}$ е ограничена. В този случай лесно се проверяват следните свойства:

(1.a) $\{q_i\} \prec \{p_i\}$  точно когато някой член на $\{p_i\}$ е горна граница за $\{q_i\}$.

(1.b) $\{q_i\} \sim \{p_i\}$ точно когато $\{p_i\}$ и $\{q_i\}$ имат еднакви горни граници.

(случай 2) $\{q_i\}$ е неограничена. В този случай:

(2.a) $\{q_i\} \prec \{p_i\}$  никога не е изпълнено.

(2.b) $\{q_i\} \sim \{p_i\}$ точно когато $\{p_i\}$ е неограничена.

\emph{Интерпретация, ако имаме реални числа $\mathbb{R}$:}

Ако $\{q_i\}$ е ограничена, тя е сходяща, нека $\lim \{q_i\}=q \in \mathbb{R}$.
Класът на еквивалентност $[\{q_i\}]$ се състои от всички редици със същата граница $q$.

Ако $\{q_i\}$ е неограничена, тя е разходяща, $\lim \{q_i\}=+\infty$.
Класът на еквивалентност $[\{q_i\}]$ се състои от всички неограничени редици.

От направените дотук разсъждения следва, че множеството от класовете на еквивалентност на 
релацията $\sim$ е изоморфно на $\mathbb{R}\cup \{+\infty\}$. 
Терминът 'изоморфно' ползваме в смисъл на биективно съответствие, 
на всеки клас, породен от ограничена редица съответства реално число,
на класа на неограничените растящи редици съпоставяме специалния символ $+\infty$.

\emph{Интерпретация, ако нямаме реални числа:}

Ако не разполагаме с конструкция на реалните числа, можем да ги дефинираме,
като ползваме класовете на еквивалентност на релацията $\sim$.

Ако вземем само ограничените редици от $\mathbb{S}_Q^+$, 
породените от $\sim$ класове образуват структура, 
върху която можем да дефинираме аритметични операции, наредба и свойства, 
удовлетворяващи интуицията ни за реалните числа.

%Например строгата наредба се задава директно от релацията $\pred$.

%Сумата на редици от два класа е нов клас, преставящ сума ... 



%\[LS=\{\{q_i\}|\{q_i\} \in \mathbb{S}_Q^+, \exists u\in \mathbb{Q} \, \forall i \, q_i<u\}\]

\end{document}
