
\documentclass[12pt,fleqn,a4paper]{article}

\usepackage[russian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{ntheorem}
\usepackage{tikz}
\usepackage{verbatim}

\usetikzlibrary{arrows,shapes}

\tikzstyle{vertex}=[circle,fill=black,minimum size=3pt,inner sep=0pt]
\tikzstyle{edge} = [draw,thick,-]

\newtheorem{definition}{Определение}
\newtheorem*{solution}{Решение}

\newenvironment{task}[2] {
	\noindent\fbox{\bf {#1} {#2}.}
}{
}

\newcommand{\mytitle}[2] {
  \begin{center}
      \bf {#1} {#2}.
  \end{center}
}

\let\origenumerate\enumerate
\let\origendenumerate\endenumerate
\renewenvironment{enumerate}{\origenumerate[topsep = 0pt, noitemsep]}{\origendenumerate}

\begin{document}
	\mytitle{Домашняя работа 3.}{Рекуррентные соотношения и графы}
	\begin{task}{COMB}{27}
		(1,5 балла) Построить общее решение неоднородного рекуррентного соотношения второго порядка $a_{n + 2} = 3 a_{n + 1} - 2 a_n + \sin(n \pi / 2)$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{28}
		(1 балл) В теннисном турнире участвуют $2n$ игроков. Составить и решить рекуррентное соотношение для количества $a_n$
		различных пар, которые можно сформировать для $n$ матчей первого круга.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{29}
		(1 балл) На плоскости нарисованы $n$ окружностей так, что любая пара окружностей пересекается ровно по двум точкам, 
		и никакие три окружности не имеют общей точки пересечения. Определить количество $a_n$ областей, 
		на которые разбивается плоскость такими окружностями.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{30}
		(3 балла) Доказать, что числа Фибоначчи $F_n$ удовлетворяют следующим соотношениям:
		\begin{enumerate}
			\item[(а)] $F_{n + m} = F_{n - 1} F_m + F_n F_{m + 1}$;
			\item[(б)] $F_1 + F_3 + \dots + F_{2n - 1} = F_2n$;
			\item[(в)] $F_1^2 + \dots + F_n^2 = F_n F_{n + 1}$.
		\end{enumerate}
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{31}
		(2 балла) Докажите, что $\mathrm{gcd}(F_n, F_m) = F_{\mathrm{gcd(n, m)}}$, где $\mathrm{gcd}(a, b)$ --- это наибольший общий делитель $a$ и $b$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{32}
		(1 балл) Пусть в графе $G$ ровно две вершины имеют нечетную степень. Доказать, что в они являются связанными.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{33}
		(1 балл) Описать все графы на $n$ вершинах, для которых любая $n$-перестановка является автоморфизмом.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}