\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.2018г.
\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. } 
Редицата на Фибоначи дефинираме така:

(1) $F_0=0, \quad F_1=1$

(2) $F_n=F_{n-1}+F_{n-2}$ за $n>1$

Докажете, че членовете от вида $F_{3k}$ са четни.

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

\paragraph{Задача 2.}
Множеството $A$ съдържа 1010 естествени числа от $I_{2018}=\{1, 2, 3, \ldots, 2018\}$.

Докажете, че има две числа от $A$, чиято сума е 2019.

\emph{Упътване:} Нека $B$ се състои от числата от вида $2019-i$, където $i \in A$.
Разсъждавайте за сечението на $A$ и $B$, възможно ли е $A\cap B=\emptyset$ ?

\paragraph{Задача 3. } Точките в равнината можем да представим чрез техните координати като двойки реални числа: 
$\mathbb{R}^2=\Bigl\{(x\,,\,y)\;|\; x\in\mathbb{R}\:,\; y\in\mathbb{R}\Bigr\}$. 
Релацията $P\subseteq\mathbb{R}^2\times\mathbb{R}^2$ е определена по следния начин: 
\[
P\;=\;\Bigl\{\;\Bigl( (x_1,y_1)\,,\,(x_2,y_2)\Bigr)\;\Bigl| \; 
 x_1+y_1 =\, x_2+y_2 \,\Bigr\}\,
\]
a)\; Да се докаже, че \,$P$\, е релация на еквивалентност.\hfill(3 точки)\\
б)\; Да се опише и начертае класът на еквивалентност на точката $(2,3)$.\hfill(3 точки)



\paragraph{Задача 4} Дадено е крайно множество $A$ и тотална функция $f: A \to A$, която е инекция. Докажете, че $f$ е биекция.

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

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

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

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

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

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

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

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

\paragraph{Задача 5.}
Намерете кратка формула за сумата: \[\sum_{i=0}^{n}{\binom{2n+1}{i}}\]

%Намерете кратка формула за сумата 
%\begin{displaymath}\sum_{i=0}^{n}{\binom{2n+1}{i}}\end{displaymath}.

Докажете верността \'{и}.



\newpage

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

\paragraph{Задача 1. } 
%Редицата на Фибоначи дефинираме така:

%(1) $F_0=0, \quad F_1=1$

%(2) $F_n=F_{n-1}+F_{n-2}$ за $n>1$

%Докажете, че членовете от вида $F_{3k}$ са четни.

Доказателството извършваме с индукция по $k$, но доказваме по-сложно твърдение:

Членовете от вида $F_{3k}$ са четни, а членовете от вида $F_{3k+1}$ и $F_{3k+2}$ са нечетни.

(1) База: При $k=0$ първите 3 члена на редицата на Фибоначи са 
 $F_0=0, F_1=1, F_2=1$ и твърдението за четността им е вярно.

(2) Ако е вярно за $k$, верността за $k+1$ проверяваме, като ползваме рекурентното уравнение.

\paragraph{Задача 4.} 
%Дадено е крайно множество $A$ и тотална функция $f: A \to A$, която е инекция. 
%Докажете, че $f$ е биекция.
Нека $B=\{y : \exists x \in A, y=f(x)\}$ е множеството от значенията на $f$. 

Ако $A=B$, то $f$ е биекция. 

Ако $B$ е същинско подмножество на $A$, то има по-малко елементи и тогава, съгласно с принципа на Дирихле, поне два елемента на $A$ ще бъдат изобразени от $f$ в един елемент на $B$, което противоречи на условието, че $f$ е инекция.

\paragraph{Задача 5.}
Кратката формула е: 

\[\sum_{i=0}^{n}{\binom{2n+1}{i}}=2^{2n}\]


Верността \'{и} следва от факта, че сумата на всички биномни коефициенти от вида 
$\binom{2n+1}{i}$ е $2^{2n+1}$, а в задачата сумираме само половината коефициенти
-- тези с номера от $0$ до $n$. 

От тривиалното равенство $\binom{2n+1}{i}=\binom{2n+1}{2n+1-i}$ следва, че на всеки коефициент с малък номер съответства равен нему коефициент с голям номер, а оттам и равенството на сумите:

\[\sum_{i=0}^{n}{\binom{2n+1}{i}}=\sum_{i=n+1}^{2n+1}{\binom{2n+1}{i}}\]

Следователно търсената сума е половината от сумата на всички коефициенти.

\end{document}