\documentclass[12pt,a4paper]{article}
\usepackage{amsthm}
\newtheorem{lemma}{Lemma}
\begin{document}

% Beweis von adversary strategy.
% version gridserach21 gegenüber 22.

% >

% about "putting things in the correct order".

% =====================
% \begin{lemma}
%   Let $1\le i\le l$, $m_i\ge 2$ and $x_{i,1}\le x_{i,2}\le \ldots \le
%   x_{i,m_i}$ positive integers.  Let us denote $y_i=x_{i,1}+x_{i,2}+
%   \dots +x_{i, m_i-1}$ and $y_{l+1}=x_{l,m_l}=1$.  If for every $i$,
%   $x_{i,j}\le y_{i+1}+\dots +y_l+y_{l+1}$, $y_{l+1}=1$ and $z$ is a
%   nonnegative integer with $z\le N=y_1+\dots+y_l+y_{l+1}$, then there
%   is a subset $Z$ of the series of the $x_{i,j}$'s which sums up to
%   $z$.
% \end{lemma}

MATHEMATICAL WRITING, G\"unter Rote, WS 2014/15.

Exercise 1; Oct 23, 2014.

\begin{lemma}
  Let $1\le i\le l$, $m_i\ge 2$ and $x_{i,1}\le x_{i,2}\le \ldots \le
  x_{i,m_{i}-1}$ and $x_{l+1,1}$ positive integers.  For $1\le i\le l$
  we denote $y_i=\sum\nolimits_{j=1}^{m_{i-1}}x_{i,j}$ and
  $y_{l+1}=x_{l+1,1}$.  If for every $1\le i\le l$ and every $1\le
  j\le m_{i-1}$, $x_{i,j}\le \sum\nolimits_{k=i+1}^{l+1}y_k$ and
  $y_{l+1}=1$ and $z$ is a nonnegative integer with $z\le N=\sum
  x_{i,j}=\sum\nolimits_{k=1}^{l+1}y_k$, then there is a subset $Z$ of
  the $x_{i,j}$'s which sums to $z$.
\end{lemma}
\begin{proof}

  Let us consider the following greedy algorithm. We process the
  series in the order $x_{1,1}, x_{1,2},\dots, x_{1,m_1-1},x_{2,1},
  x_{2,2},\dots, x_{2,m_2-1},\dots,x_{l,1}, x_{l,2},\dots,
  x_{l,m_i-1}$, and we add an element $x_{i,j}$ to $Z$ if and only if
  the sum together with it is at most $z$. We show that this algorithm
  gives the desired subset at the end.

  For that we show that after processing $x_{1,1}, x_{1,2},$ $\dots,
  x_{1,m_1-1},x_{2,1}, x_{2,2},$ $\dots, x_{2,m_2-1},\dots$ $,x_{i,1},
  x_{i,2},\dots, x_{i,m_i-1}$ the sum is in the interval
  $[z-(y_{i+1}+\dots+y_{l+1}),z]$ (this is enough, as at the end
  $i=l+1$ and this interval has length 0).

  During the process the sum is always at most $z$ by definition of
  the process, thus we only need to prove that the sum is at least
  $z-(y_{i+1}+\dots+y_{l+1}$ at the above given time. Note that during
  the process the sum is monotonely increasing as we only add
  $x_{i,j}$'s to the sum.

  We use induction on $i$. In case $i=1$, either we can add every
  $x_{1,j}$ to $Z$, or not. If we can, the sum is
  $y_1=N-(y_{2}+\dots+y_{l+1})\ge z- (y_{2}+\dots+y_{l+1})$. If we
  cannot, it means that a certain $x_{1,j}$ would push the sum over
  $z$. But then without that $x_{1,j}$ the sum when processing
  $x_{1,j}$ was already greater than $z-x_{1,j}\ge
  z-(y_{2}+\dots+y_{l+1})$.

  The induction step goes similarly. Suppose that the sum after
  $x_{1,1}, x_{1,2},\dots,$ $ x_{1,m_1-1},$ $x_{2,1}, x_{2,2},$ $
  \dots, x_{2,m_2-1},\dots,$ $x_{i-1,1}, x_{i-1,2},\dots,
  x_{i-1,m_{i-1}-1}$ is in the interval $[z-(y_{i}+\dots+y_{l+1}),z]$,
  and consider $x_{i,1}, x_{i,2},\dots, x_{i,m_i-1}$. If we can add
  all of them to $Z$, then the sum increases by $y_{i}$, hence it is
  at least $z-(y_{i}+\dots+y_{l+1})+y_i=z-(y_{i+1}+\dots+y_{l+1})$. If
  not, then again a certain $x_{i,j}$ would push it over $z$, which
  means the sum was already greater than $z-x_{i,j}\ge
  z-(y_{i+1}+\dots+y_{l+1})$.

  Thus by induction before processing $x_{l+1,1}=1$ we have a sum in
  the range $[z-y_{l+1},z]=[z-1,z]$. If the sum is $z$ then we are
  done, otherwise it is $z-1$, and we add $x_{l+1,1}=1$ to the sum to
  make it $z$.
\end{proof}
\end{document}
