\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}
Първо домашно по Дискретни структури, 10.11.2017г.
%Първо домашно по Дискретни структури, условия и решения
\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.} 
Докажете, че за всяко естествено $n\ge 2$ е вярно равенството:
\[(1-\frac{1}{2^2})(1-\frac{1}{3^2})\ldots(1-\frac{1}{n^2})=\frac{n+1}{2n}\]

\paragraph{Задача 2.} 
%5 точки лежат в равностранен тригълник със страна 2. 
%Докажете, че поне две от тях са на разстояние по-малко или равно на 1. 
Нека $\alpha$ е реално, а $n$ е положително естествено число.
Докажете, че някое от числата $\alpha,2\alpha,3\alpha \ldots n\alpha$ 
е на растояние най-много $\frac{1}{n}$ от някое цяло число.

\emph{Упътване:} Ползвайте принципа на Дирихле.

\paragraph{Задача 3.} 
Нека $\mathbb{N}$ е множеството на естествените числа, а $\mathbb{S}_+$ е множеството от строго растящи крайни редици от естествени числа:
\[\mathbb{S}_+=\{(n_0,n_1\ldots n_k)|k\in\mathbb{N}, n_i\in\mathbb{N}, n_0<n_1<\ldots<n_k \}\]
Постройте биекция между множествата $\mathbb{N}$ и $\mathbb{S}_+$.

\emph{Упътване:} За произволно естествено число $m$  
разгледайте редицата от позициите на единиците в двоичния запис на $m$.

\paragraph{Задача 4.} 
Нека $\mathbb{N}$ е множеството на естествените числа, а $\mathbb{S}$ е множеството от крайни редици от естествени числа:
\[\mathbb{S}=\{(n_0,n_1\ldots n_k)|k\in\mathbb{N}, n_i\in\mathbb{N} \}\]
Постройте биекция между множествата $\mathbb{N}$ и $\mathbb{S}$.

\emph{Упътване:} За произволно естествено число $m$  
разгледайте редицата от броя на нулите между всеки две поредни единици в двоичния запис на $m$.

\paragraph{\mbox{Задача 5.}}
Нека $\mathbb{S}_Q^+$ е множеството от строго растящи безкрайни редици от рационални числа:
\[\mathbb{S}_Q^+=\{\{q_i\}_{i=0}^\infty|\; \forall i \; (q_i\in\mathbb{Q}) \land (q_i<q_{i+1}) \}\]
Нека $\prec$ е релация над редиците от $\mathbb{S}_Q^+$, определена така:

$\{q_i\} \prec \{р_i\}$, когато съществува $n_0$, такова, че за всяко $j>n_0$ и за всяко $i$ е изпълнено неравенството $q_i<p_j$.

(a) Докажете, че $\prec$ е антирефлексивна, транзитивна и антисиметрична.

Дефинираме нова релация $\{q_i\} \sim \{р_i\}$, когато нито $\{q_i\} \prec \{р_i\}$, нито $\{p_i\} \prec \{q_i\}$

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

(c) Как изглеждат класовете на еквивалентност на $\sim$, дайте интуитивно описание.

\end{document}

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

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

(a) Нека $x_1\ne x_2$. Тогава $f(x_1)-f(x_2)=\frac{2(x_1-x_2)}{5}\ne 0$.

(b) Означаваме стойността $f(x)$ с $y$. Тогава $y=\frac{2x-7}{5}$.

Изразяваме $x$ чрез $y$ и получаваме $x=\frac{5y+7}{2}$.

Това равенство ни дава обратната функция $f^{-1}(y)=\frac{5y+7}{2}$.

\paragraph{Задача 2.} (Д. Кралчев) \mbox{} %\\

Режем квадрата на 6 еднакво широки вертикални ленти, а после всяка лента режем на 8 еднакво високи правоъгълника.

Така получаваме разрязване на квадрата на 48 еднакви правоъгълника.
Всеки правоъгълник е с ширина $7/3$ и височина $7/4$. 
Най-отдалечените точки в такъв правоъгълник са краищата на всеки от диагоналите му. Пресмятаме дължината на диагонала, тя е $35/12$, по-малка е от $3$.

