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

%\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}
Контролно по Дискретни структури, 01.12.2019г.
\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. } 
Докажете, че за всяко естествено $n>0$ е вярно равенството:
\[1+3+5+\ldots+(2n-1)=n^2\]

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

\paragraph{Задача 2. }
Всяка точка в пространството $\mathbb{R}^3$ е оцветена в синьо, червено, или жълто.
Докажете, че както и да са оцветени точките, за всяко $r>0$ съществуват две едноцветни точки на разстояние, равно на $r$.

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

\paragraph{Задача 3. } 
Дадени са два квадрата, с дължини на страните съответно 1 см и 3 см.
Постройте биекция между точките от вътрешността на двата квадрата.

\paragraph{Задача 4. } 
На планетата Тралфамадор\footnote{
\emph{от Уикипедия:}

Тралфамадор е родната планета на извънземните пришълци в някои от романите на Кърт Вонегът.

Детайлите за жителите и се променят от роман в роман.

В 'Кланица-5' те са същества, които съществуват паралелно във всички времеви точки. Така те са привилегировани да познават бъдещи събития, включително виждат разрушаването на Вселената, когато Тралфамадорски пилот-изпитател изпробва нов модел двигател за космически кораб. Те отвличат героя на романа Били Пилгрим и го затварят в прозрачна клетка в зоопарка на Тралфамадор заедно с отвлечена известна земна порноактриса.

В 'Сирените на Титан' Тралфамадор е родина на цивилизация от роботи, които изпращат своя пратеник Сало да отнесе послание към обитателите на далечна галактика. След повреда на кораба му, Сало е принуден да кацне на Титан, спътник на Сатурн, и там изчаква пристигането на необходимата му резервна част. Посредник при доставката е земният жител Уинстън Найлс Ръмфорд. Сало съществува и се движи по нормалните физически закони, докато Ръмфорд и кучето му са размити във времето, подобно на тралфамадорците в 'Кланица-5'.

В 'Бога да Ви поживи, мистър Розуотър' се описва еволюцията на планетата. Когато технологииите на Тралфамадор се развили достатъчно, нормалните живи същества, подобни на нас, хората, постепенно били изместени от машини-роботи, толкова съвършени, че за жителите на Тралфамадор животът загубил смисъла си и те се самоубили масово.
}
се играе хазартна игра, като играчите хвърлят 3 зарчета на всеки ход.
Зарчето има 12 страни
\footnote{Зарчето е с форма на додекаедър -- многостен с 12 правилни петоъгълника за стени.},
на които са обозначени от една до 12 точки. 

Комбинация на зарчетата наричаме тройката числа, която съответства на броя на точките върху горната страна на падналите зарчета.
Както и на Земята, редът на числата няма значение, 
тоест тройките $(2,7,11)$ и $(11,2,7)$ представят една комбинация.

Колко са възможните комбинации при хвърляне на зарчета на Тралфамадор?

\paragraph{Задача 5. }
%Намерете кратка формула за сумата: \[\sum_{i=0}^{n}{\binom{2n+1}{i}}\]
%Докажете верността \'{и}.
Нека $A=\{ x | x \in \mathbb{R} , 0 \le x <5 \}$, а $R\subseteq A\times A$ е релация, определена така:

$R=\{(x,y)| x-y \in \mathbb{Z} \}$

(a - 3 точки) -- Докажете, че $R$ е релация на еквивалентност. Опишете класа $[\sqrt{2}]$.

(b - 3 точки) -- Докажете, че множеството от класове на еквивалентност спрямо $R$ е неизброимо.

\newpage

\subsection*{Примерни решения:}

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

Тривиална индукция.

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

Да разгледаме правилен тетраедър с дължина на ръба $r$. Четирите върха
на тетраедъра са оцветени в три цвята. 

От принципа на Дирихле следва, че поне два върха са оцветени в един и същи цвят. 
Разстоянието между тях е $r$, това решава задачата.

%Да разгледаме правилен тетраедър ABCD с дължина на ръба r. Четирите върха на тетраедъра са оцветени в три цвята. От принципа на Дирихле следва, че някои два върха, например A и B, са оцветени в един и същи цвят. Освен това |AB| = r, така че точките A и B удовлетворяват всички изисквания от условието на задачата.

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

Разполагаме двата квадрата така, 
че единият им връх е в началото на координатната система, в точка $(0,0)$,
а диагонално противоположният връх е съответно в точки $(1,1)$ и $(3,3)$.

Една възможна биекция от малкия към големия квадрат е $f(x,y)=(3x,3y)$.

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

Търсим конфигурации без наредба, с повтаряне.
Всяко хвърляне на зарче е избор на число от множеството $\{ 1, 2 \ldots 12 \}$.
Избираме 3 пъти, като можем да повторим избора (да хвърлим 2 или 3 еднакви зара).

Общата формула за избор на $k$ елемента от множество с $n$ елемента е $\binom{n+k-1}{k}$.
В задачата $k=3$, а $n=12$.

Броят комбинации е $\binom{12+3-1}{3}=\binom{14}{3}=14.13.2=364$.


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

Проверката, че $R$ е релация на еквивалентност е тривиална.
 
(a) $[\sqrt{2}]=\{\sqrt{2}-1,\sqrt{2},\sqrt{2}+1,\sqrt{2}+2,\sqrt{2}+3\}$

(b) Нека $x>y$ са числа в интервала $(0,1)$. 
Тъй като разликата им $0<x-y<1$ не е цяло число, те пораждат различни класове на еквивалентност.

Следователно, класовете са поне колкото са числата от интервала $(0,1)$, а на лекции сме показали, че последните образуват неизброимо множество.
 

\end{document}
