\documentclass{article}
\usepackage{cmap}
\usepackage{mathtext}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{epigraph}
\usepackage{fancybox,fancyhdr}
\usepackage{multicol}
\usepackage{float}
\usepackage{venndiagram}
\usepackage[top=0.7in, bottom=0.75in, left=0.625in, right=0.625in]{geometry}
\usepackage{ytableau}
\usepackage{amsmath,amssymb}
\DeclareMathOperator{\Exists}{\exists}
\DeclareMathOperator{\Forall}{\forall}
\newcommand\abs[1]{\left|#1\right|}

\title{\textbf{Домашняя работа 5 по дискретной математике}}
\author{Артем Стрельцов, группа 188-1}
\date{Дедлайн 18 октября 2018}

\begin{document}
\normalsize
\maketitle
\bigskip\bigskip
\part*{Задача 1}

\begin{center}
    Робот ходит по координатной плоскости. На каждом шаге он может увеличить одну координату на 1 или обе координаты на 2. Сколько есть способов переместить Робота из точки (0, 0) в точку (4, 5)?
\end{center}
\subsection*{Решение:}
Пусть $F(x, y)$ - количество способов попасть в точку $(x, y)$ из точки $(0, 0)$. Тогда
\begin{equation*}
F(x, y) =
 \begin{cases}
   F(x - 1, y) + F(x, y - 1) + F(x - 2, y - 2) &\; x, y \geq 2
   \\
   F(x - 1, y) + F(x, y - 1) & иначе
 \end{cases}
\end{equation*}
Естественно, рассматриваются только $x, y\geq 0$. \newline
Составим таблицу, каждая клетка которой отражает кол-во способов попасть в данную точку. Левая верхняя - точка $(0, 0)$, нижняя правая -- $(4, 5)$.\newline
\begin{tabular}{c c c c c c}
     1 & 1 & 1 & 1 & 1 & 1 \\
    1 & 2 & 3 & 4 & 5 & 6 \\
    1 & 3 & 7 & 12 & 18 & 25 \\
    1 & 4 & 12 & 26 & 47 & 76 \\
    1 & 5 & 18 & 47 & 101 & 189 \\
\end{tabular}
Отсюда получаем 189 способов попасть в клетку $(4, 5)$.

\bigskip\bigskip
\part*{Задача 2}

\begin{center}
    Какое слагаемое в разложении $(1 + 2)^n$ по формуле бинома Ньютона будет наибольшим?
\end{center}
\subsection*{Решение:}

$(1 + 2)^n = \sum\limits_{i=0}^{n} \left(_{k}^{n}\right) 2^k$. Получается, надо найти наибольшее слагаемое вида $\left(_{k}^{n}\right) 2^k$. Для этого сравним $\left(_{k}^{n}\right) 2^k$ и $\left(_{k + 1}^{n}\right) 2^{k + 1}$. Нам нужно наименьшее $k$, при котором $\left(_{k}^{n}\right) 2^k > \left(_{k + 1}^{n}\right) 2^{k + 1}$.\newline\newline

$\frac{\left(_{k + 1}^{n}\right) 2^{k + 1}}{\left(_{k}^{n}\right) 2^k} = 2\frac{\frac{n!}{(k + 1)!(n - k - 1)!}}{\frac{n!}{k!(n - k)!}} = 2\frac{n - k}{(k + 1)} = \frac{2n - 2k}{k + 1} < 1\Leftrightarrow 2n - 2k < k + 1 \Leftrightarrow 3k > 2n - 1 \Leftrightarrow k > \frac{2n - 1}{3}$.  Поэтому ответ будет при $k = \lceil\frac{2n - 1}{3}\rceil$. В итоге наше слагаемое будет $\binom{n}{\lceil\frac{2n - 1}{3}\rceil}2^{\lceil\frac{2n - 1}{3}\rceil}$

\bigskip\bigskip
\part*{Задача 3}

\begin{center}
    Найдите число слов длины n над алфавитом $\{0, 1\}$, в которых нет двух единиц подряд.
\end{center}
\subsection*{Решение:}
Пусть $D(k, 0), D(k, 1)$ - это количество последовательностей длины $k$, заканчивающихся на 0 или 1 соответственно. То есть, другими словами, можно разбить на два случая: на конце 0 или 1. В первом случае, мы можем взять прибавить любую цифру в конец, $D(n, 0) = D(n - 1, 0) + D(n - 1, 1), D(n, 01) = D(n - 2, 0) + D(n - 2, 1)$. Тогда достаточно очевидно, что если принять за $ans_n$ количество чисел, удовлетворяющих данному условию, то $ans_n = ans_{n - 1} + ans_{n - 2}$, то есть это какое-то число Фибоначчи $F_p$. Осталось заметить, что $ans_n = F_{n + 2}$, так как $ans_1 = 2 = F_3$ (третье число Фибоначчи), $ans_2 = 3 = F_4$ (четвертое число Фибоначчи), откуда это и видно.

\part*{Задача 4}

\begin{center}
   Дать комбинаторное доказательство тождества $\left(_{m}^{n}\right)\left(_{k}^{m}\right) = \left(_{ k}^{n}\right)\left(_{m - k}^{n - k}\right)$
\end{center}
\subsection*{Решение:}
Объяснение достаточно простое: слева сначала выбираются $m$ элементов из $n$ вообще возможных, а затем из этих $m$ выбираются еще $k$, из возможных $m$ останется $m - k$ элементов. Справа же сначала выбираются же сначала $k$ элементов. Пусть они входили в некоторое $m$-элементное подмножетсво. Тогда второй множитель - это количество способов выбрать данное $(m - k)$-элементное подмножетсво из оставшихся $n - k$ элементов всего, так как $k$ из этих $m$ мы уже выбрали. Понятно, что обе части равенства по смыслу эквивалентны.

\part*{Задача 5}

\begin{center}
   Какое из чисел больше $\left(_{F_{998} + 1}^{F_{1000}}\right)$ или $\left(_{F_{999} + 1}^{F_{1000}}\right)$?
\end{center}
\subsection*{Решение:}
$\frac{\left(_{F_{998} + 1}^{F_{1000}}\right)}{\left(_{F_{999} + 1}^{F_{1000}}\right)} = \frac{(F_{999} + 1)!(F_{998} - 1)!}{(F_{998} + 1)!(F_{999} - 1)!} = \frac{F_{999}\cdot (F_{999} + 1)}{F_{998}\cdot (F_{998} + 1)} = \frac{F_{999}}{F_{998}}\cdot\frac{F_{999 + 1}}{F_{998 + 1}} > 1$, так как $F_n > F_{n - 1}$. Значит, $\left(_{F_{998} + 1}^{F_{1000}}\right)$ больше.

\part*{Задача 6}

\begin{center}
   Приведите комбинаторное доказательство равенства $\sum\limits_{k=0}^{(n+1)/2} \binom{n - k + 1}{k} = F_{n + 2}$
\end{center}
\subsection*{Решение:}
Предположим, нам надо снова найти количество последовательностей длины $n$ без двух единиц подряд. Из задачи 3 видим, что это число равно $F_{n + 2}$. Рассмотрим количество единиц в данной последовательности, их не более $\frac{n + 1}{2}$, что соответствует случаю, когда единица стоит первой, а затем чередуется с нулем. Очевидно, что большее количество единиц влечет, что какие-то из них будут стоять рядом, так как при $\frac{n + 1}{2}$ единице у нас они чередовались с нулями, значит, какой-то из них придется банально заменить. У нас есть $n - k$ нулей, а позиций, куда можно поставить $k$ единиц (между нулями, очевидно, иначе будут две единицы подряд) будет $n - k + 1$, причем единиц может быть в числе от 0 до $\frac{n + 1}{2}$. Поэтому формула $\sum\limits_{k=0}^{(n+1)/2} \binom{n - k + 1}{k}$ отражает количество последовательностей без двух единиц подряд длины $n$.
\end{document}