\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.2016г.
Първо домашно по Дискретни структури, условия и решения
\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.} 
Нека $f:\mathbb{R}\to \mathbb{R}$ е определена така:
\begin{align*}
 f(x)&=\frac{2x-7}{5}
\end{align*}

(a) Докажете, че $f$ е биекция

(b) Изразете в явен вид (чрез формула) обратната \`{и} функция $f^{-1}$.


\paragraph{Задача 2.} 49 точки лежат в квадрат със страна 14. 
Докажете, че поне две от тях са на разстояние по-малко от 3. 

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

\paragraph{Задача 3.} 
Нека $\mathbb{N}$ е множеството на естествените числа, а $2^\mathbb{N}$ е множеството от подмножествата му.
% $\{0, 1, 2, \ldots\}$. 
Постройте биекция между множествата $2^\mathbb{N}$ и $2^\mathbb{N}\times 2^\mathbb{N}$.

\paragraph{\mbox{Задача 4.}}
Добра наредба в множеството $A$ е линейна наредба, такава, че всяко непразно подмножество на $A$ има най-малък елемент.

Обичайната числова релация $<$ не е добра наредба върху множеството $\mathbb{Z}$ (обяснете защо).

Постройте добра наредба $\prec$ върху $\mathbb{Z}$.

Посочете примерна двойка числа $(m,n)$, за които $m\prec n$, но $m>n$.

\paragraph{\mbox{Задача 5.}}
Нека $R$ е наредба в крайното множество $A$.

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

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


