\documentclass[12pt]{article}

% Автор: Сергей Копелиович

\usepackage{polyglossia}

%\usepackage{amsthm, amsmath, amssymb}
\usepackage{amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{enumerate}
\usepackage{hologo}
\usepackage{minted}
\usepackage{unicode-math}

\defaultfontfeatures{Ligatures=TeX}
\setmainfont{CMU Serif}  
\setmonofont{CMU Typewriter Text}  
\setsansfont[Mapping=tex-text]{CMU Sans Serif}
\setmathfont{Latin Modern Math}
\setdefaultlanguage[spelling=modern]{russian}
\setotherlanguage{english}

\sloppy

\voffset=-22mm
\textheight=225mm
\hoffset=-25mm
\textwidth=180mm

\newenvironment{MyList}{
  \begin{enumerate}[1.]
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{5pt}
}{
  \end{enumerate}
}

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}
\newcommand{\q}[1]{\langle #1 \rangle} % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}
\def\myindent{\hspace*{\parindent}}
\def\up{\vspace*{-\baselineskip}}
\def\NO{\t{\#}}
\newcommand{\ITEM}[1]{{\bf \underline{#1}}\hspace{0.5em}}
\newcommand{\Section}[1]{\section{#1}\vspace{-1.5em}\myindent\unskip}
\def\LINE{\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}}

\begin{document}

\Section{Два указателя}

$x_n, w_n$ -- координата и вес $n$-й точки ($x_i \le x_{i+1}, w_i \ge 0$)

$[n,k]$ -- состояние динамики, первые $n$ точек разбили на $k$ отрезков
 
$p_{n,k}$ -- граница последнего отрезка

$q_{n,k}$ -- центр последнего отрезка

$o_{l,r}$ -- оптимальный центр отрезке $[l,r]$

Алгоритм выбора $o_{l,r}$ -- самая левая точка, что $\sum[l,o_{l,r}] \ge \sum(o_{l,r},r]$.

\ITEM{Цель рассуждения} доказать, что $p_{n,k-1} \le p_{n,k} \le p_{n+1,k}$ 

Последовательность утверждений:

\ITEM{Lm \NO{1}} $o_{l,r-1} \le o_{l, r} \le o_{l+1,r}$

\ITEM{Lm \NO{2}} $q_{n+1,k} \ge q_{n, k}$.
Доказательство: перейдем от оптимального $(n,k)$ разбиения к $(n+1,k)$ разбиению, не поменяв положение центра последнего отрезка $q_{n,k}$, 
функция увеличилась на $\mathbb{X} = w_n(x_n - x_{q_{n,k}})$. Теперь перейдем к оптимальному $(n+1,k)$ разбиению, функция уменьшилась.
Теперь перейдем к $(n,k)$ разбиению, функция уменьшилась на $\mathbb{Y} = w_n(x_n - x_{q_{n+1,k}})$. Если $q_{n+1,k} < q_{n,k}$, то $\mathbb{Y} > \mathbb{X}$,
и, мы получаем противоречие с предположением, что исходное разбиение $(n,k)$ было оптимальным.

\ITEM{Lm \NO{3}} $p_{n+1,k} \ge p_{n, k}$

Следует из \t{Lm \NO{2}} и \t{Lm \NO{1}}.

\ITEM{Lm \NO{4}} $p_{n,k} \ge p_{n,k-1}$

Пусть $k=3$ и $p_{n,k} < p_{n,k-1}$. Смотрим на правые два отрезка в обоих разбиениях, видим противоречие с \t{Lm \NO{3}}.
Теперь пусть $k$ -- произвольное и $p_{n,k} < p_{n,k-1}$. Смотрим на правые два отрезка в обоих разбиениях, или видим противоречие с \t{Lm \NO{3}},
или смотрим на правые три отрезка, для которых также, или противоречие, или нужно взять +1 отрезок.

\end{document}
