
\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{Домашняя работа 12.}{Паросочетания}
	\begin{task}{COMB}{141}
		(1 балл) Доказать, что в непустом $k$-регулярном двудольном графе всегда существует
		совершенное паросочетание.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{142}
		(2 балла) Пусть $D_n = \{a_1,  \dots , a_n\}$ есть множество натуральных чисел. Известно, что среди любых
		трех из них всегда можно выбрать два числа, одно из которых делится на другое. Доказать,
		что эти числа можно покрасить в два цвета так, чтобы для любых двух чисел одного цвета одно
		делилось бы на другое. Обобщить данный результат на случай, когда среди любых $m$ чисел
		можно выбрать ровно два числа, одно из которых делилось бы на другое.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{143}
		(1 балл) Пусть $A = (A_1, \dots, A_m)$ есть набор из $m$ подмножеств $n$-элементного множества $Y$. 
		Системой различных представителей для $A$ называется подмножество $\{a_1, \dots, a_m\}$ 
		различных элементов $a_i \in A$, таких, что для любого $i$ элемент $a_i \in A_i$. 
		Доказать, что $A$ обладает такой системой тогда и только тогда, когда $|\bigcup\limits_{i \in S} A_i| \ge |S|$ 
		для любого подмножества $S \subseteq {1, 2, \dots, m}$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{144}
		(1 балл) Матрицей $P$ перестановок называется квадратная бинарная матрица, в которой ровно
		одна единица стоит в каждой строке и в каждом столбце. Любая такая матрица является, по
		сути, матричным представлением некоторой перестановки $\sigma$. Доказать, что любая квадратная
		матрица $n \times n$, состоящая из неотрицательных целых чисел, выражается в виде суммы $k$ матриц
		перестановок тогда и только тогда, когда сумма чисел в любой строке, а также сумма чисел в
		любом столбце равны $k$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{145}
		(1 балл) Найти количество $X$-насыщенных паросочетаний в полном двудольном графе
		$K_{n,m}$ с долями $X$ и $Y$, $|X| = n$, $|Y| = n$, $n \le m$.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}