\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}
Контролно по Дискретни структури, 02.12.2017г.
\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.} 
Нека $x \in \mathbb{R}, x>0$, а $n \in \mathbb{N}, n>0$. Докажете, че $(1+x)^n\ge 1+nx$.
%Докажете, че числото $n^3+2n$ се дели на 3 за $\forall n \in \mathbb{N}$.

\paragraph{Задача 2.}
Тази есен във ФМИ учат 50 студенти с име от множеството \{ Иван, Георги, Стефан, Никола \}.
Докажете, че измежду тези студенти има такива, които имат имен ден на една и съща дата, и са родени в един и същ месец.

\paragraph{Задача 3.} Полетата от шахматната дъска представяме като множество от двойки $(i,j)$, 
където $i$ е номер на вертикал, а $j$ - номер на хоризонтал -- 
$C=\{(i,j)|i\in I_8, j \in I_8\}$.

Определяме релацията $R$ между двойки полета така -- $(i,j)R(u,v)$ когато офицер, 
разположен на полето $(i,j)$ може с няколко хода да достигне полето $(u,v)$.

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

(б) Колко класа на еквивалентност има $R$, 
има ли специално обозначаване на тия класове върху шахматната дъска?


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

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

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

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

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

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

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

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

\paragraph{Задача 5.}
Дадени са функции  $f: A \to B$ и  $g: A \to B$, които са биекции. 
Известно е, че  $\exists a \in A: f(a)\neq g(a)$ (функциите се различават при някоя стойност на аргумента). 

Докажете, че $\exists b \in A: a \neq b, \; f(b)\neq g(b)$ (функциите се различават и при друга стойност на аргумента).



%\end{document}

\newpage

\subsection*{Решения:}

\paragraph{\mbox{Задача 1.}} \mbox{}
%Нека $x \in \mathbb{R}, x>0$, а $n \in \mathbb{N}, n>0$. Докажете, че $(1+x)^n\ge 1+nx$.

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

(1) За $n=1$ твърдението е очевидно.

(2) Нека неравенството е вярно за $n$:
\[(1+x)^n\ge 1+nx\] 
И двата израза са положителни, 
умножаваме ги по $1+x>0$:
\[(1+x)^{n+1}\ge (1+nx)(1+x)\]
Разкриваме скобите в дясната част:
\[(1+x)^{n+1}\ge 1+(n+1)x+nx^2\]
Членът $nx^2>0$, следователно:
\[(1+x)^{n+1}\ge 1+(n+1)x+nx^2 > 1+(n+1)x\]
Неравенството е вярно и за $n+1$: 
\[(1+x)^{n+1}\ge 1+(n+1)x\]
От принципа на индукцията следва, че е вярно за всяко $n\in \mathbb{N} $.


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

На всеки студент съпоставяме двойка от вида (име, месец на раждане).
Броят на различните двойки е най-много 48 (4 възможни имена, 12 възможни месеца на раждане).

Тъй като студентите са 50, съпоставянето не е биекция.
Съгласно принципа на Дирихле ще има поне двама студенти на които сме съпоставили една и съща двойка (име, месец).
Те ще празнуват имен ден на една и съща дата и рожден ден в един и същ месец.

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

(a) Релацията $R$ е релация на еквивалелнтност не само за офицер, 
а за всяка шахматна фигура освен пешка, по следните причини:

(1) $R$ е рефлексивна, защото фигурата може да направи ход, а при следващия ход да се върне на изходното поле.

(2) $R$ е симетрична, защото фигурата може да направи поредица ходове, а след това да изпълни същата поредица наобратно и да се върне на изходното поле.

(3) $R$ е транзитивна, защото фигурата може да направи поредица ходове от поле $(i,j)$ до поле $(u,v)$, а след това да изпълни нова поредица от поле $(u,v)$ до поле $(x,y)$. Последователното изпълнение (композицията) на двете поредици мести фигурата от поле $(i,j)$ до поле $(x,y)$.

(b) При игра на шах офицерите се движат по диагонал.
При такова движение броят полета изминати по хоризонтал (без значение наляво или надясно) е равен на броя полета, изминати по вертикал (без значение нагоре или надолу). Нека този брой е $k$.

Формално от поле $(i,j)$ за един ход офицерът ще попадне в поле $(i\pm k, j\pm k)$.
При такова движение четността на сумата от координатите $i+j$ се запазва.

Нека наречем \textbf{бели} полетата с четна сума на координатите и 
\textbf{черни} полетата с нечетна сума на координатите (на обичйната шахматна дъска полетата са боядисани по този начин).

От предните разсъждения е ясно, че офицер не може да се премести от бяло на черно поле и обратно.
Следователно има поне два класа на еквивалентност. 


Доказателство, че белите полета образуват един клас на еквивалентност:

(i) от поле $(1,1)$ с един ход се достига до полета от вида $(i,i), \, i=2,3 \ldots 8$.

(ii) Нека полето $(u,v), \, u\neq v$ има различни координати и е бяло.
Нека $u>v$ (другият случай е симетричен). Тък като $u+v$ е четно, следователно и $u-v$ е четно.
Нека $u-v=2k>0$, тогава $u-k=v+k$, нека $i=u-k=v+k$ или $u=i+k, v=i-k$.
От поле $(i,i)$ с един ход се достига до поле $(u,v)=(i+k,i-k)$. 

Показахме, че с най-много два хода офицер достига от поле $(1,1)$ до всяко бяло поле.

Подобно доказателство можем да направим и за черните полета.

Следователно класовете на еквивалентност са два -- белите и черните полета на шахматната дъска.

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

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

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

Броят комбинации е $\binom{8+3-1}{3}=\binom{10}{3}=120$.

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

%Дадени са функции  $f: A \to B$ и  $g: A \to B$, които са биекции. 
%Известно е, че  $\exists a \in A: f(a)\neq g(a)$ (функциите се различават при някоя стойност на аргумента). 

%Докажете, че $\exists b \in A: a \neq b, \; f(b)\neq g(b)$ (функциите се различават и при друга стойност на аргумента).

По условие съществува $ a \in A: f(a)\neq g(a)$, нека $f(a)=y, y\in B$.
Функцията $g$ е биекция, следователно обратната и функция $g^{-1}$ съществува и също е биекция.

Нека $g^{-1}(y)=b$. Ако допуснем $a=b$ получаваме $g(a)=g(b)=g(g^{-1}(y))=y$, 
противоречие с условието $f(a)\neq g(a)$. Следователно $a \neq b$.

Вече пресметнахме $g(b)=y$, ако допуснем, че $f(b)=y$ ще се окаже, че $f$ не е инекция, тъй като $f(a)=y$.
Намерихме $b$, такова че $a \neq b, \; f(b)\neq g(b)$.


\end{document}