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