\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}
Първо домашно по Дискретни структури, 06.11.2018г.
%Първо домашно по Дискретни структури, условия и решения
\begin{spacing}{2}
\end{spacing}
Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Група:\_\_\_\_ 
\end{center}

\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c||c|}
\hline
Задача & 1 & 2 & 3 & 4a & 4b & Общо \\ 
\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.} 
Докажете, че за всяко естествено $n>0$ е вярно равенството:
\[1+3+5+\ldots+(2n-1)=n^2\]

\paragraph{Задача 2.} 
Дадени са функциите $f:A\rightarrow B$ и $g:B\rightarrow C$.
Тяхната композиция $h(x)=g(f(x))$ е инекция.

Докажете, че:

(a) Ако $f$ не е инекция, $g$ не е тотална.

(b) Ако $g$ не е инекция, $f$ не е сюрекция.


\paragraph{Задача 3.} 
Даден е равностранен триъгълник с дължина на страната $n>0$. Докажете, че както и да се изберат $n^2+1$ точки от вътрешността на триъгълника, то между тях ще има поне две на разстояние, по-малко или равно на 1. 

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

\paragraph{Задача 4.} 
Нека $A$ е множеството от всички безкрайни редици 
 $\alpha=\alpha_0\alpha_1\alpha_2\ldots$, състоящи се от нули и единици 
 ($\alpha_i \in \{0,1\}$).

Определяме релацията $R \subseteq A\times A$ така -- 
две редици $\alpha=\alpha_0\alpha_1\alpha_2\ldots$ и 
$\beta=\beta_0\beta_1\beta_2\ldots$ са в релация, 
когато се различават на краен брой позиции.

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

(a.2) Докажете, че класовете на еквивалентност, 
породени от $R$ са безкрайни изброими множества.

(b) Нека $F=\{[\alpha]|\alpha \in A\}$ е множеството от класовете на еквивалентност,
породени от $R$.
Докажете, че $F$ е неизброимо.

\vspace{30pt}

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

%\end{document}

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

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

Използваме индукция.

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

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

(a) Нека $f$ не е инекция и $g$ е тотална. 

Щом $f$ не е инекция, съществуват $x_1\neq x_2$, такива че $f(x_1)=f(x_2)=y$.

Щом $g$ е тотална, тя е дефинирана за $y$, нека $g(y)=z$.

Тогава $h(x_1)=g(f(x_1))=g(y)=z$ и  $h(x_2)=g(f(x_2))=g(y)=z$, 
следователно $h$ не е инекция, противоречие.

(b) Нека $g$ не е инекция и $f$ е сюрекция.

Щом $g$ не е инекция, съществуват $y_1\neq y_2$, такива че $g(y_1)=g(y_2)=z$.

Щом $f$ е сюрекция, $y_1$ и $y_2$ имат прообрази $x_1$ и $x_2$, 
такива че $f(x_1)=y_1$ и $f(x_2)=y_2$. 
Освен това $x_1\neq x_2$, защото $f$ е функция.

Пак намерихме  $x_1\neq x_2$, такива че $h(x_1)=h(x_2)$, противоречие.

\vspace{5pt}

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

Нека триъгълникът е $ABC$. 
Нарязваме го с прави, успоредни на страните на равностранни триъгълници със страна 1.

Използваме задача 1 и съобразяваме, че броят на малките триъгълници е $n^2$.  

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

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

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

Свойството $(\alpha,\beta) \in R$ можем да изкажем така -- 
съществува $n_0 \in \mathbb{N}$, такова че за всяко $i>n_0, \alpha_i=\beta_i$.
Достатъчно е за $n_0$ да изберем най-големия номер на позиция, в която двете редици се различават.

(a.1) Рефлексивността на $R$ следва от факта, че всяка редица се различава от себе си в нула позиции.

Симетричността на $R$ също следва тривиално от симетричността на дефиницията на релацията.

Транзитивност: нека $(\alpha,\beta) \in R, \quad (\beta,\gamma) \in R$.
Съществуват номера $n_0,n_1$, такива, че за $i>n_0, \alpha_i=\beta_i$ и за $i>n_1, \beta_i=\gamma_i$. Нека $n_2=max(n_0,n_1)$, 
тогава за всяко $i>n_2, \alpha_i=\beta_i, \beta_i=\gamma_i$, следователно за 
$i>n_2, \alpha_i=\gamma_i$, тоест $(\alpha,\gamma) \in R$.

(a.2) Нека $\alpha \in A$ е редица от нули и единици, 
а $[\alpha]$ е породеният от нея клас на еквивалентност относно релацията $R$.  
Построяваме биекция между $[\alpha]$ и $\mathbb{N}$ така:

На  $\alpha$ съпоставяме 0.

Нека $\beta \neq \alpha, (\alpha,\beta) \in R$.
Редиците $\alpha$ и $\beta$ се различават на поне една позиция, нека $n$ е най-големият номер на позиция, в която се различават.

Стром двоично число $j$ с $n+1$ цифри, което има единици в позиции, където $\alpha$ и $\beta$ се различават, като броим позициите от $n$ към $0$.

Старшата цифра на $j$ е единица, тоест $j>0$. На  $\beta$ съпоставяме числото $j$.

Лесно се вижда, че построеното съпоставяне е биекция, следователно $[\alpha]$ е изброимо безкрайно множество.

(b) Допускаме, че $F$ е крайно или изброимо.

Тъй като $A$ е обединение на елементите на $F$, и в двата случая ще се окаже, 
че $A$ е изброимо, тъка като в подусловие (a) доказахме, 
че множествата от $F$ са изброими.


От доказателството на теоремата на Кантор (диагоналния метод) знаем, 
че $|A|=|2^{\mathbb{N}}|$, тоест $A$ не е изброимо, противоречие.
   

\end{document}