\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} Първо домашно по Дискретни структури, 10.11.2017г. %Първо домашно по Дискретни структури, условия и решения \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.} Докажете, че за всяко естествено $n\ge 2$ е вярно равенството: \[(1-\frac{1}{2^2})(1-\frac{1}{3^2})\ldots(1-\frac{1}{n^2})=\frac{n+1}{2n}\] \paragraph{Задача 2.} %5 точки лежат в равностранен тригълник със страна 2. %Докажете, че поне две от тях са на разстояние по-малко или равно на 1. Нека $\alpha$ е реално, а $n$ е положително естествено число. Докажете, че някое от числата $\alpha,2\alpha,3\alpha \ldots n\alpha$ е на растояние най-много $\frac{1}{n}$ от някое цяло число. \emph{Упътване:} Ползвайте принципа на Дирихле. \paragraph{Задача 3.} Нека $\mathbb{N}$ е множеството на естествените числа, а $\mathbb{S}_+$ е множеството от строго растящи крайни редици от естествени числа: \[\mathbb{S}_+=\{(n_0,n_1\ldots n_k)|k\in\mathbb{N}, n_i\in\mathbb{N}, n_0n_0$ и за всяко $i$ е изпълнено неравенството $q_i 1/n$, за всяко $i$. Разделяме интервала $[0,1)$ на $n$ равни подинтервала -- $[0,1/n), [1/n,2/n), \ldots ,[{n-1}/n,1)$. Числата ${\beta}_i$ са точно $n$ на брой, ако някое от тях е в подинтервала $[0,1/n)$, задачата е решена, съгласно \emph{Разсъждение A:}. Ако всичките са в останалите $n-1$ подинтервала, съгласно принципа на Дирихле поне две ще са в един подинтервал, тоест на разстояние по-малко от $1/n$. Нека тези две числа са ${\beta}_i \le {\beta}_j$, тогава: \begin{equation}\label{eq1} 0\le {\beta}_j-{\beta}_i \le 1/n \end{equation} \emph{Случай B.1:} Нека $ij$, да означим $k=i-j$, очевидно $1\le k < n$: В този случай ${\beta}_j-{\beta}_i = (j-i)\alpha+\lfloor i\alpha \rfloor-\lfloor j\alpha \rfloor$ и неравенството (\ref{eq1}) придобива вида: \[ 0\le (j-i)\alpha+\lfloor i\alpha \rfloor-\lfloor j\alpha \rfloor \le 1/n \] или \[ \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor \le (j-i)\alpha \le \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor + 1/n \] заместваме $k=i-j$ и получаваме: \[ \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor \le -k\alpha \le \lfloor j\alpha \rfloor - \lfloor i\alpha \rfloor + 1/n \] умножаваме по $(-1)$: \[ \lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor \ge k\alpha \ge \lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor - 1/n \] Оказа се, че $k\alpha$ е на разстояние най-много $1/n$ от цялото число $\lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor$ (в този случай е под цялото число). \paragraph{Задача 3.} \paragraph{Първи начин:} \mbox{} Нека $m$ е строго положително естествено число. Представяме го в двоична бройна система като редица от нули и единици. Нека в записа има $k+1$ единици, а номерацията на битовете е от дясно наляво и започваме от 0. Обхождаме битовете отдясно наляво и при срещане на единица записваме позицията \`{и} в редица. Нека най-дясната единица е на позиция $n_0$, следващата единица е на позиция $n_1$ и т.н. до старшата единица, която е най-вляво на позиция $n_k$. Описахме функция, да я обозначим $h$, която по числото $m$ строи редица $h(m)=(n_0,n_1\ldots n_k)$. Редицата е строго растяща (всички единици в двоичния запис са на различни позиции). За различни числа ще получим различни редици (инекция), а за всяка редица можем да построим двоичен запис и число, което я поражда (сюрекция). \emph{Пример:} Нека $m=22$, двоичният му запис е $10110$, единици има на позиции 1, 2 и 4, следователно $h(22)=(1,2,4)$ Функцията $h$ не е тотална, тя не е дефинирана за числото 0. Нека $H(n)=h(n+1)$, новата функция $H$ е биекция от естествените числа към всички растящи редици и е решение на задачата. \paragraph{Втори начин:} \mbox{} Нека $s=(n_0,n_1\ldots n_k)$ е растяща редица, дефинираме функцията $f_{+}(s)=2^{n_0}+2^{n_1}+ \ldots +2^{n_k}$. На произволната редица $s$ функцията $f_{+}(s)$ съпоставя число $m=f_{+}(s)$. Числото $m$ има единици в двоичния си запис точно на позиции $n_0,n_1\ldots n_k$, ако броим позициите от дясно на ляво, започвайки от 0 за младшия разряд в двоичния запис на $m$. Очевидно $f_{+}$ е биекция между $\mathbb{S}_+$ и строго положителните естествени числа. На всяка редица съпоставя число, на различните редици съпоставя различни числа, а всяко положително число е образ на редица от $\mathbb{S}_+$. Функцията $f(s)=f_{+}(s)-1=2^{n_0}+2^{n_1}+ \ldots +2^{n_k}-1$ ще е биекция от $\mathbb{S}_+$ към $\mathbb{N}$, обратната \`{и} функция $f^{-1}$ е решение на задачата. \paragraph{Задача 4.} \paragraph{Първи начин:} \mbox{} Нека $m$ е строго положително естествено число. Представяме го в двоична бройна система като редица от нули и единици. Нека в записа има $k+1$ единици, а номерацията на битовете е от дясно наляво и започваме от 0. Нека $n_0$ е броят нули надясно от най-младшата (най-дясна единица в двоичния запис). Обхождаме единиците отдясно наляво и броим колко нули има между всеки две единици при обхождането. Нека $n_1$ е броят нули между най-младшата единица до следващата вляво, $n_2$ е броят нули втората и третата единица и т.н. до $n_k$ -- броят нули между двете най-леви единици в записа. Описахме функция, да я обозначим $h$, която по числото $m$ строи редица $h(m)=(n_0,n_1\ldots n_k)$. За различни числа $m_1$ и $m_2$ ще получим различни редици $h(m_1)$ и $h(m_2)$ (инекция), а за всяка редица можем да построим двоичен запис и число, което я поражда (сюрекция). \emph{Пример:} Нека $m=22$, двоичният му запис е $10110$, дължините на интервалите нули са 1, 0 и 1, следователно $h(22)=(1,0,1)$ Функцията $h$ не е тотална, тя не е дефинирана за числото 0. Нека $H(n)=h(n+1)$, новата функция $H$ е биекция от естествените числа към всички редици и е решение на задачата. \paragraph{Втори начин:} \mbox{} Нека $s=(n_0,n_1\ldots n_k)$ е произволна редица от естествени числа. Дефинираме нова редица $s_{+}=(l_0,l_1\ldots l_k)$ индуктивно по $k$ така: (1) $l_0=n_0$ (2) за $i>0$ нека $l_i=l_{i-1}+n_i+1$. По-неформално, $l_i=n_0+n_1+1+n_2+1+\ldots + n_i+1$. Очевидно $s_{+}=(l_0,l_1\ldots l_k)$ е строго растяща редица. Функцията $g(s)=s_{+}$ е биекция, която на всяка редица $s\in \mathbb{S}$ съпоставя редица $s_{+} \in \mathbb{S}_{+}$. Да вземем функцията $f_{+}$ от решението на предната задача (втори начин). Нека $m=f_{+}(g(s))$. Числото $m$ ще съдържа в двоичния си запис единици на позиции $l_0,l_1\ldots l_k$. Редицата от броя на нулите между всеки две поредни единици в двоичния запис на $m$ ще е $n_0,n_1\ldots n_k$ (тук броим и нулите след последната единица, те са точно $n_0$). Функцията $h(s)=f_{+}(g(s))-1$ е биекция от $\mathbb{S}$ към $\mathbb{N}$, обратната \`{и} функция е решение на задачата. \paragraph{Задача 5.a} \mbox{} От дефиницията на $\prec$ следва, че $\{q_i\} \prec \{p_i\}$, когато някой член на $\{p_i\}$ е по-голям от всички членове на $\{q_i\}$. Казано по друг начин, някой член на $\{p_i\}$ е строга горна граница на $\{q_i\}$. Оттук директно следва антирефлексивността и антисиметричността на $\prec$. Транзитивността също се очевидна: от $\{q_i\} \prec \{p_i\} \prec \{r_i\}$ следва, че някое $r_{n_1}$ надвишава всички $\{p_i\}$. Някое $p_{n_0}$ надвишава всички $\{q_i\}$, следователно $r_{n_1} > p_{n_0}> q_i$, или $r_{n_1} > q_i$ за всяко $i$, откъдето следва $\{q_i\} \prec \{r_i\}$. \paragraph{Задача 5.b} \mbox{} Дефиницията на $\sim$ се състои от две отрицания. Отрицанието на $\{q_i\} \prec \{p_i\}$ изглежда така: за всяко $n_0$ съществува $j>n_0$, такова, че съществува $i$ за което $q_i \ge p_j$. Неравенството $q_i \ge p_j$ влече $q_i > p_{n_0}$. Казано по-просто, отрицанието на $\{q_i\} \prec \{p_i\}$ е: за всяко $n$ съществува $i$, такова че $q_i > p_n$. Дефиницията на $\{q_i\} \sim \{p_i\}$ е еквивалентна на твърдението: всеки член на $\{q_i\}$ е по-малък от някой член на $\{p_i\}$ и всеки член на $\{p_i\}$ е по-малък от някой член на $\{q_i\}$. (1) $\{p_i\} \sim \{p_i\}$, защото всеки член $p_i$ е по-малък от $p_{i+1}$ (редиците са растящи). Следователно $\sim$ е рефлексивна. (2) Симетричността на $\sim$ следва от симетричната дефиниция. (3) Транзитивност: Нека $\{q_i\} \sim \{p_i\} \sim \{r_i\}$. Избираме произволно $i_0$, за него съществува $i_1$, такова че $q_{i_0} < p_{i_1}$. За $i_1$ съществува $i_2$, такова че $p_{i_1} < r_{i_2}$, следователно $q_{i_0} < r_{i_2}$. Избираме произволно $j_0$, за него съществува $j_1$, такова че $r_{j_0} < p_{j_1}$. За $j_1$ съществува $j_2$, такова че $p_{j_1} < q_{j_2}$, следователно $r_{j_0} < q_{j_2}$. От неравенствата $q_{i_0} < r_{i_2}$ и $r_{j_0} < q_{j_2}$ и зависимостите между съответните индекси следва $\{q_i\} \sim \{r_i\}$. \paragraph{Задача 5.c} \mbox{} Да разгледаме произволна редица $\{q_i\} \in \mathbb{S}_Q^+$. Тя е строго растяща редица от рационални числа. Интересен е въпросът дали е ограничена. Има два случая за $\{q_i\}$: (случай 1) $\{q_i\}$ е ограничена. В този случай лесно се проверяват следните свойства: (1.a) $\{q_i\} \prec \{p_i\}$ точно когато някой член на $\{p_i\}$ е горна граница за $\{q_i\}$. (1.b) $\{q_i\} \sim \{p_i\}$ точно когато $\{p_i\}$ и $\{q_i\}$ имат еднакви горни граници. (случай 2) $\{q_i\}$ е неограничена. В този случай: (2.a) $\{q_i\} \prec \{p_i\}$ никога не е изпълнено. (2.b) $\{q_i\} \sim \{p_i\}$ точно когато $\{p_i\}$ е неограничена. \emph{Интерпретация, ако имаме реални числа $\mathbb{R}$:} Ако $\{q_i\}$ е ограничена, тя е сходяща, нека $\lim \{q_i\}=q \in \mathbb{R}$. Класът на еквивалентност $[\{q_i\}]$ се състои от всички редици със същата граница $q$. Ако $\{q_i\}$ е неограничена, тя е разходяща, $\lim \{q_i\}=+\infty$. Класът на еквивалентност $[\{q_i\}]$ се състои от всички неограничени редици. От направените дотук разсъждения следва, че множеството от класовете на еквивалентност на релацията $\sim$ е изоморфно на $\mathbb{R}\cup \{+\infty\}$. Терминът 'изоморфно' ползваме в смисъл на биективно съответствие, на всеки клас, породен от ограничена редица съответства реално число, на класа на неограничените растящи редици съпоставяме специалния символ $+\infty$. \emph{Интерпретация, ако нямаме реални числа:} Ако не разполагаме с конструкция на реалните числа, можем да ги дефинираме, като ползваме класовете на еквивалентност на релацията $\sim$. Ако вземем само ограничените редици от $\mathbb{S}_Q^+$, породените от $\sim$ класове образуват структура, върху която можем да дефинираме аритметични операции, наредба и свойства, удовлетворяващи интуицията ни за реалните числа. %Например строгата наредба се задава директно от релацията $\pred$. %Сумата на редици от два класа е нов клас, преставящ сума ... %\[LS=\{\{q_i\}|\{q_i\} \in \mathbb{S}_Q^+, \exists u\in \mathbb{Q} \, \forall i \, q_i