\documentclass[a4paper,11pt,fleqn]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1,T2A]{fontenc}
\usepackage[english,bulgarian]{babel}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{xparse}
\usepackage{mathtools}
\usepackage{pifont}

\reversemarginpar	

\setlength{\textheight}{24cm}
\setlength{\textwidth}{19cm}
\setlength{\hoffset}{-1cm}
 \setlength{\voffset}{-1cm}



\begin{document}
	
\begin{center}
  \textsc{Домашно №1 по Дискретни Структури на специалност Компютърни Науки, 2~поток,\\ зимен семестър 2023/2024г.,
    \\ \vspace{2mm} {\sl \small \today}}
\end{center}
\vspace{.2cm}
	
\noindent
\makebox[11cm]{Име:\dotfill}
\makebox[5cm]{Ф№:\dotfill}
\makebox[1.8cm]{Група:\dotfill}

\noindent
\begin{center}
  \begin{tabular}{|c|c|c|c|c||c|}
    \hline
    \textbf{Задача}  & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{Макс.} \\
    \hline
    \hline
    \emph{получени точки} & & & & & \\[1ex]
    \hline
    \emph{от максимално} & \makebox[1.5cm]{25} & \makebox[1.5cm]{20} & 
                                                                       \makebox[1.5cm]{20} &  \makebox[1.5cm]{35} &
                                                                                                                    \makebox[1.6cm]{100} \\
    \hline
  \end{tabular}
\end{center}
	
\vspace{.2cm}
\noindent
\rule{\linewidth}{0.1mm}
	
\vspace{1cm}
\noindent
\textbf{Задача 1:} \; % Докажете по индукция по $n$, че за всяко цяло
% положително $n$ е в сила
% \[
%   \frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 2
% \]
Представете си игра с един играч (\emph{solitaire}).  Дадени са $n$
монети.  Номиналите на монетите са без значение.  Монетите са наредени
вертикално в една купчина.  На всеки ход, играчът избира една купчина,
имаща повече от една монета, и разбива тази купчина на две произволни
непразни купчини.  При това получава печалба, равна на произведението
от броя на монетите в тези две купчини.  Примерно, ако играчът избере
купчина с $11$ монети и я разбие на една купчина с $6$ монети и друга
с $5$ монети, печалбата е $5 \times 6 = 30$.  Играта завършва, когато
всяка купчина е с точно една монета.  Печалбата в цялата игра е сумата
от печалбите от всички разбивания.

\medskip
\noindent
Докажете по индукция, че печалбата винаги е $\binom{n}{2}$
\textbf{независимо} от това как точно играе играчът.


\vspace{1cm}
\noindent
\textbf{Задача 2:} \;  Нека $f: \mathbb{R} \rightarrow \mathbb{R}$
и $g: \mathbb{R} \rightarrow \mathbb{R}$ са произволни биекции.  Дефинираме
две други функции $h$ и $t$ така:
\begin{align*}
  & \forall x \in \mathbb{R} : h(x) = f(x) + g(x) \\
  & \forall x \in \mathbb{R} : t(x) = f(x) g(x) 
\end{align*}
Докажете или опровергайте, че:
\begin{itemize}
\item $h$ е биекция.\marginpar{\hfill \small \textsl{10 т.}}
\item $t$ е биекция.\marginpar{\hfill \small \textsl{10 т.}}
\end{itemize}

	
\vspace{1cm}
\noindent
\textbf{Задача 3:} \; Нека
$A = \{ x \in \mathbb{R} \, | \, -\pi \leq x \leq \pi\}$.  Дефинираме
релацията $R \subseteq A^2$ така:
\[
  \forall x, y \in A \; \bigl( x R y \; \leftrightarrow \; (x = y) \vee ( x \in \{-\pi,\pi\} \wedge y \in \{-\pi,\pi\} ) \bigr)
\]
\begin{itemize}
\item Докажете, че $R$ е релация на еквивалентност.\marginpar{\hfill \small \textsl{10 т.}}
\item Нека \marginpar{\hfill \small \textsl{10 т.}}  за всяко
  $x \in A$ дефинираме множеството $T_x$ така:
  \[
    T_x = \{ y \in A \, | \, x R y \}
  \]
  Нека $Z$ е множеството, дефинирано така
  \[
    Z = \{ T_x \, | \, x \in A \}
  \]
  Отговорете дали $Z$ е крайно, изброимо безкрайно или неизброимо
  безкрайно.  Трябва да обосновете отговорите си добре.
\end{itemize}


\vspace{1cm}
\noindent
\textbf{Задача 4:} \; За всяко цяло положително число $n$
 дефинираме множеството $M_n$ така:
\[
  M_n = \{ \{ a_1, \ldots, a_k \}_M \, | \, a_1 + \cdots + a_k = n \}
\]
Примерно,
\begin{align*}
  M_1 & = \bigl\{ \{ 1 \}_M \bigr\} \\
  M_5 & = \bigl\{ \{ 5 \}_M, \{ 1, 4 \}_M, \{ 2, 3 \}_M, \{ 1, 1, 3 \}_M, \{ 1, 2, 2 \}_M, \{ 1, 1, 1, 2 \}_M, \{ 1, 1, 1, 1, 1 \}_M \bigr\}
\end{align*}
Дефинираме още $M_{n,o}$ и $M_{n,d}$ така
\begin{align*}
  M_{n,o} & = \{ X \in M_n \, | \, \text{ елементите на } X \text{ са нечетни} \} \\
  M_{n,d} & = \{ X \in M_n \, | \, \text{ елементите на } X \text{ са два по два различни} \} 
\end{align*}
Примерно,
\begin{align*}
  M_{1,o} & = \{ \{ 1 \}_M \} \\
  M_{1,d} & = \{ \{ 1 \}_M \} \\
  M_{5,o} & = \{ \{ 5 \}_M, \{ 1, 1, 3 \}_M, \{ 1, 1, 1, 1, 1 \}_M \} \\
  M_{5,d} & = \{ \{ 5 \}_M, \{ 1, 4 \}_M, \{ 2, 3 \}_M \}
\end{align*}
Както виждате, $|M_{1,o}| = |M_{1,d}|$ и $|M_{5,o}| = |M_{5,d}|$.
Това не е случайно -- за всяко цяло положително $n$ е вярно, че
$|M_{n,o}| = |M_{n,d}|$.  Вашата задача е да намерите и обосновете
явна биекция $f : M_{n,o} \rightarrow M_{n,d}$.

\medskip
\noindent
\emph{Упътване: алгоритъмът ``взема'' мултимножество, чиято сума е
  $n$.  Ако тези числа са две по две различни, примерно
  $\{ 3, 11, 15\}_M$, има ли смисъл да се прави още нещо?  Ако има
  повтарящи се числа, примерно $\{ 3, 3, 3, 3, 3, 3, 11, 11, 15 \}_M$,
  представете $n$ като сума от произведения от числата и кратностите
  им; в този пример $55 = 3 \times 6 + 11 \times 2 + 15 \times 1$.
  Представете всяка кратност като \underline{сума} от степени на
  двойката.  Ако отворите скобите, какво получавате?  }


	
\end{document} 