Всяка от дадените в условието 49 точки ще попадне в някой от 48-те правоъгълници.
Ако точка лежи на граница или връх на правоъгълник, тогава тя попада едновременно в няколко правоъгълника, но в този случай и съпоставяме кой да е от тях. 

Така получената функция изобразява 49-те точки в 48 правоъгълника и съгласно принципа на Дирихле поне 2 точки ще лежат в общ правоъгълник.
Разстоянието между тях е по-малко от 3.

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

Нека $A\subset \mathbb{N}$ е произволно подмножество на естествените числа.
Съпоставяме му характеристичната редица $\alpha=\alpha_0\alpha_1\alpha_2\ldots$, 
такава че $\alpha_i$ е $1$, когато $i\in A$ и $0$, когато $i\notin A$. 
От лекции знаем, че това съоветствие е биективно.

Дефинираме функция $f(\alpha)=(\alpha_{e},\alpha_{o})$ така:

$\alpha_{e}=\alpha_0\alpha_2\alpha_4\ldots$ се състои от четните битове на $\alpha$. 

$\alpha_{o}=\alpha_1\alpha_3\alpha_5\ldots$ се състои от нечетните битове на $\alpha$. 

Лесно се проверява, че $f$ е биекция от множеството на характеристичните редици към множеството от наредените двойки характеристични редици.

Ако означим с $A_e$ и $A_o$ множествата от естествени числа, съответни на характеристичните редици $\alpha_{e}$ и $\alpha_{o}$, получаваме композиция от биекции:

$A \to \alpha \to f(\alpha)=(\alpha_{e},\alpha_{o}) \to (A_e,A_o)$

Тази композиция е биекция между множествата $2^\mathbb{N}$ и $2^\mathbb{N}\times 2^\mathbb{N}$.

\emph{Забележка:} На лекции обсъдихме факта, че мощността на $2^\mathbb{N}$ съвпада с мощността на множеството реални числа в интервала $(0,1)$, също и с мощността на континуума (множеството на всички реални числа, множеството от точките върху права линия).  
От представената задача следва, че същата мощност ще имат множествата от точки, разположени във вътрешността на единичен квадрат или пък всички точки в равнината или пространството, т.е. има биекция между отворения интервал $(0,1)$ и $\mathbb{R}^3$.

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

Нека първо построим биекция $f:\mathbb{Z}\to\mathbb{N}$.

Една примерна биекция е:\\
%$f(0)=0$\\
$f(n)=2n$ ако $n\ge0$\\
$f(n)=2|n|-1$ ако $n<0$

Дефинираме релация $\prec$ върху $\mathbb{Z}$ така: $n\prec m$ когато $f(n)<f(m)$.

Като ползваме биективността на $f$ и дефиницията на $\prec$ можем да проверим, че тя наследява всички свойства на релацията $<$  върху $\mathbb{N}$: $\prec$ е антирефлесивна, силно антисиметрична, транзитивна и добра наредба върху $\mathbb{Z}$.

$\prec$ не е нормалната числова наредба върху $\mathbb{Z}$.
Нека $n=1, m=-2$. Очевидно $n\prec m$, защото $f(n)=2, f(m)=3$, но $n>m$. 

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

%Нека $R$ е наредба в крайното множество $A$.

%Докажете, че $R$ добра наредба точно когато е линейна.

Тъй като всяка добра наредба е линейна, остава да докажем, ако $R$ е линейна наредба в крайното множество $A$, тя ще бъде и добра наредба.

Нека $B\ne\emptyset, B\subset A$.
На лекции сме доказали, че ако $R$ е наредба в крайното множество $A$, 
то $B$ съдържа минимален елемент $x$, такъв че $\forall y\in B, x\ne y \to \lnot yRx$.
 
Но $R$ е линейна, за всяка двойка $(x,y), \lnot yRx \to xRy$, 
следователно $\forall y\in B, x\ne y \to xRy$ и $x$ е най-малък елемент в $B$. 

Доказахме, че произволно избраното непразно подмножество $B$ има най-малък елемент, следователно $R$ е добра наредба.  

\end{document}