\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} \setlength{\parindent}{10pt} \setlength{\parskip}{1ex} \begin{document} \begin{center} Първо домашно по Дискретни структури, 09.11.2020 г. \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=\{A \; | \; A \subseteq \mathbb{N}, A$ е крайно $\}$. %е множеството от крайни подмножества на $\mathbb{N}$. Докажете, че $F$ е изброимо. %\emph{Упътване:} \paragraph{Задача 2.} Докажете, че за всяко $k \in \mathbb{N}$, съществува $n \in \mathbb{N}$, такова че: \[ \sum_{i=1}^{n}{\frac{1}{i}} > k \] %\emph{Упътване:} Пробвайте индукция. \paragraph{Задача 3.} 33 топа са разположени върху шахматна дъска. Покажете, че поне 5 от тях не се бият взаимно. %\emph{Упътване:} Ползвайте принципа на Дирихле. \paragraph{Задача 4.} Колко са редиците от естествени числа $x_1,x_2,\ldots,x_n$, такива че: $x_1+x_2+\ldots+x_n=m$ $\forall i \quad x_i>0$ \paragraph{\mbox{Задача 5.}} Разглеждаме множеството от точки в равнината, с $|PQ|$ означаваме дължината на отсечката $PQ$. Нека $A$ и $B$ са две точки в равнината. Определяме релацията $R = \{(M,N)|\; |MA|+|MB|=|NA|+|NB| \}$. %($M$ и $N$ са в релация, ако сумите от разстоянията им до точките $A$ и $B$ са равни). (a) Докажете, че $R$ е релация на еквивалентност. (b) Как изглеждат класовете на еквивалентност, породени от $R$, когато $A$ и $B$ съвпадат? (c) Как изглеждат класовете на еквивалентност, когато $A$ и $B$ са различни? \emph{Упътване:} За подточки (b) и (c) дайте кратък текстов отговор. За подточка (c), потърсете информация в Интернет. \vspace{20pt} \emph{Срок за предаване:} Предайте домашното на асистента на вашата група до 26 ноември 2020 г.! \emph{Правила за предаване:} Пратете мейл на асистента на вашата група с файлове, в някоя от следните форми: (1) Заснети или сканирани листи, на които сте написали решенията ръкописно. Ако снимате с телефон, опитайте да използвате приложение с функционалности като CamScanner. (2) Файлове във формат *.tex и *.pdf, изготвени по стандарта \LaTeX. На следващата страница има кратки инструкции за \LaTeX. \newpage \begin{center} \section*{Как да ползваме \LaTeX?} \end{center} \LaTeX \; е език за автоматизиране на издателската дейност. Като среда за типографска дейност, езикът е достъпен за различни операционни системи и е с отворен лиценз (open source). Той е създаден от Лесли Лампорд (Leslie Lamport), американски учен, по-известен с работите си по теория на разпределените компютърни системи, за които получава Тюрингова премия през 2013 г. \LaTeX \; е макро-разширение на \TeX, език за описание на типографската дейност, създаден около 1978 г. от Доналд Кнут (Donald Knuth), американски учен, по-известен с многотомника си "Изкуството на програмирането". Кнут е считан за баща на теорията за анализ на алгоритми, получава Тюрингова премия през 1974 г. %\href{https://www.latex-tutorial.com/tutorials/}{LaTex tutorial} \vspace{10pt} \paragraph{Първи стъпки:} \mbox{} \\ Започнете с учебника \url{https://www.latex-tutorial.com/tutorials/} Той съдържа инструкции за инсталиране на системата и въвежда в създаването на прости документи, ползването на математически формули и графика. \vspace{10pt} \paragraph{Образец:} \mbox{} \\ За да напишете решенията си, ползвайте сорса на този документ (файла с разширение .tex), публикуван в Мудъл. Изтрийте втората страница, съдържаща тези инструкции, а вашите решения опишете на последната страница. После компилирайте до формат *.pdf. \vspace{10pt} \paragraph{Полезни връзки:} \mbox{} \\ \url{https://en.wikipedia.org/wiki/LaTeX} \url{https://en.wikipedia.org/wiki/TeX} \url{https://www.latex-tutorial.com/tutorials/} \newpage \section*{Решения} \paragraph{Задача 1.} \mbox{} \\ \paragraph{Задача 2.} \mbox{} \\ \paragraph{Задача 3.} \mbox{} \\ \paragraph{Задача 4.} \mbox{} \\ \paragraph{Задача 5.} \mbox{} \\ \end{document}