1 files changed, 80 insertions, 0 deletions
diff --git a/dm/dm-18.tex b/dm/dm-18.tex
new file mode 100644
index 0000000..e764814
--- /dev/null
+++ b/dm/dm-18.tex
@@ -0,0 +1,80 @@
+\documentclass[11pt]{article}
+\usepackage[x11names, svgnames, rgb]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,shapes}
+
+\usepackage{scrextend}
+
+\input{intro}
+
+\lhead{\color{gray} Шарафатдинов Камиль 192}
+\rhead{\color{gray} дм-17 (\texttt{cw18\_plus})}
+\title{Дискретная математика 18}
+\author{Шарафатдинов Камиль БПМИ192}
+\date{билд: \today}
+
+% -- Here bet  dragons --
+\begin{document}
+
+\maketitle
+
+\setlength{\columnsep}{1cm}
+\twocolumn
+\dmquestion{1}
+
+    Первый может на первом ходу взять четыре спички, а дальше играть по следующей стратегии:
+    если второй берет $k$ спичек, то первый следующим ходом должен будет взять $6 - k$ спичек. Он, очевидно, может так делать в любой момент, а так же после каждого хода первого количество спичек уменьшается на $6$. Значит, первый заберет последнюю спичку, а значит, второму спичек не останется и он проиграет.
+
+    Ответ: у первого.
+\dmquestion{2}
+
+    Пусть второй сделает четыре хода как-нибудь.
+
+    Пусть, для определенности, он всегда пишет $1$.
+    Тогда после пятого хода первого игрока на доске будет написано число $n$.
+    Одно из чисел $10n + 0, 10n + 1, 10n + 2, 10n + 3, 10n + 4, 10n + 5, 10n + 6$ обязательно делится на $7$, а значит, второй может написать соответствующую цифру и сделать число делящимся на $7$.
+
+    Ответ: у второго.
+\dmquestion{3}
+
+    Заметим, что если число на доске - нечетное, то у него есть только нечетные делители. Поэтому за один ход его можно сделать только четным. А если на доске написано четное число, то его всегда можно уменьшить на единичку, то есть, сделать нечетным.
+
+    Тогда первый может всегда делать число нечетным, а второй всегда будет вынужден делать его четным (после хода второго число на доске обязательно четное, поэтому первый может продолжать играть по этой стратигии). С каждым ходом число на доске уменьшается, поэтому когда-нибудь оно станет нулем и игра закончится. Так как четные числа появляются только после ходов второго игрока, то он и проиграет.
+
+    Ответ: у первого.
+\dmquestion{4}
+
+    Рассмотрим немножко другую игру (3 с семинара).
+    У первого всегда есть выигрышная стратегия:
+
+    Если количество минусов нечетно, то первым ходом он переправит минус посередине, а если четно, то два минуса посередине. Дальше он может действовать симметрично второму относительно центра (потому что первый не может ходить одновременно по обе стороны от середины). Значит, он всегда может сделать ход после второго, а значит он выиграет.
+
+    Теперь, рассмотрим нашу задачу. При $n = 1, 2$ у первого есть выигрышная стратегия - переправить все минусы. При $n > 2$ после любого хода первого второй может действовать как если бы они играли в рассмотренную выше игру (с последовательно выписанными оставшимися минусами) и выиграть. То есть при $n > 2$ у второго есть выигрышная стратегия.
+
+    Ответ: 1, 2.
+\dmquestion{5}
+
+    Докажем, что разбить выпуклый $n$-угольник можно только на $n - 2$ треугольника.
+
+    Для $n = 3$: треугольник уже разбит на один треугольник.
+
+    Пусть для $n - 1$ верно. Возьмем $n$-угольник и любое ребро из его разбиения на треугольники. Такое ребро делит его на два выпуклых многоугольника с количеством углов $k$ и $n - k + 2$. Тогда первый можно разбить только на $k - 2$ треугольников, а второй только на $n - k$ треугольников. Значит, разбить $n$-угольник можно только на $n - 2$ треугольника.
+
+    Значит, вне зависимости от ходов, при четных $n$ выигрывает первый, а при нечетных - второй.
+\dmquestion{6}
+
+    Пронумеруем вершины $v_1, \ldots, v_n$. Пусть у первого игрока уже есть связный (связанный ребрами красного цвета) граф на первых $k$ вершинах (назовем его $G_k$) и каждый игрок сделал $k - 1$ ход.
+
+    Так как граф полный, то $v_{k + 1}$ соединена с каждой из вершин в $G_k$.
+    
+    Так как второй игрок сделал $k - 1$ ходов, то есть ребро из $v_{k + 1}$ в $G_k$, которое не покрашено в синий цвет.
+    
+    А так как у первого игрока есть граф на $k$ вершинах, то в нем есть хотя бы $k - 1$ ребер. Значит, первый не красил ребра вне $G_k$, значит, есть ребро из $v_{k + 1}$ в $G_k$, которое еще никем не покрашено.
+
+    Значит, первый может покрасить это ребро в красный цвет и у него будет связный граф на первых $k + 1$ вершинах.
+
+    Так как в самом начале у первого есть связный граф из одной вершины, то он может продолжать действовать так, чтобы перед каждым его ходом у него был связный граф на первых вершинах. Значит, после $n - 1$ хода у него будет связный граф на $n$ вершинах, а второй к этому моменту сделает только $n - 2$ хода, поэтому у него точно не будет связного графа на $n$ вершинах.
+
+    Ответ: при любых $n \geq 2$.
+
+\end{document}