\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