\documentclass
[numbers=enddot,12pt,final,onecolumn,notitlepage,german]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[ngerman]{babel}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=True]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Saturday, February 06, 2021 20:44:27}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Satz}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Bemerkung}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Folgerung}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Konvention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Frage}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warnung}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Vermutung}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Beispiel}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Aufgabe}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newtheorem{aufg}[exer]{Aufgabe}
\newenvironment{aufgabe}[1][]
{\begin{aufg}[#1]\begin{leftbar}}
{\end{leftbar}\end{aufg}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{aufgabe}[1][Aufgabe]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{22.5cm}
\setlength\textwidth{14.8cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\ihead{Aufgabenblatt Ungleichungen}
\ohead{Seite \thepage}
\cfoot{}
\begin{document}

\title{Einf\"{u}hrung in algebraische Ungleichungen I}
\author{Darij Grinberg}
\date{\today\\
unfertige Version!\footnote{Eine aktuelle Version dieses Aufgabenblattes kann
auf \url{http://www.cip.ifi.lmu.de/~grinberg/algebra/aimo2021-ineqs.pdf}
gefunden werden.}}
\maketitle

\begin{abstract}
(Aufgabenblatt f\"{u}r IMO-Training 2021 Deutschland)

\end{abstract}
\tableofcontents

\section*{***}

Algebraische Ungleichungen sind eines der klassischen Topoi von
Mathematikwettbewerben, und haben auch f\"{u}r andere Gebiete Relevanz. Zu
meiner IMO-Zeit (2004--2006) hatten sie besonders im Internet eine enorme
Popularit\"{a}t (das AoPS-Forum war voll von Drei-Variablen-Ungleichungen mit
immer technischeren Beweisen); diese ist seitdem etwas abgeflaut (wohl nicht
zuletzt wegen der zunehmenden Theoretisierung, die zu starke Vorteile f\"{u}r
B\"{u}cher- und Forenleser hervorgebracht hat), aber nach wie vor hat jede
IMO-Shortlist mindestens zwei Ungleichung.

Diese kleine Einf\"{u}hrung ersetzt keinen Expertenkurs, aber sollte einige
Methoden und Ideen vermitteln. Mehr (oftmals viel mehr) ist in Quellen wie
\cite{Steele04}, \cite{Mildor06}, \cite{Lee07}, \cite{Cirtoa06},
\cite{Hung07}, \cite{infinity} und \cite[OTIS Excerpts]{ChenEvan} zu finden.

\subsection{Notationen}

Im Folgenden bedeute $\mathbb{N}$ die Menge $\left\{  0,1,2,\ldots\right\}  $.

\section{\label{chp.AM-GM}AM-GM}

\subsection{Die Ur-Ungleichung und AM-GM f\"{u}r zwei Zahlen}

Die \textquotedblleft Mutter aller Ungleichungen\textquotedblright\ ist
folgender Satz:

\begin{theorem}
[Die Ur-Ungleichung]\label{thm.xsquare}F\"{u}r jede reelle Zahl $x$ ist
$x^{2}\geq0$.
\end{theorem}

\begin{proof}
[Hinweise zum Beweis von Satz \ref{thm.xsquare}.]Wer es wirklich nicht glaubt:
erst auf den Fall $x\in\mathbb{Q}$ reduzieren (durch Grenzwertbildung); dann
auf den Fall $x\in\mathbb{Z}$ reduzieren (denn jedes $x\in\mathbb{Q}$ ist
darstellbar als $x=u/v$ f\"{u}r gewisse $u,v\in\mathbb{Z}$); dann auf den Fall
$x\in\mathbb{N}$ reduzieren (weil $\left(  -x\right)  ^{2}=x^{2}$); dort ist
es aber klar. Die Details finden sich in jedem guten Analysisbuch.
\end{proof}

Die meisten Ungleichungen, die wir im folgenden beweisen, sind Folgerungen
(oder Folgerungen von Folgerungen, oder Folgerungen von Folgerungen von
Folgerungen...) von Satz \ref{thm.xsquare}. Hier ist die erste Generation:

\begin{theorem}
[AM-GM-Ungleichung f\"{u}r zwei Zahlen]\label{thm.2ab}Seien $a$ und $b$ zwei
reelle Zahlen.

\textbf{(a)} Es gilt $a^{2}+b^{2}\geq2ab$.

\textbf{(b)} Es gilt $\left(  a+b\right)  ^{2}\geq4ab$.

\textbf{(c)} Sind $a$ und $b$ nichtnegativ, dann ist $a+b\geq2\sqrt{ab}$.

\textbf{(d)} Sind $a$ und $b$ positiv, dann ist $\dfrac{a}{b}+\dfrac{b}{a}%
\geq2$.
\end{theorem}

\begin{proof}
[Beweis von Satz \ref{thm.2ab}.]\textbf{(a)} Wir haben%
\[
a^{2}+b^{2}-2ab=\left(  a-b\right)  ^{2}\geq0
\]
(nach Satz \ref{thm.xsquare}, angewandt auf $x=a-b$). Also ist $a^{2}%
+b^{2}\geq2ab$. Hieraus folgt Satz \ref{thm.2ab} \textbf{(a)}.

\textbf{(b)} Wir haben $\left(  a+b\right)  ^{2}=\underbrace{a^{2}+b^{2}%
}_{\substack{\geq2ab\\\text{(laut Satz \ref{thm.2ab} \textbf{(a)})}}%
}+2ab\geq2ab+2ab=4ab$. Damit ist Satz \ref{thm.2ab} \textbf{(b)} bewiesen.

\textbf{(c)} Seien $a$ und $b$ nichtnegativ. Satz \ref{thm.2ab} \textbf{(b)}
ergibt $\left(  a+b\right)  ^{2}\geq4ab=\left(  2\sqrt{ab}\right)  ^{2}$. Wir
k\"{o}nnen die Quadrate auf beiden Seiten dieser Ungleichung loswerden, indem
wir Quadratwurzeln ziehen (denn $a+b$ und $2\sqrt{ab}$ sind nichtnegativ);
somit erhalten wir $a+b\geq2\sqrt{ab}$. Satz \ref{thm.2ab} \textbf{(c)} ist
somit bewiesen.

\textbf{(d)} Seien $a$ und $b$ positiv. Satz \ref{thm.2ab} \textbf{(a)} ergibt
$a^{2}+b^{2}\geq2ab$. Wir k\"{o}nnen diese Ungleichung durch $ab$ dividieren
(denn $ab$ ist positiv); somit erhalten wir $\dfrac{a^{2}+b^{2}}{ab}\geq2$.
Das hei\ss t, $\dfrac{a}{b}+\dfrac{b}{a}\geq2$ (denn $\dfrac{a^{2}+b^{2}}%
{ab}=\dfrac{a}{b}+\dfrac{b}{a}$). Satz \ref{thm.2ab} \textbf{(d)} ist somit bewiesen.
\end{proof}

Satz \ref{thm.2ab} wird oft die \textit{AM-GM-Ungleichung f\"{u}r zwei Zahlen}
genannt. Er mag unschuldig klingen, reicht aber f\"{u}r viele Anwendungen
vollkommen aus. Hier sind einige der einfachsten Beispiele.

\begin{example}
\label{exa.aa+bb+cc}Seien $a,b,c$ drei reelle Zahlen. Man beweise:%
\begin{equation}
a^{2}+b^{2}+c^{2}\geq bc+ca+ab. \label{eq.exa.aa+bb+cc.eq}%
\end{equation}

\end{example}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.aa+bb+cc}.]Aus Satz \ref{thm.2ab}
\textbf{(a)} folgen die drei Ungleichungen%
\begin{align*}
b^{2}+c^{2}  &  \geq2bc;\\
c^{2}+a^{2}  &  \geq2ca;\\
a^{2}+b^{2}  &  \geq2ab.
\end{align*}
Addieren wir diese drei Ungleichungen auf, so erhalten wir%
\[
\left(  b^{2}+c^{2}\right)  +\left(  c^{2}+a^{2}\right)  +\left(  a^{2}%
+b^{2}\right)  \geq2bc+2ca+2ab.
\]
Dies vereinfacht sich zu%
\[
2\left(  a^{2}+b^{2}+c^{2}\right)  \geq2\left(  bc+ca+ab\right)  .
\]
Division durch $2$ ergibt nun (\ref{eq.exa.aa+bb+cc.eq}). Damit ist Beispiel
\ref{exa.aa+bb+cc} gel\"{o}st.
\end{proof}

\begin{example}
\label{exa.(y+z)(z+x)(x+y)}Seien $x,y,z$ drei nichtnegative reelle Zahlen. Man
beweise:%
\begin{equation}
\left(  y+z\right)  \left(  z+x\right)  \left(  x+y\right)  \geq8xyz.
\label{eq.exa.(y+z)(z+x)(x+y).eq}%
\end{equation}

\end{example}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.(y+z)(z+x)(x+y)}.]Aus Satz \ref{thm.2ab}
\textbf{(c)} folgen die drei Ungleichungen%
\begin{align*}
y+z  &  \geq2\sqrt{yz};\\
z+x  &  \geq2\sqrt{zx};\\
x+y  &  \geq2\sqrt{xy}.
\end{align*}
Multiplizieren wir diese drei Ungleichungen\footnote{Dies d\"{u}rfen wir tun,
denn alle Seiten dieser drei Ungleichungen sind nichtnegativ.}, so erhalten
wir%
\[
\left(  y+z\right)  \left(  z+x\right)  \left(  x+y\right)  \geq2\sqrt
{yz}\cdot2\sqrt{zx}\cdot2\sqrt{xy}=8xyz.
\]
Damit ist Beispiel \ref{exa.(y+z)(z+x)(x+y)} gel\"{o}st.
\end{proof}

\begin{example}
\label{exa.sqrt(a+c)(b+d)}Seien $a,b,c,d$ vier nichtnegative reelle Zahlen.
Man beweise:%
\begin{equation}
\sqrt{\left(  a+c\right)  \left(  b+d\right)  }\geq\sqrt{ab}+\sqrt{cd}.
\label{eq.exa.sqrt(a+c)(b+d).eq}%
\end{equation}

\end{example}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.sqrt(a+c)(b+d)}.]Da alle in
(\ref{eq.exa.sqrt(a+c)(b+d).eq}) vorkommenden Zahlen nichtnegativ sind,
k\"{o}nnen wir die zu beweisende Ungleichung (\ref{eq.exa.sqrt(a+c)(b+d).eq})
quadrieren (ohne dass sich dabei ihr Wahrheitsgehalt \"{a}ndert). Das
hei\ss t, es reicht aus, dass wir die Ungleichung%
\[
\left(  \sqrt{\left(  a+c\right)  \left(  b+d\right)  }\right)  ^{2}%
\geq\left(  \sqrt{ab}+\sqrt{cd}\right)  ^{2}%
\]
beweisen. Doch letztere Ungleichung k\"{o}nnen wir ziemlich einfach zeigen:
Wir haben%
\[
\left(  \sqrt{\left(  a+c\right)  \left(  b+d\right)  }\right)  ^{2}=\left(
a+c\right)  \left(  b+d\right)  =ab+ad+bc+cd.
\]
Wegen%
\begin{align*}
ad+bc  &  \geq2\sqrt{ad\cdot bc}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{nach Satz \ref{thm.2ab} \textbf{(c)},
angewendet auf }ad\text{ und }bc\text{ statt }a\text{ und }b\right) \\
&  =2\sqrt{ab\cdot cd}\ \ \ \ \ \ \ \ \ \ \left(  \text{denn }ad\cdot
bc=ab\cdot cd\right) \\
&  =2\sqrt{ab}\cdot\sqrt{cd}%
\end{align*}
ist also%
\begin{align*}
\left(  \sqrt{\left(  a+c\right)  \left(  b+d\right)  }\right)  ^{2}  &
=\underbrace{ab}_{=\left(  \sqrt{ab}\right)  ^{2}}+\underbrace{ad+bc}%
_{\geq2\sqrt{ab}\cdot\sqrt{cd}}+\underbrace{cd}_{=\left(  \sqrt{cd}\right)
^{2}}\\
&  \geq\left(  \sqrt{ab}\right)  ^{2}+2\sqrt{ab}\cdot\sqrt{cd}+\left(
\sqrt{cd}\right)  ^{2}=\left(  \sqrt{ab}+\sqrt{cd}\right)  ^{2}.
\end{align*}
Wie gesagt, ist dies ausreichend, um Beispiel \ref{exa.sqrt(a+c)(b+d)} zu l\"{o}sen.
\end{proof}

\begin{example}
\label{exa.bc/a+ca/ab+ab/c}Seien $a,b,c$ drei positive reelle Zahlen. Man
beweise:%
\[
\dfrac{bc}{a}+\dfrac{ca}{b}+\dfrac{ab}{c}\geq a+b+c.
\]

\end{example}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.bc/a+ca/ab+ab/c}.]Dies ist ein Paradebeispiel
f\"{u}r \textit{Substitution}. Und zwar definieren wir drei positive reelle
Zahlen $x,y,z$ durch $x=\sqrt{\dfrac{bc}{a}}$, $y=\sqrt{\dfrac{ca}{b}}$ und
$z=\sqrt{\dfrac{ab}{c}}$. (Dies ist erlaubt, denn unter den Quadratwurzeln
stehen nur positive reelle Zahlen.) Nun wenden wir Beispiel \ref{exa.aa+bb+cc}
auf $x,y,z$ statt $a,b,c$ an. Hierdurch erhalten wir%
\[
\left(  \sqrt{\dfrac{bc}{a}}\right)  ^{2}+\left(  \sqrt{\dfrac{ca}{b}}\right)
^{2}+\left(  \sqrt{\dfrac{ab}{c}}\right)  ^{2}\geq\sqrt{\dfrac{ca}{b}}%
\cdot\sqrt{\dfrac{ab}{c}}+\sqrt{\dfrac{ab}{c}}\cdot\sqrt{\dfrac{bc}{a}}%
+\sqrt{\dfrac{bc}{a}}\cdot\sqrt{\dfrac{ca}{b}}.
\]
Dies vereinfacht sich zu%
\[
\dfrac{bc}{a}+\dfrac{ca}{b}+\dfrac{ab}{c}\geq a+b+c
\]
(denn $\sqrt{\dfrac{ca}{b}}\cdot\sqrt{\dfrac{ab}{c}}=a$ und $\sqrt{\dfrac
{ab}{c}}\cdot\sqrt{\dfrac{bc}{a}}=b$ und $\sqrt{\dfrac{bc}{a}}\cdot
\sqrt{\dfrac{ca}{b}}=c$). Beispiel \ref{exa.bc/a+ca/ab+ab/c} ist damit gel\"{o}st.
\end{proof}

\begin{example}
[Nesbitt-Ungleichung]\label{exa.nesbitt-3}Seien $a,b,c$ drei positive reelle
Zahlen. Man beweise:%
\[
\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b}\geq\dfrac{3}{2}.
\]

\end{example}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.nesbitt-3}.]Wir setzen $x=b+c$, $y=c+a$ und
$z=a+b$. Somit sind auch $x,y,z$ drei positive reelle Zahlen. Nun pr\"{u}ft
man leicht nach, dass $x+y+z=2a+2b+2c$ ist. Also ist
\[
2a=x+y+z-\left(  2b+2c\right)  =x+y+z-2\underbrace{\left(  b+c\right)  }%
_{=x}=x+y+z-2x=y+z-x.
\]
Folglich ist%
\begin{align*}
\dfrac{2a}{b+c}  &  =\dfrac{y+z-x}{x}\ \ \ \ \ \ \ \ \ \ \left(  \text{denn
}2a=y+z-x\text{ und }b+c=x\right) \\
&  =\dfrac{y}{x}+\dfrac{z}{x}-1.
\end{align*}
Analog ist%
\[
\dfrac{2b}{c+a}=\dfrac{z}{y}+\dfrac{x}{y}-1\ \ \ \ \ \ \ \ \ \ \text{und}%
\ \ \ \ \ \ \ \ \ \ \dfrac{2c}{a+b}=\dfrac{x}{z}+\dfrac{y}{z}-1.
\]
Addieren wir diese drei Gleichungen auf, so erhalten wir%
\begin{align*}
\dfrac{2a}{b+c}+\dfrac{2b}{c+a}+\dfrac{2c}{a+b}  &  =\left(  \dfrac{y}%
{x}+\dfrac{z}{x}-1\right)  +\left(  \dfrac{z}{y}+\dfrac{x}{y}-1\right)
+\left(  \dfrac{x}{z}+\dfrac{y}{z}-1\right) \\
&  =\underbrace{\left(  \dfrac{y}{z}+\dfrac{z}{y}\right)  }_{\substack{\geq
2\\\text{(nach Satz \ref{thm.2ab} \textbf{(d)})}}}+\underbrace{\left(
\dfrac{z}{x}+\dfrac{x}{z}\right)  }_{\substack{\geq2\\\text{(nach Satz
\ref{thm.2ab} \textbf{(d)})}}}+\underbrace{\left(  \dfrac{x}{y}+\dfrac{y}%
{x}\right)  }_{\substack{\geq2\\\text{(nach Satz \ref{thm.2ab} \textbf{(d)})}%
}}-3\\
&  \geq2+2+2-3=3.
\end{align*}
Dividieren wir nun beide Seiten dieser Ungleichung durch $2$, so erhalten wir%
\[
\dfrac{a}{b+c}+\dfrac{b}{c+a}+\dfrac{c}{a+b}\geq\dfrac{3}{2}.
\]
Damit ist Beispiel \ref{exa.nesbitt-3} bewiesen.
\end{proof}

\begin{example}
\label{exa.ml17086var}Seien $a,b,c$ die Seitenl\"{a}ngen eines Dreiecks. Man
beweise:%
\begin{equation}
abc\geq\left(  2a-b\right)  \left(  2b-c\right)  \left(  2c-a\right)  .
\label{eq.exa.ml17086var.eq}%
\end{equation}

\end{example}

\begin{noncompile}
Source: https://artofproblemsolving.com/community/c6h17086p117756 (weniger allgemein).
\end{noncompile}

Die Bedingung, dass $a,b,c$ die Seitenl\"{a}ngen eines Dreiecks sind, ist hier
wichtig; f\"{u}r $\left(  a,b,c\right)  =\left(  1,4,10\right)  $
beispielsweise ist die Ungleichung falsch.

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.ml17086var}.]Da $a,b,c$ die Seitenl\"{a}ngen
eines Dreiecks ist, gilt nach den Dreiecksungleichungen $b+c>a$ und $c+a>b$
und $a+b>c$. Ferner sind $a,b,c$ positiv.

Somit ist h\"{o}chstens eine der drei Zahlen $2a-b$, $2b-c$ und $2c-a$
negativ. [\textit{Beweis:} Nehmen wir das Gegenteil an. Dann sind also
mindestens zwei von diesen drei Zahlen negativ. O. B. d. A. seien also $2a-b$
und $2b-c$ negativ (denn sonst k\"{o}nnen wir dies durch eine zyklische
Vertauschung von $a,b,c$ erreichen). Dann ist also $2a<b$ und $2b<c$. Da $a$
positiv ist, gilt nun $a<2a<b$ und somit $\underbrace{a}_{<b}+b<b+b=2b<c$.
Dies widerspricht $a+b>c$. Dieser Widerspruch zeigt, dass unsere Annahme
falsch ist. Damit ist gezeigt, dass h\"{o}chstens eine der drei Zahlen $2a-b$,
$2b-c$ und $2c-a$ negativ ist.]

Wir m\"{u}ssen die Ungleichung (\ref{eq.exa.ml17086var.eq}) beweisen. Wenn
genau eine der drei Zahlen $2a-b$, $2b-c$ und $2c-a$ negativ ist, dann ist
diese Ungleichung trivial (denn in diesem Fall ist die rechte Seite dieser
Ungleichung $\leq0$, w\"{a}hrend die linke Seite offensichtlich $\geq0$ ist).
Somit d\"{u}rfen wir o. B. d. A. annehmen, dass \textbf{nicht} genau eine der
drei Zahlen $2a-b$, $2b-c$ und $2c-a$ negativ ist. Nehmen wir dies an.
Folglich ist \textbf{keine} der drei Zahlen $2a-b$, $2b-c$ und $2c-a$ negativ
(denn wir wissen bereits, dass h\"{o}chstens eine der drei Zahlen $2a-b$,
$2b-c$ und $2c-a$ negativ ist). Das hei\ss t, die drei Zahlen $2a-b$, $2b-c$
und $2c-a$ sind nichtnegativ.

Nun ist $\left(  \left(  2a-b\right)  +b\right)  ^{2}\geq4\left(  2a-b\right)
b$ (laut Satz \ref{thm.2ab} \textbf{(b)}, angewandt auf $2a-b$ statt $a$).
Wegen $\left(  2a-b\right)  +b=2a$ vereinfacht sich dies zu $\left(
2a\right)  ^{2}\geq4\left(  2a-b\right)  b$. Dividieren wir diese Ungleichung
durch $4$, so erhalten wir%
\[
a^{2}\geq\left(  2a-b\right)  b.
\]
\footnote{Alternativ k\"{o}nnen wir diese Ungleichung auch einsehen, indem wir
die rechte Seite von der linken subtrahieren: N\"{a}mlich ist $a^{2}-\left(
2a-b\right)  b=\left(  a-b\right)  ^{2}\geq0$.} Analog gilt%
\begin{align*}
b^{2}  &  \geq\left(  2b-c\right)  c\ \ \ \ \ \ \ \ \ \ \text{und}\\
c^{2}  &  \geq\left(  2c-a\right)  a.
\end{align*}
Wir k\"{o}nnen diese drei Ungleichungen miteinander multiplizieren (denn wir
wissen, dass die drei Zahlen $2a-b$, $2b-c$ und $2c-a$ nichtnegativ sind;
somit sind alle Seiten dieser drei Ungleichungen nichtnegativ); somit erhalten
wir%
\[
a^{2}b^{2}c^{2}\geq\left(  2a-b\right)  b\cdot\left(  2b-c\right)
c\cdot\left(  2c-a\right)  a.
\]
Diese Ungleichung k\"{o}nnen wir durch $abc$ dividieren (denn $a,b,c$ sind
positiv), und erhalten somit%
\[
abc\geq\left(  2a-b\right)  \left(  2b-c\right)  \left(  2c-a\right)  .
\]
Damit ist (\ref{eq.exa.ml17086var.eq}) bewiesen. Beispiel \ref{exa.ml17086var}
ist also gel\"{o}st.
\end{proof}

\begin{remark}
\label{rmk.eqcases.1}Wir werden uns zwar nicht oft mit Gleichheitsf\"{a}llen
befassen, doch ein paar Anmerkungen zu ihnen sind wohl nicht fehl am Platz, da
sie Anwendungen haben (die Faustregel ist: \"{u}berall dort, wo eine
Ungleichung gebraucht wird, wird fr\"{u}her oder sp\"{a}ter auch eine Analyse
ihrer Gleichheitsf\"{a}lle n\"{u}tzlich). Wir gehen also kurz die oben
bewiesenen Ungleichungen durch und analysieren, wann sie zu Gleichheiten werden:

\begin{itemize}
\item Die Ungleichung $x^{2}\geq0$ in Satz \ref{thm.xsquare} wird genau dann
zur Gleichheit, wenn $x=0$ ist. F\"{u}r alle $x\in\mathbb{R}\setminus\left\{
0\right\}  $ gilt $x^{2}>0$. (Um dies zu zeigen, ben\"{o}tigt man die
Tatsache, dass es f\"{u}r jede positive reelle Zahl $\varepsilon$ eine
positive ganze Zahl $n$ mit $\varepsilon>1/n$ gibt.)

\item Die Ungleichung $a^{2}+b^{2}\geq2ab$ in Satz \ref{thm.2ab} \textbf{(a)}
wird genau dann zur Gleichheit, wenn $a=b$ ist. (Denn wenn $a\neq b$ ist, dann
ist $a-b\neq0$ und somit $\left(  a-b\right)  ^{2}>0$; somit k\"{o}nnen die
\textquotedblleft$\geq$\textquotedblright-Zeichen im Beweis von Satz
\ref{thm.2ab} \textbf{(a)} in diesem Fall durch \textquotedblleft%
$>$\textquotedblright-Zeichen ersetzt werden.)

\item Die Ungleichung $\left(  a+b\right)  ^{2}\geq4ab$ in Satz \ref{thm.2ab}
\textbf{(b)} wird genau dann zur Gleichheit, wenn $a=b$ ist. (Dies folgt aus
dem gleichen Grund wie die analoge Aussage \"{u}ber Satz \ref{thm.2ab}
\textbf{(a)}.)

\item Selbiges gilt f\"{u}r die Ungleichungen in Satz \ref{thm.2ab}
\textbf{(c)} und in in Satz \ref{thm.2ab} \textbf{(d)}.

\item Die Ungleichung (\ref{eq.exa.aa+bb+cc.eq}) in Beispiel
\ref{exa.aa+bb+cc} wird genau dann zur Gleichheit, wenn $a=b=c$ ist. (Denn
diese Ungleichung wurde durch Aufaddieren der drei Ungleichungen $b^{2}%
+c^{2}\geq2bc$, $c^{2}+a^{2}\geq2ca$ und $a^{2}+b^{2}\geq2ab$ erhalten. Damit
sind zur Gleichheit wird, m\"{u}ssen also alle drei aufaddierten Ungleichungen
zu Gleichheiten werden. Aber dazu ist es n\"{o}tig, dass $b=c$ und $c=a$ und
$a=b$ gilt, denn wir haben ja bereits analysiert, wann die Ungleichung von
Satz \ref{thm.2ab} \textbf{(a)} zur Gleichheit wird. Das hei\ss t, es ist
n\"{o}tig, dass $a=b=c$ ist.)

\item Die Ungleichung (\ref{eq.exa.(y+z)(z+x)(x+y).eq}) in Beispiel
\ref{exa.(y+z)(z+x)(x+y)} wird genau dann zur Gleichheit, wenn%
\[
x=y=z\text{ oder }y=z=0\text{ oder }z=x=0\text{ oder }x=y=0
\]
ist. (Die einfachste Methode, dies einzusehen, ist wohl durch
Fallunterscheidung. Wir haben die Ungleichung (\ref{eq.exa.(y+z)(z+x)(x+y).eq}%
) erhalten, indem wir die drei Ungleichungen $y+z\geq2\sqrt{yz}$,
$z+x\geq2\sqrt{zx}$ und $x+y\geq2\sqrt{xy}$ multipliziert haben. Wenn
\textbf{alle} drei Zahlen $x,y,z$ von $0$ verschieden sind, dann sind alle
Seiten dieser drei Ungleichungen positiv, und somit wird das Produkt dieser
Ungleichungen nur dann zur Gleichheit, wenn sie alle zu Gleichheiten werden;
dazu muss aber $y=z$ und $z=x$ und $x=y$ gelten, also $x=y=z$. Die
\textquotedblleft interessanteren\textquotedblright\ F\"{a}lle sind die, in
denen \textbf{nicht} alle drei Zahlen $x,y,z$ von $0$ verschieden sind. In
solchen F\"{a}llen kann es vorkommen, dass auch eine strikte Ungleichung (also
eine, die nicht zur Gleichheit wird) nach Multiplikation mit einer anderen
Ungleichung zur Gleichheit wird. So wird beispielsweise das Produkt der zwei
Ungleichungen $1\geq0$ und $0\geq0$ zur Gleichheit $1\cdot0=0\cdot0$, obwohl
die erste multiplizierte Ungleichung $1\geq0$ keine Gleichheit ist. Also muss
man hier vorsichtiger vorgehen. Zum Gl\"{u}ck lassen sich diese F\"{a}lle
leicht einzeln angehen: Wenn \textbf{genau zwei} der drei Zahlen $x,y,z$ von
$0$ verschieden sind (d.h., genau eine dieser drei Zahlen $x,y,z$ ist gleich
$0$), dann wird die Ungleichung (\ref{eq.exa.(y+z)(z+x)(x+y).eq})
\textbf{nicht} zur Gleichheit, da die linke Seite positiv ist und die rechte
gleich $0$. Wenn aber \textbf{h\"{o}chstens eine} der drei Zahlen $x,y,z$ von
$0$ verschieden ist (d.h., mindestens zwei von ihnen sind gleich $0$), dann
wird die Ungleichung (\ref{eq.exa.(y+z)(z+x)(x+y).eq}) zur Gleichheit (weil
beide Seiten $0$ sind). Somit erhalten wir obige Klassifikation der Gleichheitsf\"{a}lle.)

\item Die Ungleichung (\ref{eq.exa.sqrt(a+c)(b+d).eq}) in Beispiel
\ref{exa.sqrt(a+c)(b+d)} wird genau dann zur Gleichheit, wenn $ad=bc$ ist.
(Dies sieht man leicht aus dem Beweis, da wir ja wissen, wann die Ungleichung
in Satz \ref{thm.2ab} \textbf{(c)} zur Gleichheit wird.)

\item Die Ungleichung in Beispiel \ref{exa.bc/a+ca/ab+ab/c} wird genau dann
zur Gleichheit, wenn $a=b=c$ ist. (Um dies einzusehen, schauen wir uns wieder
den Beweis an. Wir m\"{u}ssen also nur zeigen, dass $\sqrt{\dfrac{bc}{a}%
}=\sqrt{\dfrac{ca}{b}}=\sqrt{\dfrac{ab}{c}}$ genau dann gilt, wenn $a=b=c$
ist. Dies ist aber leicht.)

\item Die Ungleichung in Beispiel \ref{exa.nesbitt-3} wird genau dann zur
Gleichheit, wenn $a=b=c$ ist. (Auch dies folgt unschwer aus unserem Beweis
dieser Ungleichung. Denn die dort definierten drei Zahlen $x,y,z$ erf\"{u}llen
$x=y=z$ genau dann, wenn $a=b=c$ ist.)
\end{itemize}
\end{remark}

\begin{exercise}
\label{exe.piab-logconc}Seien $a$ und $b$ zwei reelle Zahlen.

\textbf{(a)} Man beweise: $2\left(  a^{2}+b^{2}\right)  \geq\left(
a+b\right)  ^{2}$.

\textbf{(b)} F\"{u}r jedes $i\in\mathbb{N}$ sei $p_{i}=a^{i}+b^{i}$. Sei $m$
eine positive ganze Zahl. Man zeige, dass $p_{m+1}p_{m-1}\geq p_{m}^{2}$ gilt,
wenn $ab\geq0$ ist oder wenn $m$ ungerade ist.
\end{exercise}

\begin{exercise}
\label{exe.3(aa+bb+cc)}Seien $a,b,c$ drei reelle Zahlen.

\textbf{(a)} Man beweise: $3\left(  a^{2}+b^{2}+c^{2}\right)  \geq\left(
b-c\right)  ^{2}+\left(  c-a\right)  ^{2}+\left(  a-b\right)  ^{2}$.

\textbf{(b)} Man beweise: $b^{2}c^{2}+c^{2}a^{2}+a^{2}b^{2}\geq abc\left(
a+b+c\right)  $.
\end{exercise}

\begin{exercise}
\label{exe.1/2(a+b+c+d)sq}Seien $a,b,c,d$ vier reelle Zahlen.

\textbf{(a)} Man beweise: $\dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}\geq\left(
a+c\right)  \left(  b+d\right)  +2\left(  ac+bd\right)  $.

\textbf{(b)} Man beweise:%
\[
3\left(  a+b+c+d\right)  ^{2}\geq8\left(  ab+ac+ad+bc+bd+cd\right)  .
\]

\end{exercise}

Folgende Aufgabe verallgemeinert Beispiel \ref{exa.nesbitt-3}:

\begin{exercise}
\label{exe.nesbitt-n}Sei $n\geq2$ eine ganze Zahl. Seien $a_{1},a_{2}%
,\ldots,a_{n}$ beliebige $n$ positive reelle Zahlen. Man zeige:%
\[
\sum_{i=1}^{n}\dfrac{a_{i}}{a_{1}+a_{2}+\cdots+a_{i-1}+a_{i+1}+\cdots+a_{n}%
}\geq\dfrac{n}{n-1}.
\]
(Im Nenner auf der linken Seite steht die Summe aller Zahlen $a_{1}%
,a_{2},\ldots,a_{n}$ bis auf $a_{i}$.)
\end{exercise}

Die \textit{Cauchy--Schwarz-Ungleichung} besagt folgendes:

\begin{theorem}
[Cauchy--Schwarz-Ungleichung]\label{thm.cs}Sei $n\in\mathbb{N}$. Seien
$a_{1},a_{2},\ldots,a_{n}$ sowie $b_{1},b_{2},\ldots,b_{n}$ beliebige reelle
Zahlen. Dann gilt%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]

\end{theorem}

\begin{exercise}
\label{exe.cs.proof-by-amgm}Man beweise Satz \ref{thm.cs} folgenderma\ss en:

Setze $A=\sqrt{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}$ und $B=\sqrt{b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}}$. Zeige, dass $a_{i}^{2}B^{2}+b_{i}^{2}%
A^{2}\geq2a_{i}b_{i}AB$ f\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $
gilt. Summiere diese Ungleichung \"{u}ber alle $i$ auf, und vereinfache.
\end{exercise}

(Dieser Beweis der Cauchy--Schwarz-Ungleichung enstammt \cite{Lin12}. Wir
werden sp\"{a}ter deutlich mehr \"{u}ber diese Ungleichung erfahren.)

\subsection{Einige Anwendungen}

Die AM-GM-Ungleichung f\"{u}r zwei Zahlen ist schon f\"{u}r einiges gut! Die
folgenden zwei Beispiele aus der Graphentheorie sollten das illustrieren:

\begin{example}
[Satz von Mantel]\label{exa.mantel}Sei $G$ ein schlichter ungerichteter
Graph\footnotemark\ mit $n$ Knoten und mehr als $n^{2}/4$ Kanten. Man zeige:
Der Graph $G$ hat drei Knoten $a$, $b$ und $c$, die paarweise benachbart sind.
\end{example}

\footnotetext{Zur Erinnerung: Ein Graph hei\ss t \textit{schlicht}, wenn er
keine Schlingen und keine Mehrfachkanten hat.}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.mantel}.]Nehmen wir das Gegenteil an. Der
Graph $G$ hat also keine drei Knoten $a$, $b$ und $c$, die paarweise
benachbart sind.

F\"{u}r jeden Knoten $v$ von $G$ sei $N\left(  v\right)  $ die Menge aller zu
$v$ benachbarten Knoten von $G$. Sei $V$ die Menge aller Knoten von $G$. Dann
ist also $\left\vert V\right\vert =n$ (denn $G$ hat $n$ Knoten). Der Graph $G$
hat mehr als $n^{2}/4$ Kanten, also mehr als $0$ Kanten (denn $n^{2}/4\geq0$);
folglich muss der Graph $G$ auch mindestens einen Knoten haben. Das hei\ss t,
$V\neq\varnothing$.

Wir w\"{a}hlen nun einen Knoten $v$ von $G$, f\"{u}r den $\left\vert N\left(
v\right)  \right\vert $ maximal ist. (Dies ist m\"{o}glich, denn
$V\neq\varnothing$.) Dann gilt also%
\begin{equation}
\left\vert N\left(  x\right)  \right\vert \leq\left\vert N\left(  v\right)
\right\vert \ \ \ \ \ \ \ \ \ \ \text{f\"{u}r jeden Knoten }x\in V.
\label{pf.exa.mantel.NxNv}%
\end{equation}


Nun haben wir aber angenommen, dass der Graph $G$ keine drei Knoten $a$, $b$
und $c$ hat, die paarweise benachbart sind. Insbesondere d\"{u}rfen also zwei
verschiedene Nachbarn von $v$ nicht miteinander benachbart sein. Mit anderen
Worten: Zwei verschiedene Knoten in $N\left(  v\right)  $ d\"{u}rfen nicht
miteinander benachbart sein. Mit noch anderen Worten: Es ist nicht
m\"{o}glich, dass beide Endknoten einer Kante von $G$ in $N\left(  v\right)  $
liegen. Das hei\ss t, jede Kante von $G$ hat mindestens einen Endknoten in
$V\setminus N\left(  v\right)  $. Das hei\ss t, jede Kante von $G$
verl\"{a}uft durch mindestens einen Knoten $x\in V\setminus N\left(  v\right)
$. Somit gilt%
\begin{align*}
&  \left(  \text{Anzahl aller Kanten von }G\right) \\
&  \leq\sum_{x\in V\setminus N\left(  v\right)  }\underbrace{\left(
\text{Anzahl aller Kanten von }G\text{, die durch }x\text{ verlaufen}\right)
}_{=\left(  \text{Anzahl aller Nachbarn von }x\right)  =\left\vert N\left(
x\right)  \right\vert }\\
&  =\sum_{x\in V\setminus N\left(  v\right)  }\underbrace{\left\vert N\left(
x\right)  \right\vert }_{\substack{\leq\left\vert N\left(  v\right)
\right\vert \\\text{(nach (\ref{pf.exa.mantel.NxNv}))}}}\leq\sum_{x\in
V\setminus N\left(  v\right)  }\left\vert N\left(  v\right)  \right\vert
=\left\vert V\setminus N\left(  v\right)  \right\vert \cdot\left\vert N\left(
v\right)  \right\vert ,
\end{align*}
also%
\begin{equation}
\left\vert V\setminus N\left(  v\right)  \right\vert \cdot\left\vert N\left(
v\right)  \right\vert \geq\left(  \text{Anzahl aller Kanten von }G\right)
>n^{2}/4 \label{pf.exa.mantel.4}%
\end{equation}
(denn $G$ hat mehr als $n^{2}/4$ Kanten). Doch wegen $N\left(  v\right)
\subseteq V$ gilt $\left\vert V\setminus N\left(  v\right)  \right\vert
=\left\vert V\right\vert -\left\vert N\left(  v\right)  \right\vert $ und
somit $\left\vert V\setminus N\left(  v\right)  \right\vert +\left\vert
N\left(  v\right)  \right\vert =\left\vert V\right\vert =n$. Also ist
$n=\left\vert V\setminus N\left(  v\right)  \right\vert +\left\vert N\left(
v\right)  \right\vert $, daher%
\begin{align*}
n^{2}  &  =\left(  \left\vert V\setminus N\left(  v\right)  \right\vert
+\left\vert N\left(  v\right)  \right\vert \right)  ^{2}\geq4\cdot
\underbrace{\left\vert V\setminus N\left(  v\right)  \right\vert
\cdot\left\vert N\left(  v\right)  \right\vert }_{\substack{>n^{2}%
/4\\\text{(nach (\ref{pf.exa.mantel.4}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{laut Satz \ref{thm.2ab} \textbf{(b)},
angewandt auf }a=\left\vert V\setminus N\left(  v\right)  \right\vert \text{
und }b=\left\vert N\left(  v\right)  \right\vert \right) \\
&  >4\cdot n^{2}/4=n^{2},
\end{align*}
was absurd ist. Dieser Widerspruch zeigt, dass unsere Annahme falsch war;
damit ist Beispiel \ref{exa.mantel} gel\"{o}st.
\end{proof}

(Obige L\"{o}sung stammt aus \cite[Lecture 1, third proof of Theorem
1]{Conlon11}.)

\begin{example}
\label{exa.chess-amgm}Sei $n$ eine positive ganze Zahl. In den $n^{2}$ Feldern
eines $n\times n$-Schachbretts stehen Zahlen; und zwar steht jede der $n$
Zahlen $1,2,\ldots,n$ in genau $n$ Feldern.\footnotemark\ Man zeige: Es gibt
mindestens eine Zeile oder Spalte des Schachbretts, die mindestens $\sqrt{n}$
verschiedene Zahlen enth\"{a}lt.
\end{example}

\footnotetext{Hier ist ein Beispiel f\"{u}r ein solches Schachbrett im Fall
von $n=3$:%
\[
\text{%
\begin{tabular}
[c]{|c|c|c|}\hline
$2$ & $1$ & $3$\\\hline
$3$ & $1$ & $2$\\\hline
$1$ & $3$ & $2$\\\hline
\end{tabular}
}%
\]
}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.chess-amgm}.]Nehmen wir das Gegenteil an.
Jede Zeile oder Spalte des Schachbretts enth\"{a}lt also $<\sqrt{n}$
verschiedene Zahlen. F\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $ sei
$z_{i}$ die Anzahl aller verschiedenen Zahlen in der $i$-ten Zeile, und sei
$s_{i}$ die Anzahl aller verschiedenen Zahlen in der $i$-ten Spalte. Laut
unserer Annahme ist also
\begin{equation}
z_{i}<\sqrt{n}\ \ \ \ \ \ \ \ \ \ \text{und}\ \ \ \ \ \ \ \ \ \ s_{i}<\sqrt{n}
\label{pf.exa.chess-amgm.z-sqrt}%
\end{equation}
f\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $.

F\"{u}r jedes $k\in\left\{  1,2,\ldots,n\right\}  $ sei $z_{k}^{\prime}$ die
Anzahl aller Zeilen, die die Zahl $k$ enthalten, und sei $s_{k}^{\prime}$ die
Anzahl aller Spalten, die die Zahl $k$ enthalten. F\"{u}r jedes $k\in\left\{
1,2,\ldots,n\right\}  $ gilt dann%
\[
z_{k}^{\prime}s_{k}^{\prime}\geq n
\]
(denn es gibt genau $n$ Felder des Schachbretts, in denen die Zahl $k$ steht,
und jedes dieser $n$ Felder liegt in einer der $z_{k}^{\prime}$ Zeilen, die
$k$ enthalten, und in einer der $s_{k}^{\prime}$ Spalten, die $k$ enthalten;
f\"{u}r so ein Feld gibt es aber nur $z_{k}^{\prime}s_{k}^{\prime}$
M\"{o}glichkeiten) und somit%
\begin{align}
z_{k}^{\prime}+s_{k}^{\prime}  &  \geq2\sqrt{z_{k}^{\prime}s_{k}^{\prime}%
}\ \ \ \ \ \ \ \ \ \ \left(  \text{nach Satz \ref{thm.2ab} \textbf{(c)},
angewandt auf }a=z_{k}^{\prime}\text{ und }b=s_{k}^{\prime}\right) \nonumber\\
&  \geq2\sqrt{n}\ \ \ \ \ \ \ \ \ \ \left(  \text{denn }z_{k}^{\prime}%
s_{k}^{\prime}\geq n\right)  . \label{pf.exa.chess-amgm.z-2sqrt}%
\end{align}


Nun gilt%
\begin{equation}
\sum_{i=1}^{n}z_{i}=\sum_{k=1}^{n}z_{k}^{\prime}
\label{pf.exa.chess-amgm.z-doub}%
\end{equation}
(denn auf beiden Seiten dieser Gleichung steht lediglich die Anzahl aller
Paare $\left(  i,k\right)  \in\left\{  1,2,\ldots,n\right\}  ^{2}$ mit der
Eigenschaft, dass die Zahl $k$ in der $i$-ten Zeile vorkommt). Analogerweise
gilt%
\begin{equation}
\sum_{i=1}^{n}s_{i}=\sum_{k=1}^{n}s_{k}^{\prime}.
\label{pf.exa.chess-amgm.s-doub}%
\end{equation}


Addieren wir die Gleichungen (\ref{pf.exa.chess-amgm.z-doub}) und
(\ref{pf.exa.chess-amgm.s-doub}), so erhalten wir%
\[
\sum_{i=1}^{n}z_{i}+\sum_{i=1}^{n}s_{i}=\sum_{k=1}^{n}z_{k}^{\prime}%
+\sum_{k=1}^{n}s_{k}^{\prime}=\sum_{k=1}^{n}\underbrace{\left(  z_{k}^{\prime
}+s_{k}^{\prime}\right)  }_{\substack{\geq2\sqrt{n}\\\text{(nach
(\ref{pf.exa.chess-amgm.z-2sqrt}))}}}\geq\sum_{k=1}^{n}2\sqrt{n}=n\cdot
2\sqrt{n}.
\]
Dies widerspricht aber%
\[
\sum_{i=1}^{n}\underbrace{z_{i}}_{\substack{<\sqrt{n}\\\text{(nach
(\ref{pf.exa.chess-amgm.z-sqrt}))}}}+\sum_{i=1}^{n}\underbrace{s_{i}%
}_{\substack{<\sqrt{n}\\\text{(nach (\ref{pf.exa.chess-amgm.z-sqrt}))}%
}}<\underbrace{\sum_{i=1}^{n}\sqrt{n}}_{=n\sqrt{n}}+\underbrace{\sum_{i=1}%
^{n}\sqrt{n}}_{=n\sqrt{n}}=n\sqrt{n}+n\sqrt{n}=n\cdot2\sqrt{n}.
\]
Dieser Widerspruch ist genau das, was wir brauchen. Beispiel
\ref{exa.chess-amgm} ist damit gel\"{o}st.
\end{proof}

(Obige L\"{o}sung stammt aus \url{https://math.stackexchange.com/a/2950374/} .)

\begin{exercise}
\label{exe.mantel2}Ein Graph $G$ hei\ss e \textit{bipartierbar}, wenn sich
seine Knotenmenge in zwei disjunkte Teilmengen $A$ und $B$ unterteilen
l\"{a}\ss t mit der Eigenschaft, dass jede Kante von $G$ einen Endknoten in
$A$ und einen Endknoten in $B$ hat. (Das Wort \textquotedblleft
unterteilen\textquotedblright\ bedeutet dabei, dass jeder Knoten in $A$ oder
in $B$ liegt. Die Mengen $A$ und $B$ d\"{u}rfen leer sein.)

Sei $G$ ein schlichter ungerichteter Graph mit $n$ Knoten und $n^{2}/4$ Kanten
(wobei $n\in\mathbb{N}$). Angenommen, der Graph $G$ hat keine drei Knoten $a$,
$b$ und $c$, die paarweise benachbart sind. Man zeige, dass $G$ bipartierbar ist.
\end{exercise}

\begin{noncompile}
St\"{a}rkere Aussage: https://www.math.kit.edu/iag6/lehre/extremalgt2016s/media/01-solution.pdf
\end{noncompile}

\begin{exercise}
\label{exe.friendship-paradox}Sei $G$ ein Graph mit Knotenmenge $V$ und
Kantenmenge $E$. Wir nehmen an, dass $G$ keine Schlingen enth\"{a}lt.

F\"{u}r jeden Knoten $v$ von $G$ sei der \textit{Grad} von $v$ definiert als
die Anzahl aller Kanten, die $v$ enthalten. Dieser Grad wird mit $\deg v$ bezeichnet.

Liegt ein Knoten $v$ auf einer Kante $e$, dann bezeichnen wir mit $e/v$ den
von $v$ verschiedenen Endknoten von $e$ (oder $v$ selber, wenn $e$ eine
Schlinge ist). F\"{u}r jeden Knoten $v\in V$ definieren wir eine rationale
Zahl $q_{v}$ durch%
\[
q_{v}=\sum_{\substack{e\in E;\\v\text{ liegt auf }e}}\dfrac{\deg\left(
e/v\right)  }{\deg v}.
\]
(Der Nenner $\deg v$ ist hierbei von $0$ verschieden, wann immer die Summe
nichtleer ist.)

[Grob gesprochen ist $q_{v}$ der durchschnittliche Grad der Nachbarn von $v$.
Genauer gesagt wird der Durchschnitt hier nicht \"{u}ber die Nachbarn von $v$,
sondern \"{u}ber die Kanten durch $v$ gebildet; somit z\"{a}hlen einige
Nachbarn mehrfach, falls es Mehrfachkanten gibt.]

Man zeige:%
\begin{equation}
\sum_{v\in V}q_{v}\geq\sum_{v\in V}\deg v.
\label{eq.exe.friends-neighbors.claim}%
\end{equation}


[Grob gesprochen: Der durchschnittliche Freund eines durchschnittlichen
Social-Network-Users hat mehr Freunde als der User selber.]
\end{exercise}

\begin{exercise}
\label{exe.extcomb.Si-wo-Sj}Seien $n,k\in\mathbb{N}$ mit $k\geq2$. Sei $S$
eine $n$-elementige Menge. Seien $S_{1},S_{2},\ldots,S_{k}$ beliebige
Teilmengen von $S$. Man zeige, dass es zwei Zahlen $i,j\in\left\{
1,2,\ldots,k\right\}  $ mit $i\neq j$ und $\left\vert S_{i}\setminus
S_{j}\right\vert \leq\dfrac{nk}{4\left(  k-1\right)  }$ gibt.
\end{exercise}

\begin{noncompile}
Quelle: https://artofproblemsolving.com/community/c6h83740p496979
\end{noncompile}

\begin{exercise}
\label{exe.extcomb.chess-amgm-gen}Verallgemeinere Beispiel
\ref{exa.chess-amgm} so weit wie m\"{o}glich (z. B. auf rechteckige Matrizen,
auf \textquotedblleft3D-Matrizen\textquotedblright, auf ungleichverteilt
vorkommende Zahlen...).
\end{exercise}

\subsection{AM und GM}

Nach diesen Aufw\"{a}rm\"{u}bungen gehen wir nun zum Verallgemeinern von Satz
\ref{thm.2ab} auf mehrere Zahlen \"{u}ber. Beginnen wir mit drei Zahlen:

\begin{theorem}
[AM-GM-Ungleichung f\"{u}r drei Zahlen]\label{thm.3abc}Seien $a,b,c$ drei
nichtnegative reelle Zahlen.

\textbf{(a)} Es gilt $a^{3}+b^{3}+c^{3}\geq3abc$.

\textbf{(b)} Es gilt $a+b+c\geq3\sqrt[3]{abc}$.
\end{theorem}

\begin{proof}
[Beweis von Satz \ref{thm.3abc}.]\textbf{(a)} Durch stumpfes Ausrechnen
pr\"{u}ft man leicht nach: Es gilt%
\begin{align}
&  a^{3}+b^{3}+c^{3}-3abc\nonumber\\
&  =\left(  a+b+c\right)  \left(  a^{2}+b^{2}+c^{2}-bc-ca-ab\right)  .
\label{pf.thm.3abc.fac}%
\end{align}


\begin{fineprint}
Wie man diese Gleichung nachrechnet, ist klar. Aber wie findet man sie? Dies
ist weniger einfach. Es gibt Algorithmen, um beliebige Polynome mit rationalen
Koeffizienten zu faktorisieren (siehe z. B. \cite[Essay 1.4]{Edwards-Essays}
f\"{u}r einen solchen); man kann also einen Computer nach der Faktorisierung
von $a^{3}+b^{3}+c^{3}-3abc$ fragen und prompt die rechte Seite von
(\ref{pf.thm.3abc.fac}) erhalten. Ohne Computer machen diese Algorithmen viel
weniger Spa\ss \ (und auf einer IMO-Klausur verlangen sie wohl eine seltene
Kombination aus Masochismus und Schnelligkeit). Daher k\"{o}nnen Tricks zum
Faktorisieren von Polynomen immer noch n\"{u}tzlich sein, auch wenn sie nicht
allgemein anwendbar sind. Insbesondere helfen folgende Tricks beim Finden von
(\ref{pf.thm.3abc.fac}):

\begin{itemize}
\item Man kann feststellen, dass $a^{3}+b^{3}+c^{3}-3abc=0$ gilt, wann immer
$a+b+c=0$ ist. (Dies folgt z. B. aus der binomischen Formel f\"{u}r $\left(
a+b\right)  ^{3}$.) Dies suggeriert, dass $a^{3}+b^{3}+c^{3}-3abc$ (als
Polynom in den Variablen $a,b,c$ betrachtet) durch $a+b+c$ teilbar sein
k\"{o}nnte. (Wenn man ein wenig Ringtheorie kennt, wird man sich hier das
\textquotedblleft k\"{o}nnte\textquotedblright\ sparen k\"{o}nnen; wenn ein
Polynom $f\left(  a,b,c\right)  $ auf einer Ebene mit der Gleichung
$ua+vb+wc=t$ (wobei $u,v,w,t$ Konstanten sind) identisch verschwindet, dann
muss das Polynom $f\left(  a,b,c\right)  $ durch $ua+vb+wc-t$ teilbar sein.
Wenn man ein wenig algebraische Geometrie kennt, wird man dies sogar als
Sonderfall des Hilbertschen Nullstellensatzes wiedererkennen (zumindest
f\"{u}r komplexe Zahlen). Aber wir brauchen so etwas nicht zu wissen, um auf
die richtige Idee zu kommen.)

Hat man nun den Verdacht, dass das Polynom $a^{3}+b^{3}+c^{3}-3abc$ durch
$a+b+c$ teilbar sein k\"{o}nnte, dann kann man den Quotienten $\dfrac
{a^{3}+b^{3}+c^{3}-3abc}{a+b+c}$ durch Polynomdivision finden (hierzu
betrachte man $b$ und $c$ als Konstanten, sodass man zwei monische Polynome in
$a$ durcheinander dividieren muss).

\item Alternativ kann man auch bemerken, dass das Polynom $a^{3}+b^{3}%
+c^{3}-3abc$ symmetrisch ist. Nun l\"{a}\ss t sich bekanntlich jedes
symmetrische Polynom in $a,b,c$ als Polynom in den drei
\textit{elementarsymmetrischen Polynomen}%
\[
e_{1}=a+b+c,\ \ \ \ \ \ \ \ \ \ e_{2}=bc+ca+ab,\ \ \ \ \ \ \ \ \ \ e_{3}=abc
\]
ausdr\"{u}cken. Hierf\"{u}r gibt es Algorithmen (siehe z. B. \cite{Brande05}
oder \cite[\S 4.3, Satz 5]{Bosch20} oder \cite[8.5.5]{Kerber04} oder
\cite[Satz 4.4]{Lehn15} oder auch
\href{http://hydra.nat.uni-magdeburg.de/math4u/var/pdf/pu71.pdf}{Aufgabe U.71
in math4u.de}); diese f\"{u}hren auf%
\[
a^{3}+b^{3}+c^{3}-3abc=e_{1}^{3}-3e_{1}e_{2}.
\]
An der rechten Seite hier sieht man sofort, dass $e_{1}$ sich ausklammern
l\"{a}\ss t. Man erh\"{a}lt also
\begin{align*}
a^{3}+b^{3}+c^{3}-3abc  &  =e_{1}^{3}-3e_{1}e_{2}=e_{1}\left(  e_{1}%
^{2}-3e_{2}\right) \\
&  =\left(  a+b+c\right)  \left(  \left(  a+b+c\right)  ^{2}-3\left(
bc+ca+ab\right)  \right) \\
&  =\left(  a+b+c\right)  \left(  a^{2}+b^{2}+c^{2}-bc-ca-ab\right)  .
\end{align*}


Siehe \cite{Jainta02} f\"{u}r einige weitere Anwendungen dieser Methode.
\end{itemize}
\end{fineprint}

Aus (\ref{pf.thm.3abc.fac}) folgt nun%
\begin{equation}
a^{3}+b^{3}+c^{3}-3abc=\underbrace{\left(  a+b+c\right)  }_{\geq
0}\underbrace{\left(  a^{2}+b^{2}+c^{2}-bc-ca-ab\right)  }_{\substack{\geq
0\\\text{(wegen (\ref{eq.exa.aa+bb+cc.eq}))}}}\geq0.\nonumber
\end{equation}
Damit ist $a^{3}+b^{3}+c^{3}\geq3abc$. Also ist Satz \ref{thm.3abc}
\textbf{(a)} bewiesen.

\textbf{(b)} Wenden wir Satz \ref{thm.3abc} \textbf{(a)} auf $\sqrt[3]{a}$,
$\sqrt[3]{b}$ und $\sqrt[3]{c}$ statt $a$, $b$ und $c$ an, so erhalten wir:
\[
\left(  \sqrt[3]{a}\right)  ^{3}+\left(  \sqrt[3]{b}\right)  ^{3}+\left(
\sqrt[3]{c}\right)  ^{3}\geq3\sqrt[3]{a}\sqrt[3]{b}\sqrt[3]{c}=3\sqrt[3]%
{abc}.
\]
Dies vereinfacht sich zu $a+b+c\geq3\sqrt[3]{abc}$. Dies beweist Satz
\ref{thm.3abc} \textbf{(b)}.
\end{proof}

F\"{u}r vier Zahlen brauchen wir eine neue Idee:

\begin{theorem}
[AM-GM-Ungleichung f\"{u}r vier Zahlen]\label{thm.4abcd}Seien $a,b,c,d$ vier
reelle Zahlen.

\textbf{(a)} Es gilt $a^{4}+b^{4}+c^{4}+d^{4}\geq4abcd$.

\textbf{(b)} Wenn $a,b,c,d$ nichtnegativ sind, dann gilt $a+b+c+d\geq
4\sqrt[4]{abcd}$.
\end{theorem}

\begin{proof}
[Beweis von Satz \ref{thm.4abcd}.]\textbf{(a)} Mit der Methode von Satz
\ref{thm.3abc} \textbf{(a)} kommen wir hier nicht weiter; das Polynom
$a^{4}+b^{4}+c^{4}+d^{4}-4abcd$ l\"{a}\ss t sich nicht (nichttrivial)
faktorisieren. Allerdings funktioniert hier eine \textquotedblleft
Divide-and-conquer\textquotedblright-Taktik, denn $4=2\cdot2$. Und zwar haben
wir%
\begin{align*}
\underbrace{a^{4}+b^{4}}_{\substack{=\left(  a^{2}\right)  ^{2}+\left(
b^{2}\right)  ^{2}\\\geq2a^{2}b^{2}\\\text{(nach Satz \ref{thm.2ab}
\textbf{(a)},}\\\text{angewandt auf }a^{2}\text{ und }b^{2}\\\text{statt
}a\text{ und }b\text{)}}}+\underbrace{c^{4}+d^{4}}_{\substack{=\left(
c^{2}\right)  ^{2}+\left(  d^{2}\right)  ^{2}\\\geq2c^{2}d^{2}\\\text{(nach
Satz \ref{thm.2ab} \textbf{(a)},}\\\text{angewandt auf }c^{2}\text{ und }%
d^{2}\\\text{statt }a\text{ und }b\text{)}}}  &  \geq2a^{2}b^{2}+2c^{2}%
d^{2}=2\underbrace{\left(  \left(  ab\right)  ^{2}+\left(  cd\right)
^{2}\right)  }_{\substack{\geq2abcd\\\text{(nach Satz \ref{thm.2ab}
\textbf{(a)},}\\\text{angewandt auf }ab\text{ und }cd\\\text{statt }a\text{
und }b\text{)}}}\\
&  \geq2\cdot2abcd=4abcd.
\end{align*}
Damit ist Satz \ref{thm.4abcd} \textbf{(a)} bewiesen.

\textbf{(b)} Satz \ref{thm.4abcd} \textbf{(b)} folgt aus Satz \ref{thm.4abcd}
\textbf{(a)} genauso, wie Satz \ref{thm.3abc} \textbf{(b)} aus Satz
\ref{thm.3abc} \textbf{(a)} folgte.
\end{proof}

Der Leser mag sich \"{u}berlegen, wieso es in Satz \ref{thm.3abc} \textbf{(a)}
n\"{o}tig war, die Nichtnegativit\"{a}t von $a,b,c$ zu fordern, in Satz
\ref{thm.4abcd} \textbf{(a)} und Satz \ref{thm.2ab} \textbf{(a)} aber nicht.
(Hinweis: Was ist der wichtigste Unterschied zwischen ungeraden und geraden
Potenzen?) Sehen wir aber erst einmal von negativen Zahlen ab, dann sehen Satz
\ref{thm.2ab} \textbf{(a)}, Satz \ref{thm.3abc} \textbf{(a)} und Satz
\ref{thm.4abcd} \textbf{(a)} wie die ersten Glieder einer Kette von S\"{a}tzen
aus. So kann die Katze endlich aus dem Sack:

\begin{theorem}
[AM-GM-Ungleichung f\"{u}r $n$ Zahlen]\label{thm.am-gm}Sei $n$ eine positive
ganze Zahl. Seien $a_{1},a_{2},\ldots,a_{n}$ beliebige $n$ nichtnegative
reelle Zahlen.

\textbf{(a)} Es gilt $a_{1}^{n}+a_{2}^{n}+\cdots+a_{n}^{n}\geq na_{1}%
a_{2}\cdots a_{n}$.

\textbf{(b)} Es gilt $a_{1}+a_{2}+\cdots+a_{n}\geq n\sqrt[n]{a_{1}a_{2}\cdots
a_{n}}$.
\end{theorem}

\begin{proof}
[Beweis von Satz \ref{thm.am-gm}.]Hier m\"{u}ssen wir erst einmal ausholen.
Vergessen wir, dass wir $n$ sowie $a_{1},a_{2},\ldots,a_{n}$ fixiert haben.
Wir beweisen Satz \ref{thm.am-gm} \textbf{(a)} erst einmal in dem Fall, wenn
$n$ eine Zweierpotenz ist. Wir beweisen also folgendes:

\begin{statement}
\textit{Behauptung 1:} Sei $m\in\mathbb{N}$. Seien $a_{1},a_{2},\ldots
,a_{2^{m}}$ beliebige $2^{m}$ reelle Zahlen. Dann gilt%
\[
a_{1}^{2^{m}}+a_{2}^{2^{m}}+\cdots+a_{2^{m}}^{2^{m}}\geq2^{m}a_{1}a_{2}\cdots
a_{2^{m}}.
\]

\end{statement}

[\textit{Beweis von Behauptung 1:} Dies ist im Wesentlichen die
offensichtliche Verallgemeinerung von Satz \ref{thm.2ab} \textbf{(a)}. Hier
der Beweis:

Wir verwenden Induktion nach $m$. Der \textit{Induktionsanfang} ist der Fall
$m=0$; in diesem m\"{u}ssen wir zeigen, dass $a_{1}^{1}\geq1a_{1}$ gilt. Dies
ist keine gro\ss e Herausforderung. Kommen wir also zum
\textit{Induktionsschritt}: Sei $k\in\mathbb{N}$. Nehmen wir an, Behauptung 1
gelte f\"{u}r $m=k$. Wir m\"{u}ssen zeigen, dass Behauptung 1 auch f\"{u}r
$m=k+1$ gilt. Seien also $a_{1},a_{2},\ldots,a_{2^{k+1}}$ beliebige $2^{k+1}$
reelle Zahlen. Wir m\"{u}ssen zeigen, dass
\begin{equation}
a_{1}^{2^{k+1}}+a_{2}^{2^{k+1}}+\cdots+a_{2^{k+1}}^{2^{k+1}}\geq2^{k+1}%
a_{1}a_{2}\cdots a_{2^{k+1}} \label{pf.thm.am-gm.a.c1.pf.1}%
\end{equation}
ist. Laut Induktionsannahme gilt Behauptung 1 f\"{u}r $m=k$; somit k\"{o}nnen
wir Behauptung 1 auf $k$ und $a_{i}^{2}$ statt $m$ und $a_{i}$ anwenden. Wir
erhalten also%
\[
\left(  a_{1}^{2}\right)  ^{2^{k}}+\left(  a_{2}^{2}\right)  ^{2^{k}}%
+\cdots+\left(  a_{2^{k}}^{2}\right)  ^{2^{k}}\geq2^{k}a_{1}^{2}a_{2}%
^{2}\cdots a_{2^{k}}^{2}.
\]
Mit anderen Worten:%
\[
a_{1}^{2^{k+1}}+a_{2}^{2^{k+1}}+\cdots+a_{2^{k}}^{2^{k+1}}\geq2^{k}a_{1}%
^{2}a_{2}^{2}\cdots a_{2^{k}}^{2}%
\]
(denn f\"{u}r jedes $i$ gilt $\left(  a_{i}^{2}\right)  ^{2^{k}}=a_{i}%
^{2\cdot2^{k}}=a_{i}^{2^{k+1}}$). Das gleiche Argument (angewendet auf die
$2^{k}$ Zahlen $a_{2^{k}+1},a_{2^{k}+2},\ldots,a_{2^{k+1}}$ statt den $2^{k}$
Zahlen $a_{1},a_{2},\ldots,a_{2^{k}}$) ergibt%
\[
a_{2^{k}+1}^{2^{k+1}}+a_{2^{k}+2}^{2^{k+1}}+\cdots+a_{2^{k+1}}^{2^{k+1}}%
\geq2^{k}a_{2^{k}+1}^{2}a_{2^{k}+2}^{2}\cdots a_{2^{k+1}}^{2}.
\]
Nun ist%
\begin{align*}
&  a_{1}^{2^{k+1}}+a_{2}^{2^{k+1}}+\cdots+a_{2^{k+1}}^{2^{k+1}}\\
&  =\underbrace{\left(  a_{1}^{2^{k+1}}+a_{2}^{2^{k+1}}+\cdots+a_{2^{k}%
}^{2^{k+1}}\right)  }_{\geq2^{k}a_{1}^{2}a_{2}^{2}\cdots a_{2^{k}}^{2}%
}+\underbrace{\left(  a_{2^{k}+1}^{2^{k+1}}+a_{2^{k}+2}^{2^{k+1}}%
+\cdots+a_{2^{k+1}}^{2^{k+1}}\right)  }_{\geq2^{k}a_{2^{k}+1}^{2}a_{2^{k}%
+2}^{2}\cdots a_{2^{k+1}}^{2}}\\
&  \geq2^{k}a_{1}^{2}a_{2}^{2}\cdots a_{2^{k}}^{2}+2^{k}a_{2^{k}+1}%
^{2}a_{2^{k}+2}^{2}\cdots a_{2^{k+1}}^{2}=2^{k}\left(  \underbrace{a_{1}%
^{2}a_{2}^{2}\cdots a_{2^{k}}^{2}}_{=\left(  a_{1}a_{2}\cdots a_{2^{k}%
}\right)  ^{2}}+\underbrace{a_{2^{k}+1}^{2}a_{2^{k}+2}^{2}\cdots a_{2^{k+1}%
}^{2}}_{=\left(  a_{2^{k}+1}a_{2^{k}+2}\cdots a_{2^{k+1}}\right)  ^{2}}\right)
\\
&  =2^{k}\underbrace{\left(  \left(  a_{1}a_{2}\cdots a_{2^{k}}\right)
^{2}+\left(  a_{2^{k}+1}a_{2^{k}+2}\cdots a_{2^{k+1}}\right)  ^{2}\right)
}_{\substack{\geq2\left(  a_{1}a_{2}\cdots a_{2^{k}}\right)  \cdot\left(
a_{2^{k}+1}a_{2^{k}+2}\cdots a_{2^{k+1}}\right)  \\\text{(nach Satz
\ref{thm.2ab} \textbf{(a)},}\\\text{angewandt auf }a=a_{1}a_{2}\cdots
a_{2^{k}}\\\text{und }b=a_{2^{k}+1}a_{2^{k}+2}\cdots a_{2^{k+1}}\text{)}}}\\
&  \geq\underbrace{2^{k}\cdot2}_{=2^{k+1}}\underbrace{\left(  a_{1}a_{2}\cdots
a_{2^{k}}\right)  \cdot\left(  a_{2^{k}+1}a_{2^{k}+2}\cdots a_{2^{k+1}%
}\right)  }_{=a_{1}a_{2}\cdots a_{2^{k+1}}}=2^{k+1}a_{1}a_{2}\cdots
a_{2^{k+1}}.
\end{align*}
Damit ist (\ref{pf.thm.am-gm.a.c1.pf.1}) gezeigt. Behauptung 1 gilt also
f\"{u}r $m=k+1$. Damit ist der Induktionsschritt vollendet, und Behauptung 1
ist bewiesen.]

Satz \ref{thm.am-gm} \textbf{(b)} k\"{o}nnen wir f\"{u}r $n=2^{m}$ nun
ebenfalls herleiten:

\begin{statement}
\textit{Behauptung 2:} Sei $m\in\mathbb{N}$. Seien $a_{1},a_{2},\ldots
,a_{2^{m}}$ beliebige $2^{m}$ nichtnegative reelle Zahlen. Dann gilt%
\[
a_{1}+a_{2}+\cdots+a_{2^{m}}\geq2^{m}\sqrt[2^{m}]{a_{1}a_{2}\cdots a_{2^{m}}%
}.
\]

\end{statement}

[\textit{Beweis von Behauptung 2:} Behauptung 1 (angewandt auf $\sqrt[2^{m}%
]{a_{i}}$ statt $a_{i}$) ergibt%
\begin{align*}
\left(  \sqrt[2^{m}]{a_{1}}\right)  ^{2^{m}}+\left(  \sqrt[2^{m}]{a_{2}%
}\right)  ^{2^{m}}+\cdots+\left(  \sqrt[2^{m}]{a_{2^{m}}}\right)  ^{2^{m}}  &
\geq2^{m}\sqrt[2^{m}]{a_{1}}\sqrt[2^{m}]{a_{2}}\cdots\sqrt[2^{m}]{a_{2^{m}}}\\
&  =2^{m}\sqrt[2^{m}]{a_{1}a_{2}\cdots a_{2^{m}}}.
\end{align*}
Da $\left(  \sqrt[2^{m}]{a_{i}}\right)  ^{2^{m}}=a_{i}$ f\"{u}r jedes $i$
gilt, vereinfacht sich dies zu%
\[
a_{1}+a_{2}+\cdots+a_{2^{m}}\geq2^{m}\sqrt[2^{m}]{a_{1}a_{2}\cdots a_{2^{m}}%
}.
\]
Behauptung 2 ist damit bewiesen.]

Nun kommen wir zum allgemeinen Beweis von Satz \ref{thm.am-gm} \textbf{(b)}
(woraus wir dann nachher Satz \ref{thm.am-gm} \textbf{(a)} herleiten werden):

\textbf{(b)} Es gibt sicherlich eine Zahl $m\in\mathbb{N}$ mit $2^{m}\geq n$
(beispielsweise kann man $m=n$ nehmen, denn bekanntlich ist $2^{n}\geq n$).
Betrachten wir eine solche Zahl $m$. Wir setzen $g=\sqrt[n]{a_{1}a_{2}\cdots
a_{n}}$. Wir erweitern nun unser $n$-Tupel $\left(  a_{1},a_{2},\ldots
,a_{n}\right)  $ zu einem $2^{m}$-Tupel $\left(  a_{1},a_{2},\ldots,a_{2^{m}%
}\right)  $, indem wir
\begin{equation}
a_{n+1}=a_{n+2}=\cdots=a_{2^{m}}=g \label{pf.thm.am-gm.b.set}%
\end{equation}
setzen (dies ist legitim, denn $2^{m}\geq n$). Die Zahlen $a_{1},a_{2}%
,\ldots,a_{2^{m}}$ sind nichtnegative reelle Zahlen; laut Behauptung 2 gilt
also%
\[
a_{1}+a_{2}+\cdots+a_{2^{m}}\geq2^{m}\sqrt[2^{m}]{a_{1}a_{2}\cdots a_{2^{m}}%
}.
\]
Wegen
\begin{align*}
a_{1}+a_{2}+\cdots+a_{2^{m}}  &  =\left(  a_{1}+a_{2}+\cdots+a_{n}\right)
+\underbrace{\left(  a_{n+1}+a_{n+2}+\cdots+a_{2^{m}}\right)  }%
_{\substack{=\left(  2^{m}-n\right)  g\\\text{(wegen (\ref{pf.thm.am-gm.b.set}%
))}}}\\
&  =\left(  a_{1}+a_{2}+\cdots+a_{n}\right)  +\left(  2^{m}-n\right)  g
\end{align*}
und%
\[
a_{1}a_{2}\cdots a_{2^{m}}=\underbrace{\left(  a_{1}a_{2}\cdots a_{n}\right)
}_{\substack{=g^{n}\\\text{(denn }\sqrt[n]{a_{1}a_{2}\cdots a_{n}}=g\text{)}%
}}\underbrace{\left(  a_{n+1}a_{n+2}\cdots a_{2^{m}}\right)  }%
_{\substack{=g^{2^{m}-n}\\\text{(wegen (\ref{pf.thm.am-gm.b.set}))}}%
}=g^{n}g^{2^{m}-n}=g^{2^{m}}%
\]
vereinfacht sich dies zu%
\[
\left(  a_{1}+a_{2}+\cdots+a_{n}\right)  +\left(  2^{m}-n\right)  g\geq
2^{m}\underbrace{\sqrt[2^{m}]{g^{2^{m}}}}_{=g}=2^{m}g.
\]
Subtrahieren wir $\left(  2^{m}-n\right)  g$ von dieser Ungleichung, so
erhalten wir%
\[
a_{1}+a_{2}+\cdots+a_{n}\geq2^{m}g-\left(  2^{m}-n\right)  g=n\underbrace{g}%
_{=\sqrt[n]{a_{1}a_{2}\cdots a_{n}}}=n\sqrt[n]{a_{1}a_{2}\cdots a_{n}}.
\]
Satz \ref{thm.am-gm} \textbf{(b)} ist damit bewiesen.

\textbf{(a)} Wenden wir Satz \ref{thm.am-gm} \textbf{(b)} auf $a_{i}^{n}$
statt $a_{i}$ an, so erhalten wir%
\[
a_{1}^{n}+a_{2}^{n}+\cdots+a_{n}^{n}\geq n\underbrace{\sqrt[n]{a_{1}^{n}%
a_{2}^{n}\cdots a_{n}^{n}}}_{=a_{1}a_{2}\cdots a_{n}}=na_{1}a_{2}\cdots
a_{n}.
\]
Damit ist Satz \ref{thm.am-gm} \textbf{(a)} bewiesen.
\end{proof}

Dieser Beweis verdient aufgrund seiner merkw\"{u}rdigen Struktur einen
Kommentar. Im Wesentlichen besteht die Idee darin, den Satz zuerst durch
Induktion f\"{u}r alle Zweierpotenzen zu beweisen (also f\"{u}r $n=2^{m}$),
und dann durch \textquotedblleft R\"{u}ckw\"{a}rtssprung\textquotedblright%
\ auf alle nat\"{u}rlichen Zahlen auszudehnen. Diese Argumentationsstruktur
wird \"{o}fters \textit{Cauchy-Induktion} genannt. Sie geh\"{o}rt nicht zu den
h\"{a}ufigsten Beweismethoden, tritt aber immer wieder auf. Ein anderes
Beispiel f\"{u}r ihre Anwendung ist
\href{https://www.mathe-wettbewerbe.de/bwm/aufgaben/aufgaben-2005/loes_05_1_e.pdf}{BWM
2005/1/4}.

Die Terminologie \textquotedblleft AM-GM-Ungleichung\textquotedblright\ steht
kurz f\"{u}r \textquotedblleft Ungleichung zwischen dem arithmetischen und dem
geometrischen Mittel\textquotedblright. Das \textit{arithmetische Mittel} von
$n$ reellen Zahlen $a_{1},a_{2},\ldots,a_{n}$ ist definiert als $\dfrac
{a_{1}+a_{2}+\cdots+a_{n}}{n}$; das \textit{geometrische Mittel} von $n$
nichtnegativen reellen Zahlen $a_{1},a_{2},\ldots,a_{n}$ ist definiert als
$\sqrt[n]{a_{1}a_{2}\cdots a_{n}}$. Satz \ref{thm.am-gm} \textbf{(b)} sagt
also aus, dass das arithmetische Mittel von $n$ nichtnegativen reellen Zahlen
mindestens so gro\ss \ ist wie deren geometrisches Mittel. Die zwei
bekanntesten Verallgemeinerungen von Satz \ref{thm.am-gm} \textbf{(b)} sind
die sogenannte \textit{Potenzmittelungleichung} (auf Englisch
\textquotedblleft power means inequality\textquotedblright, was auf seine
eigene Weise zweideutig ist) und die sogenannte \textit{gewichtete
AM-GM-Ungleichung} (und noch allgemeiner gibt es die \textit{gewichtete
Potenzmittelungleichung}, die beide verallgemeinert). Aber bereits die
AM-GM-Ungleichung hat viele (und oft unerwartete) Anwendungen:

\begin{example}
\label{exa.vasc-1-23a}Seien $a,b,c$ drei positive reelle Zahlen mit $abc=1$.
Man zeige:%
\begin{equation}
\dfrac{a-1}{b}+\dfrac{b-1}{c}+\dfrac{c-1}{a}\geq0.
\label{eq.exa.vasc-1-23a.eq}%
\end{equation}

\end{example}

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.vasc-1-23a}.]Die linke Seite der zu
beweisenden Ungleichung (\ref{eq.exa.vasc-1-23a.eq}) ist
\begin{align*}
\dfrac{a-1}{b}+\dfrac{b-1}{c}+\dfrac{c-1}{a}  &  =\dfrac{1}{abc}%
\underbrace{\left(  \left(  a-1\right)  ca+\left(  b-1\right)  ab+\left(
c-1\right)  bc\right)  }_{=ab^{2}+bc^{2}+ca^{2}-bc-ca-ab}\\
&  =\dfrac{1}{abc}\left(  ab^{2}+bc^{2}+ca^{2}-bc-ca-ab\right)  .
\end{align*}
Also reicht es aus zu zeigen, dass $ab^{2}+bc^{2}+ca^{2}-bc-ca-ab\geq0$ ist
(denn $abc$ ist ja positiv). Mit anderen Worten: Wir m\"{u}ssen zeigen, dass
$ab^{2}+bc^{2}+ca^{2}\geq bc+ca+ab$ ist.

Dazu wenden wir Satz \ref{thm.3abc} \textbf{(b)} auf $ab^{2}$, $bc^{2}$ und
$bc^{2}$ statt $a$, $b$ und $c$ an; dadurch erhalten wir
\[
ab^{2}+bc^{2}+bc^{2}\geq3\sqrt[3]{ab^{2}\cdot bc^{2}\cdot bc^{2}}%
=3\sqrt[3]{ab^{4}c^{4}}=3bc\underbrace{\sqrt[3]{abc}}%
_{\substack{=1\\\text{(denn }abc=1\text{)}}}=3bc.
\]
Zyklische Vertauschung der Variablen ergibt die analogen Ungleichungen%
\begin{align*}
bc^{2}+ca^{2}+ca^{2}  &  \geq3ca\ \ \ \ \ \ \ \ \ \ \text{und}\\
ca^{2}+ab^{2}+ab^{2}  &  \geq3ab.
\end{align*}
Addieren wir diese drei Ungleichungen auf, so erhalten wir%
\[
\left(  ab^{2}+bc^{2}+bc^{2}\right)  +\left(  bc^{2}+ca^{2}+ca^{2}\right)
+\left(  ca^{2}+ab^{2}+ab^{2}\right)  \geq3bc+3ca+3ab.
\]
Dies vereinfacht sich zu%
\[
3\left(  ab^{2}+bc^{2}+ca^{2}\right)  \geq3\left(  bc+ca+ab\right)  .
\]
Dividieren wir diese Ungleichung durch $3$, so erhalten wir $ab^{2}%
+bc^{2}+ca^{2}\geq bc+ca+ab$. Wie wir aber bereits gesehen haben, ist damit
Beispiel \ref{exa.vasc-1-23a} gel\"{o}st.
\end{proof}

Das n\"{a}chste, recht skurrile Beispiel stammt aus \cite[Chapter 9, Problem
13]{Hung07}:

\begin{example}
\label{exa.hung-9-13}Seien $a,b,c,d$ nichtnegative reelle Zahlen. Man zeige:%
\[
ab\left(  b+c\right)  +bc\left(  c+d\right)  +cd\left(  d+a\right)  +da\left(
a+b\right)  \leq\dfrac{4}{27}\left(  a+b+c+d\right)  ^{3}.
\]

\end{example}

Die Merkw\"{u}rdigkeit dieser Ungleichung ist schon daran zu erkennen, dass
die Gleichheit nicht etwa f\"{u}r $a=b=c=d$ eintritt, sondern im Fall, wenn
das $4$-Tupel $\left(  a,b,c,d\right)  $ proportional zu einem der $4$-Tupel
$\left(  1,2,0,0\right)  $, $\left(  0,1,2,0\right)  $, $\left(
0,0,1,2\right)  $ und $\left(  2,0,0,1\right)  $ ist. Wenn man dies
fr\"{u}hzeitig erkennt, kann man m\"{o}glicherweise einige Aufschl\"{u}sse
\"{u}ber die m\"{o}glichen Argumentationswege im Beweis der Ungleichung
erhalten (so kann man z. B. nicht die Summe $a+b+c+d$ auf der rechten Seite
durch ein $4\sqrt[4]{abcd}$ absch\"{a}tzen, weil dies die Gleichheitsf\"{a}lle
zerst\"{o}ren w\"{u}rde). Aber auch nach solcher Vorarbeit wird folgende
L\"{o}sung wohl einige \"{U}berraschungen bieten:

\begin{proof}
[L\"{o}sung zu Beispiel \ref{exa.hung-9-13}.]Die Ungleichung, die wir beweisen
wollen, ist invariant gegen\"{u}ber zyklischer Vertauschung der Variablen
$a,b,c,d$; das hei\ss t, wenn wir $a,b,c,d$ durch $b,c,d,a$ ersetzen, dann
ver\"{a}ndert sich die Ungleichung nicht.\footnote{Sie ver\"{a}ndert sich aber
sehr wohl, wenn wir $a,b,c,d$ (beispielsweise) durch $b,a,c,d$ ersetzen.}
Durch eine solche Vertauschung k\"{o}nnen wir aber erzielen, dass $b+d\leq
a+c$ ist (denn eine solche Vertauschung vertauscht auch die Rollen von $a+c$
und $b+d$). Wir k\"{o}nnen also o. B. d. A. annehmen, dass $b+d\leq a+c$ gilt.
Nehmen wir dies an.

Nun zeigt aber eine kurze Rechnung, dass%
\begin{align}
&  ab\left(  b+c\right)  +bc\left(  c+d\right)  +cd\left(  d+a\right)
+da\left(  a+b\right) \nonumber\\
&  =\left(  a+c\right)  \left(  bc+da\right)  +\underbrace{\left(  b+d\right)
}_{\leq a+c}\left(  ab+cd\right) \nonumber\\
&  \leq\left(  a+c\right)  \left(  bc+da\right)  +\left(  a+c\right)  \left(
ab+cd\right) \nonumber\\
&  =\left(  a+c\right)  \underbrace{\left(  bc+da+ab+cd\right)  }%
_{\substack{=ab+bc+cd+da\\=\left(  a+c\right)  \left(  b+d\right)
}}\nonumber\\
&  =\left(  a+c\right)  \left(  a+c\right)  \left(  b+d\right)  .
\label{sol.hung-9-13.1}%
\end{align}


\begin{fineprint}
(In dieser Rechnung sind einige interessante Tricks verborgen. Insbesondere
ist es nicht verkehrt, sich die Faktorisierung $ab+bc+cd+da=\left(
a+c\right)  \left(  b+d\right)  $ zu merken!)
\end{fineprint}

Nun ist aber%
\[
2\left(  a+b+c+d\right)  =\left(  a+c\right)  +\left(  a+c\right)  +2\left(
b+d\right)  \geq3\sqrt[3]{\left(  a+c\right)  \left(  a+c\right)
\cdot2\left(  b+d\right)  }%
\]
(nach Satz \ref{thm.3abc} \textbf{(b)}, angewandt auf $a+c$, $a+c$ und
$2\left(  b+d\right)  $ statt $a$, $b$ und $c$). Nehmen wir beide Seiten
dieser Ungleichung in die dritte Potenz, so erhalten wir%
\begin{align*}
\left(  2\left(  a+b+c+d\right)  \right)  ^{3}  &  \geq\left(  3\sqrt[3]%
{\left(  a+c\right)  \left(  a+c\right)  \cdot2\left(  b+d\right)  }\right)
^{3}\\
&  =27\left(  a+c\right)  \left(  a+c\right)  \cdot2\left(  b+d\right) \\
&  =2\cdot27\left(  a+c\right)  \left(  a+c\right)  \left(  b+d\right)  ,
\end{align*}
also%
\begin{align}
\left(  a+c\right)  \left(  a+c\right)  \left(  b+d\right)   &  \leq\dfrac
{1}{2\cdot27}\left(  2\left(  a+b+c+d\right)  \right)  ^{3}\nonumber\\
&  =\dfrac{4}{27}\left(  a+b+c+d\right)  ^{3}. \label{sol.hung-9-13.2}%
\end{align}
Nun wird (\ref{sol.hung-9-13.1}) zu%
\begin{align*}
&  ab\left(  b+c\right)  +bc\left(  c+d\right)  +cd\left(  d+a\right)
+da\left(  a+b\right) \\
&  \leq\left(  a+c\right)  \left(  a+c\right)  \left(  b+d\right)  \leq
\dfrac{4}{27}\left(  a+b+c+d\right)  ^{3}\ \ \ \ \ \ \ \ \ \ \left(
\text{nach (\ref{sol.hung-9-13.2})}\right)  .
\end{align*}
Damit ist Beispiel \ref{exa.hung-9-13} gel\"{o}st.
\end{proof}

\begin{exercise}
\label{exe.a/b-sum-3}Seien $a,b,c$ drei positive reelle Zahlen. Man beweise:
\[
\dfrac{a}{b}+\dfrac{b}{c}+\dfrac{c}{a}\geq3.
\]

\end{exercise}

\begin{exercise}
\label{exe.hung.sumab(b+c)}Seien $a,b,c$ drei nichtnegative reelle Zahlen. Man
beweise:
\[
ab\left(  b+c\right)  +bc\left(  c+a\right)  +ca\left(  a+b\right)  \leq
\dfrac{2}{9}\left(  a+b+c\right)  ^{3}.
\]

\end{exercise}

\begin{exercise}
\label{exe.mse192763}Seien $a,b,c,d,e,f$ sechs nichtnegative reelle Zahlen.
Man beweise:%
\[
abc+bcd+cde+def+efa+fab\leq\dfrac{1}{27}\left(  a+b+c+d+e+f\right)  ^{3}.
\]

\end{exercise}

\subsection{Youngs Ungleichung}

\textit{Youngs Ungleichung} (oder \textit{Youngs Produktungleichung}) ist
folgender Satz:

\begin{theorem}
[Young--Ungleichung]\label{thm.young}Seien $a$ und $b$ zwei nichtnegative
reelle Zahlen. Seien $p$ und $q$ zwei positive reelle Zahlen mit $\dfrac{1}%
{p}+\dfrac{1}{q}=1$. Dann gilt%
\[
\dfrac{a^{p}}{p}+\dfrac{b^{q}}{q}\geq ab.
\]

\end{theorem}

Satz \ref{thm.2ab} \textbf{(a)} f\"{u}r nichtnegative Zahlen $a$ und $b$ ist
der Sonderfall von Satz \ref{thm.young} f\"{u}r $p=2$ und $q=2$. Satz
\ref{thm.young} ist also sozusagen eine \textquotedblleft
schiefe\textquotedblright\ (\textquotedblleft biased\textquotedblright)
Version von Satz \ref{thm.2ab} \textbf{(a)}. (\textquotedblleft
Schief\textquotedblright\ in dem Sinne, dass $a$ und $b$ in verschiedenen
Potenzen vorkommen.)

Wir beweisen Satz \ref{thm.young} im Falle von $p,q\in\mathbb{Q}$:

\begin{proposition}
\label{prop.youngQQ}Seien $a$ und $b$ zwei nichtnegative reelle Zahlen. Seien
$p$ und $q$ zwei positive rationale Zahlen mit $\dfrac{1}{p}+\dfrac{1}{q}=1$.
Dann gilt%
\[
\dfrac{a^{p}}{p}+\dfrac{b^{q}}{q}\geq ab.
\]

\end{proposition}

\begin{proof}
[Beweis von Proposition \ref{prop.youngQQ}.]Die Zahl $p$ ist positiv und
rational; also ist auch ihr Kehrwert $\dfrac{1}{p}$ positiv und rational. Wir
k\"{o}nnen also $\dfrac{1}{p}$ in der Form $\dfrac{1}{p}=\dfrac{k}{n}$
schreiben f\"{u}r zwei positive ganze Zahlen $k$ und $n$. Betrachten wir diese
Zahlen $k$ und $n$.

Aus $\dfrac{1}{p}+\dfrac{1}{q}=1$ erhalten wir $\dfrac{1}{q}%
=1-\underbrace{\dfrac{1}{p}}_{=\dfrac{k}{n}}=1-\dfrac{k}{n}=\dfrac{n-k}{n}$.
Wir setzen $m=n-k$; dann ist $m$ eine ganze Zahl (denn $k$ und $n$ sind ganz)
und erf\"{u}llt $k+m=n$ (denn $m=n-k$). Ferner ist $\dfrac{1}{q}=\dfrac
{n-k}{n}=\dfrac{m}{n}$ (denn $n-k=m$), also $m=\dfrac{n}{q}>0$ (denn $n>0$ und
$q>0$). Also ist $m$ eine positive ganze Zahl.

Aus $\dfrac{1}{p}=\dfrac{k}{n}$ folgt $p=\dfrac{n}{k}=n/k$. Aus $\dfrac{1}%
{q}=\dfrac{m}{n}$ folgt $q=\dfrac{n}{m}=n/m$.

Seien $\alpha=a^{1/k}$ und $\beta=b^{1/m}$. Dies sind nichtnegative reelle
Zahlen (denn $a$ und $b$ sind nichtnegative reelle Zahlen).

Nun definieren wir $n$ nichtnegative reelle Zahlen $a_{1},a_{2},\ldots,a_{n}$
durch%
\[
\left(  a_{1},a_{2},\ldots,a_{n}\right)  =\left(  \underbrace{\alpha
,\alpha,\ldots,\alpha}_{k\text{ mal}},\underbrace{\beta,\beta,\ldots,\beta
}_{m\text{ mal}}\right)
\]
\footnote{Dies ist wohldefiniert, denn wegen $k+m=n$ ist $\left(
\underbrace{\alpha,\alpha,\ldots,\alpha}_{k\text{ mal}},\underbrace{\beta
,\beta,\ldots,\beta}_{m\text{ mal}}\right)  $ ein $n$-Tupel.}. Dann ist also%
\begin{align}
&  a_{1}^{n}+a_{2}^{n}+\cdots+a_{n}^{n}\nonumber\\
&  =\underbrace{\alpha^{n}+\alpha^{n}+\cdots+\alpha^{n}}_{k\text{ mal}%
}+\underbrace{\beta^{n}+\beta^{n}+\cdots+\beta^{n}}_{m\text{ mal}}=k\alpha
^{n}+m\beta^{n}\nonumber\\
&  =\underbrace{k}_{\substack{=n/p\\\text{(denn }p=n/k\text{)}}%
}\ \ \underbrace{\left(  a^{1/k}\right)  ^{n}}_{\substack{=a^{\left(
1/k\right)  n}=a^{p}\\\text{(denn }\left(  1/k\right)  n=n/k=p\text{)}%
}}+\underbrace{m}_{\substack{=n/q\\\text{(denn }q=n/m\text{)}}%
}\ \ \underbrace{\left(  b^{1/m}\right)  ^{n}}_{\substack{=b^{\left(
1/m\right)  n}=b^{q}\\\text{(denn }\left(  1/m\right)  n=n/m=q\text{)}%
}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{denn }\alpha
=a^{1/k}\text{ und }\beta=b^{1/m}\right) \nonumber\\
&  =\left(  n/p\right)  a^{p}+\left(  n/q\right)  b^{q}=n\left(  \dfrac{a^{p}%
}{p}+\dfrac{b^{q}}{q}\right)  \label{pf.prop.youngQQ.4}%
\end{align}
und%
\begin{equation}
a_{1}a_{2}\cdots a_{n}=\underbrace{\alpha\alpha\cdots\alpha}_{k\text{ mal}%
}\underbrace{\beta\beta\cdots\beta}_{m\text{ mal}}=\underbrace{\alpha^{k}%
}_{\substack{=a\\\text{(da }\alpha=a^{1/k}\text{)}}}\ \ \underbrace{\beta^{m}%
}_{\substack{=b\\\text{(da }\beta=b^{1/m}\text{)}}}=ab.
\label{pf.prop.youngQQ.5}%
\end{equation}
Doch Satz \ref{thm.am-gm} \textbf{(a)} ergibt $a_{1}^{n}+a_{2}^{n}%
+\cdots+a_{n}^{n}\geq na_{1}a_{2}\cdots a_{n}$. Wegen (\ref{pf.prop.youngQQ.4}%
) und (\ref{pf.prop.youngQQ.5}) k\"{o}nnen wir dies umschreiben als $n\left(
\dfrac{a^{p}}{p}+\dfrac{b^{q}}{q}\right)  \geq nab$. Division durch $n$ ergibt
$\dfrac{a^{p}}{p}+\dfrac{b^{q}}{q}\geq ab$. Damit ist Proposition
\ref{prop.youngQQ} bewiesen.
\end{proof}

Satz \ref{thm.young} folgt aus Proposition \ref{prop.youngQQ} durch ein
Stetigkeitsargument\footnote{In der Tat ist $\dfrac{a^{p}}{p}+\dfrac{b^{q}}%
{q}$ eine stetige Funktion in $p$, wenn wir $a$ und $b$ festhalten und $q$
durch $\dfrac{1}{1-\dfrac{1}{p}}$ ersetzt denken (denn die Bedingung
$\dfrac{1}{p}+\dfrac{1}{q}=1$ f\"{u}hrt zu $q=\dfrac{1}{1-\dfrac{1}{p}}$). Da
wir (aus Proposition \ref{prop.youngQQ}) wissen, dass alle Werte dieser
Funktion f\"{u}r rationales $p>1$ nicht kleiner sind als $ab$, folgt dies aus
der Stetigkeit also auch f\"{u}r alle Werte mit reellem $p>1$. Wir
\"{u}berlassen die Details dem Leser, da wir uns f\"{u}r irrationale
Exponenten hier nicht besonders interessieren.}.

Die \textit{H\"{o}lder-Ungleichung} verallgemeinert die
Cauchy--Schwarz-Ungleichung ungef\"{a}hr so, wie die Young-Ungleichung Satz
\ref{thm.2ab} \textbf{(a)} verallgemeinert (aber wieder nur im Fall, wenn alle
vorkommenden Zahlen nichtnegativ sind):

\Needspace{5cm}

\begin{theorem}
[H\"{o}lder-Ungleichung]\label{thm.holder}Sei $n\in\mathbb{N}$. Seien
$a_{1},a_{2},\ldots,a_{n}$ sowie $b_{1},b_{2},\ldots,b_{n}$ nichtnegative
reelle Zahlen. Seien $p$ und $q$ zwei positive reelle Zahlen mit $\dfrac{1}%
{p}+\dfrac{1}{q}=1$. Dann gilt%
\[
\sqrt[p]{a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}}\cdot\sqrt[q]{b_{1}^{q}%
+b_{2}^{q}+\cdots+b_{n}^{q}}\geq a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}.
\]

\end{theorem}

\begin{exercise}
\label{exe.holder.proof-by-young}Man beweise Satz \ref{thm.holder}.

[\textbf{Hinweis:} Siehe Aufgabe \ref{exe.cs.proof-by-amgm} f\"{u}r den Fall
$p=2$ und $q=2$.]
\end{exercise}

\newpage

\section{Cauchy--Schwarz (Kapitel im Entstehen)}

\subsection{Zwei neue Beweise}

Die Cauchy--Schwarz-Ungleichung (Satz \ref{thm.cs}) haben wir bereits in
Kapitel \ref{chp.AM-GM} gesehen. Jedoch gibt es viel mehr \"{u}ber sie zu
sagen. In den meisten B\"{u}chern \"{u}ber Ungleichungen findet sich ein
Kapitel \"{u}ber sie; auch ein ganzes Buch (\cite{Steele04}) wurde schon
\"{u}ber sie geschrieben. Wir werden im Folgenden einige ihrer Anwendungen und
Varianten sehen.

Zun\"{a}chst geben wir zwei weitere Beweise f\"{u}r sie. Erst einmal wollen
wir ihre Behauptung noch einmal formulieren:

\begin{theorem}
[Cauchy--Schwarz-Ungleichung]\label{thm.cs-REPEAT}Sei $n\in\mathbb{N}$. Seien
$a_{1},a_{2},\ldots,a_{n}$ sowie $b_{1},b_{2},\ldots,b_{n}$ beliebige reelle
Zahlen. Dann gilt%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]

\end{theorem}

\begin{proof}
[Erster Beweis von Satz \ref{thm.cs-REPEAT}.](Wenn man den Beweis in Aufgabe
\ref{exe.cs.proof-by-amgm} mitz\"{a}hlt, dann ist dies nat\"{u}rlich ein
zweiter Beweis.) Der folgende Beweis st\"{u}tzt sich vor allem auf die
Standard-Rechenregeln f\"{u}r Summationszeichen.

Sei $\left[  n\right]  $ die Menge $\left\{  1,2,\ldots,n\right\}  $. Dann ist%
\begin{align*}
&  \underbrace{\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  }%
_{=\sum_{i\in\left[  n\right]  }a_{i}^{2}}\underbrace{\left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  }_{=\sum_{j\in\left[  n\right]  }b_{j}%
^{2}}\\
&  =\left(  \sum_{i\in\left[  n\right]  }a_{i}^{2}\right)  \left(  \sum
_{j\in\left[  n\right]  }b_{j}^{2}\right)  =\underbrace{\sum_{i\in\left[
n\right]  }\ \ \sum_{j\in\left[  n\right]  }}_{=\sum_{\left(  i,j\right)
\in\left[  n\right]  ^{2}}}a_{i}^{2}b_{j}^{2}\\
&  =\sum_{\left(  i,j\right)  \in\left[  n\right]  ^{2}}a_{i}^{2}b_{j}%
^{2}=\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2}%
;\\i<j}}a_{i}^{2}b_{j}^{2}+\underbrace{\sum_{\substack{\left(  i,j\right)
\in\left[  n\right]  ^{2};\\i=j}}}_{=\sum_{j\in\left[  n\right]  }%
\ \ \sum_{\substack{i\in\left[  n\right]  ;\\i=j}}}a_{i}^{2}b_{j}%
^{2}+\underbrace{\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\i>j}}}_{=\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\j<i}}}a_{i}^{2}b_{j}^{2}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{denn jedes Paar }\left(  i,j\right)  \in\left[  n\right]  ^{2}\text{
erf\"{u}llt genau eine}\\
\text{der drei Behauptungen }i<j\text{, }i=j\text{ und }i>j
\end{array}
\right) \\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{i}^{2}b_{j}^{2}+\sum_{j\in\left[  n\right]  }\ \ \underbrace{\sum
_{\substack{i\in\left[  n\right]  ;\\i=j}}a_{i}^{2}b_{j}^{2}}%
_{\substack{=a_{j}^{2}b_{j}^{2}\\\text{(denn diese Summe}\\\text{hat nur einen
Summanden,}\\\text{n\"{a}mlich den f\"{u}r }i=j\text{)}}}+\underbrace{\sum
_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\j<i}}a_{i}%
^{2}b_{j}^{2}}_{\substack{=\sum_{\substack{\left(  j,i\right)  \in\left[
n\right]  ^{2};\\i<j}}a_{j}^{2}b_{i}^{2}\\\text{(hier haben wir den}%
\\\text{Summationsindex }\left(  i,j\right)  \\\text{in }\left(  j,i\right)
\text{ umbenannt)}}}\\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{i}^{2}b_{j}^{2}+\sum_{j\in\left[  n\right]  }a_{j}^{2}b_{j}^{2}%
+\underbrace{\sum_{\substack{\left(  j,i\right)  \in\left[  n\right]
^{2};\\i<j}}}_{\substack{=\sum_{\substack{\left(  i,j\right)  \in\left[
n\right]  ^{2};\\i<j}}\\\text{(denn die Abbildung von }\left[  n\right]
^{2}\text{ nach }\left[  n\right]  ^{2}\text{,}\\\text{die jedes Paar }\left(
i,j\right)  \text{ nach }\left(  j,i\right)  \text{ sendet,}\\\text{ist eine
Bijektion)}}}a_{j}^{2}b_{i}^{2}\\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{i}^{2}b_{j}^{2}+\sum_{j\in\left[  n\right]  }a_{j}^{2}b_{j}^{2}%
+\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{j}^{2}b_{i}^{2}%
\end{align*}
Andererseits ist%
\begin{align*}
&  \left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)  ^{2}\\
&  =\underbrace{\left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)
}_{=\sum_{i\in\left[  n\right]  }a_{i}b_{i}}\underbrace{\left(  a_{1}%
b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)  }_{=\sum_{j\in\left[  n\right]
}a_{j}b_{j}}\\
&  =\left(  \sum_{i\in\left[  n\right]  }a_{i}b_{i}\right)  \left(  \sum
_{j\in\left[  n\right]  }a_{j}b_{j}\right)  =\underbrace{\sum_{i\in\left[
n\right]  }\ \ \sum_{j\in\left[  n\right]  }}_{=\sum_{\left(  i,j\right)
\in\left[  n\right]  ^{2}}}a_{i}b_{i}a_{j}b_{j}\\
&  =\sum_{\left(  i,j\right)  \in\left[  n\right]  ^{2}}a_{i}b_{i}a_{j}%
b_{j}=\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2}%
;\\i<j}}a_{i}b_{i}a_{j}b_{j}+\underbrace{\sum_{\substack{\left(  i,j\right)
\in\left[  n\right]  ^{2};\\i=j}}}_{=\sum_{j\in\left[  n\right]  }%
\ \ \sum_{\substack{i\in\left[  n\right]  ;\\i=j}}}a_{i}b_{i}a_{j}%
b_{j}+\underbrace{\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\i>j}}}_{=\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\j<i}}}a_{i}b_{i}a_{j}b_{j}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{denn jedes Paar }\left(  i,j\right)  \in\left[  n\right]  ^{2}\text{
erf\"{u}llt genau eine}\\
\text{der drei Behauptungen }i<j\text{, }i=j\text{ und }i>j
\end{array}
\right) \\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{i}b_{i}a_{j}b_{j}+\sum_{j\in\left[  n\right]  }\ \ \underbrace{\sum
_{\substack{i\in\left[  n\right]  ;\\i=j}}a_{i}b_{i}a_{j}b_{j}}%
_{\substack{=a_{j}b_{j}a_{j}b_{j}\\\text{(denn diese Summe}\\\text{hat nur
einen Summanden,}\\\text{n\"{a}mlich den f\"{u}r }i=j\text{)}}%
}+\underbrace{\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\j<i}}a_{i}b_{i}a_{j}b_{j}}_{\substack{=\sum_{\substack{\left(
j,i\right)  \in\left[  n\right]  ^{2};\\i<j}}a_{j}b_{j}a_{i}b_{i}\\\text{(hier
haben wir den}\\\text{Summationsindex }\left(  i,j\right)  \\\text{in }\left(
j,i\right)  \text{ umbenannt)}}}\\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{i}b_{i}a_{j}b_{j}+\sum_{j\in\left[  n\right]  }\underbrace{a_{j}b_{j}%
a_{j}b_{j}}_{=a_{j}^{2}b_{j}^{2}}+\underbrace{\sum_{\substack{\left(
j,i\right)  \in\left[  n\right]  ^{2};\\i<j}}}_{\substack{=\sum
_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}}\\\text{(denn
die Abbildung von }\left[  n\right]  ^{2}\text{ nach }\left[  n\right]
^{2}\text{,}\\\text{die jedes Paar }\left(  i,j\right)  \text{ nach }\left(
j,i\right)  \text{ sendet,}\\\text{ist eine Bijektion)}}}a_{j}b_{j}a_{i}%
b_{i}\\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{i}b_{i}a_{j}b_{j}+\sum_{j\in\left[  n\right]  }a_{j}^{2}b_{j}^{2}%
+\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{j}b_{j}a_{i}b_{i}.
\end{align*}
Subtrahieren wir letztere Gleichung von der ersteren, so erhalten wir%
\begin{align*}
&  \left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right)  -\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}\\
&  =\left(  \sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\i<j}}a_{i}^{2}b_{j}^{2}+\sum_{j\in\left[  n\right]  }a_{j}^{2}b_{j}%
^{2}+\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2}%
;\\i<j}}a_{j}^{2}b_{i}^{2}\right) \\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \sum_{\substack{\left(  i,j\right)  \in\left[
n\right]  ^{2};\\i<j}}a_{i}b_{i}a_{j}b_{j}+\sum_{j\in\left[  n\right]  }%
a_{j}^{2}b_{j}^{2}+\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\i<j}}a_{j}b_{j}a_{i}b_{i}\right) \\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}%
}a_{i}^{2}b_{j}^{2}+\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]
^{2};\\i<j}}a_{j}^{2}b_{i}^{2}-\sum_{\substack{\left(  i,j\right)  \in\left[
n\right]  ^{2};\\i<j}}a_{i}b_{i}a_{j}b_{j}-\sum_{\substack{\left(  i,j\right)
\in\left[  n\right]  ^{2};\\i<j}}a_{j}b_{j}a_{i}b_{i}\\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2}%
;\\i<j}}\underbrace{\left(  a_{i}^{2}b_{j}^{2}+a_{j}^{2}b_{i}^{2}-a_{i}%
b_{i}a_{j}b_{j}-a_{j}b_{j}a_{i}b_{i}\right)  }_{\substack{=a_{i}^{2}b_{j}%
^{2}+a_{j}^{2}b_{i}^{2}-2a_{i}b_{j}a_{j}b_{i}\\=\left(  a_{i}b_{j}-a_{j}%
b_{i}\right)  ^{2}}}\\
&  =\sum_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2}%
;\\i<j}}\underbrace{\left(  a_{i}b_{j}-a_{j}b_{i}\right)  ^{2}}%
_{\substack{\geq0\\\text{(nach Satz \ref{thm.xsquare})}}}\geq\sum
_{\substack{\left(  i,j\right)  \in\left[  n\right]  ^{2};\\i<j}}0=0.
\end{align*}
Das hei\ss t,%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]
Damit ist Satz \ref{thm.cs-REPEAT} bewiesen.
\end{proof}

TODO: fortsetzen...

\begin{noncompile}
Anfang eines zweiten Beweises von Satz \ref{thm.cs-REPEAT}:

Zuerst einmal bemerken wir, dass f\"{u}r beliebige vier reelle Zahlen
$u,v,x,y$ die Ungleichung%
\begin{equation}
\left(  u^{2}+v^{2}\right)  \left(  x^{2}+y^{2}\right)  \geq\left(
ux+vy\right)  ^{2} \label{pf.thm.cs-REPEAT.4vars}%
\end{equation}
gilt. In der Tat gilt
\[
\left(  u^{2}+v^{2}\right)  \left(  x^{2}+y^{2}\right)  -\left(  ux+vy\right)
^{2}=\left(  uy-vx\right)  ^{2}\geq0\ \ \ \ \ \ \ \ \ \ \left(  \text{nach
Satz \ref{thm.xsquare}}\right)  .
\]


Nun zeigen wir folgende Ungleichung:%
\begin{align}
&  \sqrt{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}\cdot\sqrt{b_{1}^{2}+b_{2}%
^{2}+\cdots+b_{n}^{2}}\nonumber\\
&  \geq a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}.
\label{pf.thm.cs-REPEAT.2nd.goal1}%
\end{align}
(Die Quadratwurzeln auf der linken Seite sind wohldefiniert, denn die Zahlen
$a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}$ und $b_{1}^{2}+b_{2}^{2}+\cdots
+b_{n}^{2}$ sind (als Summen von Quadraten) nichtnegativ.)
\end{noncompile}

\newpage

\section{Anhang: Die Summe der Minima ist $\leq$ dem Minimum der Summe}

\subsection{Das Prinzip}

Die folgenden Argumente stammen aus dem Kvant-Artikel \cite{AleKur91} von
Alekseev und Kurlyandchik. Ich habe sie von Arthur Engel im IMO-Training ca.
2005 gelernt.

Wir beginnen mit zwei Definitionen:

\begin{definition}
\label{def.sum-func}Sei $I$ eine beliebige Menge. Seien $f,g:I\rightarrow
\mathbb{R}$ zwei Funktionen. Die Funktion $f+g:I\rightarrow\mathbb{R}$ ist
dann definiert als die Funktion von $I$ nach $\mathbb{R}$, die jedes $x\in I$
auf $f\left(  x\right)  +g\left(  x\right)  \in\mathbb{R}$ abbildet.
\end{definition}

\begin{definition}
Sei $I$ eine beliebige Menge. Sei $f:I\rightarrow\mathbb{R}$ eine Funktion.

Unter dem \textit{Minimum} der Funktion $f$ verstehen wir das kleinste Element
der Bildmenge $f\left(  I\right)  =\left\{  f\left(  x\right)  \ \mid\ x\in
I\right\}  $, falls ein solches existiert. Dieses Minimum bezeichnen wir mit
$\min f$.
\end{definition}

\begin{proposition}
\label{prop.sum-min.2}Sei $I$ eine beliebige Menge. Seien $f,g:I\rightarrow
\mathbb{R}$ zwei Funktionen. Angenommen, die Minima $\min f$, $\min g$ und
$\min\left(  f+g\right)  $ existieren. Dann gilt%
\[
\min f+\min g\leq\min\left(  f+g\right)  .
\]

\end{proposition}

\begin{proof}
[Beweis von Proposition \ref{prop.sum-min.2}.]Das Minimum einer Funktion ist
offensichtlich ein Wert dieser Funktion. Somit ist $\min\left(  f+g\right)  $
ein Wert von $f+g$. Es gibt also ein $y\in I$ mit $\min\left(  f+g\right)
=\left(  f+g\right)  \left(  y\right)  $. Betrachten wir dieses $y$. Die
Definition von $f+g$ ergibt $\left(  f+g\right)  \left(  y\right)  =f\left(
y\right)  +g\left(  y\right)  $.

Das Minimum $\min f$ ist $\leq$ als jeder Wert von $f$. Insbesondere gilt also
$\min f\leq f\left(  y\right)  $. Analog gilt $\min g\leq g\left(  y\right)
$. Daher ist%
\[
\underbrace{\min f}_{\leq f\left(  y\right)  }+\underbrace{\min g}_{\leq
g\left(  y\right)  }\leq f\left(  y\right)  +g\left(  y\right)  =\left(
f+g\right)  \left(  y\right)  =\min\left(  f+g\right)  .
\]
Damit ist Proposition \ref{prop.sum-min.2} bewiesen.
\end{proof}

Proposition \ref{prop.sum-min.2} l\"{a}\ss t sich leicht auf beliebig viele
Funktionen verallgemeinern:

\begin{proposition}
\label{prop.sum-min.n}Sei $n\in\mathbb{N}$. Sei $I$ eine beliebige Menge.
Seien $f_{1},f_{2},\ldots,f_{n}:I\rightarrow\mathbb{R}$ beliebige Funktionen.
Angenommen, das Minimum $\min\left(  f_{1}+f_{2}+\cdots+f_{n}\right)  $
existiert, und das Minimum $\min\left(  f_{i}\right)  $ existiert f\"{u}r
jedes $i\in\left\{  1,2,\ldots,n\right\}  $. Dann gilt%
\begin{equation}
\min\left(  f_{1}\right)  +\min\left(  f_{2}\right)  +\cdots+\min\left(
f_{n}\right)  \leq\min\left(  f_{1}+f_{2}+\cdots+f_{n}\right)  .
\label{eq.prop.sum-min.n.eq}%
\end{equation}

\end{proposition}

\begin{proof}
[Beweis von Proposition \ref{prop.sum-min.n}.]Mancheiner w\"{u}rde hier gerne
mit Induktion nach $n$ argumentieren; dies wird jedoch dadurch vereitelt, dass
die Funktionen $f_{1}+f_{2}+\cdots+f_{k}$ f\"{u}r $1<k<n$ nicht
notwendigerweise Minima haben. Daher arbeiten wir uns von vorne durch und
dehnen einfach den obigen Beweis von Proposition \ref{prop.sum-min.2} auf
unsere Verallgemeinerung aus:

Das Minimum einer Funktion ist offensichtlich ein Wert dieser Funktion. Somit
ist $\min\left(  f_{1}+f_{2}+\cdots+f_{n}\right)  $ ein Wert von $f_{1}%
+f_{2}+\cdots+f_{n}$. Es gibt also ein $y\in I$ mit $\min\left(  f_{1}%
+f_{2}+\cdots+f_{n}\right)  =\left(  f_{1}+f_{2}+\cdots+f_{n}\right)  \left(
y\right)  $. Betrachten wir dieses $y$. Die Definition von $f_{1}+f_{2}%
+\cdots+f_{n}$ ergibt
\[
\left(  f_{1}+f_{2}+\cdots+f_{n}\right)  \left(  y\right)  =f_{1}\left(
y\right)  +f_{2}\left(  y\right)  +\cdots+f_{n}\left(  y\right)  .
\]
(Genauer gesagt muss man dies durch Induktion nach $n$ beweisen, denn wir
haben in Definition \ref{def.sum-func} ja nur die Summe $f+g$ von zwei
Funktionen und nicht direkt die Summe $f_{1}+f_{2}+\cdots+f_{n}$ von $n$
Funktionen definiert. Aber der Beweis ist trivial.)

Nun ist%
\begin{align}
&  \min\left(  f_{1}\right)  +\min\left(  f_{2}\right)  +\cdots+\min\left(
f_{n}\right) \nonumber\\
&  =\sum_{i=1}^{n}\underbrace{\min\left(  f_{i}\right)  }_{\substack{\leq
f_{i}\left(  y\right)  \\\text{(denn das Minimum }\min\left(  f_{i}\right)
\text{ von }f_{i}\\\text{ist }\leq\text{ als jeder Wert von }f_{i}\text{)}%
}}\nonumber\\
&  \leq\sum_{i=1}^{n}f_{i}\left(  y\right)  =f_{1}\left(  y\right)
+f_{2}\left(  y\right)  +\cdots+f_{n}\left(  y\right)  =\left(  f_{1}%
+f_{2}+\cdots+f_{n}\right)  \left(  y\right) \nonumber\\
&  =\min\left(  f_{1}+f_{2}+\cdots+f_{n}\right)  .
\label{pf.prop.sum-min.n.calc}%
\end{align}
Damit ist Proposition \ref{prop.sum-min.n} bewiesen.
\end{proof}

\begin{remark}
\label{rmk.sum-min.n.equa}Die Ungleichung (\ref{eq.prop.sum-min.n.eq}) in
Proposition \ref{prop.sum-min.n} wird genau dann zur Gleichheit, wenn es ein
$x\in I$ gibt, welches $f_{i}\left(  x\right)  =\min\left(  f_{i}\right)  $
f\"{u}r alle $i\in\left\{  1,2,\ldots,n\right\}  $ erf\"{u}llt. Dies ist recht
leicht einzusehen: Wenn es ein solches $x$ gibt, dann erf\"{u}llt dieses $x$
auch
\begin{align*}
\min\left(  f_{1}+f_{2}+\cdots+f_{n}\right)   &  \leq\left(  f_{1}%
+f_{2}+\cdots+f_{n}\right)  \left(  x\right) \\
&  =\underbrace{f_{1}\left(  x\right)  }_{=\min\left(  f_{1}\right)
}+\underbrace{f_{2}\left(  x\right)  }_{=\min\left(  f_{2}\right)  }%
+\cdots+\underbrace{f_{n}\left(  x\right)  }_{=\min\left(  f_{n}\right)  }\\
&  =\min\left(  f_{1}\right)  +\min\left(  f_{2}\right)  +\cdots+\min\left(
f_{n}\right)  ,
\end{align*}
und zusammen mit der Ungleichung (\ref{eq.prop.sum-min.n.eq}) f\"{u}hrt dies
auf Gleichheit in (\ref{eq.prop.sum-min.n.eq}). Umgekehrt: Wenn es
\textbf{kein} solches $x$ gibt, dann ist f\"{u}r jedes $y\in I$ mindestens
eine der $n$ Ungleichungen $\min\left(  f_{i}\right)  \leq f_{i}\left(
y\right)  $ (mit $i\in\left\{  1,2,\ldots,n\right\}  $) strikt, und somit kann
das \textquotedblleft$\leq$\textquotedblright-Zeichen in
(\ref{pf.prop.sum-min.n.calc}) durch ein \textquotedblleft$<$%
\textquotedblright-Zeichen ersetzt werden; dies bedeutet, dass in
(\ref{eq.prop.sum-min.n.eq}) keine Gleichheit eintritt.
\end{remark}

\subsection{Cauchy--Schwarz in Engelform (aka Titus Lemma)}

Genug der Allgemeinheiten; um aus obigen Propositionen etwas N\"{u}tzliches zu
erhalten, brauchen wir Funktionen, deren Minima wir tats\"{a}chlich ausrechnen
k\"{o}nnen. Als erstes Beispiel werden wir uns quadratische Funktionen auf
$\mathbb{R}$ dienen. Ihre Minima erhalten wir folgenderma\ss en:

\begin{proposition}
\label{prop.min.quadratic}Seien $a,b$ zwei reelle Zahlen mit $a>0$. Sei
$f_{a,b}:\mathbb{R}\rightarrow\mathbb{R}$ die Funktion, die jedes
$x\in\mathbb{R}$ auf $ax^{2}+2bx$ sendet. Dann existiert das Minimum der
Funktion $f_{a,b}$, und es ist%
\begin{equation}
\min\left(  f_{a,b}\right)  =\dfrac{-b^{2}}{a}.
\label{eq.prop.min.quadratic.min}%
\end{equation}
Das Minimum der Funktion $f_{a,b}$ wird genau an der Stelle $-\dfrac{b}{a}$
erreicht (d.h., die einzige Zahl $x\in\mathbb{R}$ mit $f_{a,b}\left(
x\right)  =\min\left(  f_{a,b}\right)  $ ist $-\dfrac{b}{a}$).
\end{proposition}

\begin{proof}
[Beweis von Proposition \ref{prop.min.quadratic}.]F\"{u}r jedes $x\in
\mathbb{R}$ ist%
\begin{equation}
f_{a,b}\left(  x\right)  =ax^{2}+2bx=a\left(  x+\dfrac{b}{a}\right)
^{2}-\dfrac{b^{2}}{a}. \label{pf.prop.min.quadratic.1}%
\end{equation}
(Die letztere Gleichheit l\"{a}\ss t sich leicht nachrechnen; es handelt sich
aber einfach um die Scheitelform der Parabel $y=ax^{2}+2bx$.)

Aus der Gleichung (\ref{pf.prop.min.quadratic.1}) folgt%
\[
f_{a,b}\left(  x\right)  =a\underbrace{\left(  x+\dfrac{b}{a}\right)  ^{2}%
}_{\substack{\geq0\\\text{(nach Satz \ref{thm.xsquare})}}}-\dfrac{b^{2}}%
{a}\geq-\dfrac{b^{2}}{a}%
\]
(hier haben wir verwendet, dass $a>0$ ist). In dieser Ungleichung tritt
Gleichheit tats\"{a}chlich ein, wenn $x=-\dfrac{b}{a}$ ist (denn dann ist
$x+\dfrac{b}{a}=0$). Somit wissen wir, dass $f_{a,b}\left(  x\right)
\geq-\dfrac{b^{2}}{a}$ gilt, und Gleichheit hier genau dann eintritt, wenn
$x=-\dfrac{b}{a}$ ist. Somit ist $-\dfrac{b^{2}}{a}$ das Minimum der Funktion
$f_{a,b}$, und dieses Minimum wird genau an der Stelle $-\dfrac{b}{a}$
erreicht. Das hei\ss t, das Minimum der Funktion $f_{a,b}$ existiert, und ist
$\min\left(  f_{a,b}\right)  =-\dfrac{b^{2}}{a}=\dfrac{-b^{2}}{a}$, und wird
genau an der Stelle $-\dfrac{b}{a}$ erreicht. Proposition
\ref{prop.min.quadratic} ist damit bewiesen.
\end{proof}

Nun k\"{o}nnen wir Proposition \ref{prop.sum-min.n} auf quadratische
Funktionen anwenden, und erhalten folgendes:

\begin{theorem}
[Cauchy--Schwarz-Ungleichung in Engelform, auch \textquotedblleft Titus
Lemma\textquotedblright\ genannt]\label{thm.cs-engel}Sei $n$ eine positive
ganze Zahl. Seien $a_{1},a_{2},\ldots,a_{n}$ beliebige $n$ positive reelle
Zahlen. Seien $b_{1},b_{2},\ldots,b_{n}$ beliebige $n$ reelle Zahlen. Dann
gilt%
\begin{equation}
\dfrac{b_{1}^{2}}{a_{1}}+\dfrac{b_{2}^{2}}{a_{2}}+\cdots+\dfrac{b_{n}^{2}%
}{a_{n}}\geq\dfrac{\left(  b_{1}+b_{2}+\cdots+b_{n}\right)  ^{2}}{a_{1}%
+a_{2}+\cdots+a_{n}}. \label{eq.thm.cs-engel.eq}%
\end{equation}

\end{theorem}

\begin{proof}
[Beweis von Satz \ref{thm.cs-engel}.]F\"{u}r beliebige zwei reelle Zahlen
$a,b$ definieren wir $f_{a,b}:\mathbb{R}\rightarrow\mathbb{R}$ als die
Funktion, die jedes $x\in\mathbb{R}$ auf $ax^{2}+2bx$ sendet. Laut Proposition
\ref{prop.min.quadratic} hat jede solche Funktion $f_{a,b}$ mit positivem $a$
ein Minimum. Insbesondere haben also die Funktionen $f_{a_{1},b_{1}}$,
$f_{a_{2},b_{2}}$, $\ldots$, $f_{a_{n},b_{n}}$ sowie die Funktion
$f_{a_{1}+a_{2}+\cdots+a_{n},b_{1}+b_{2}+\cdots+b_{n}}$ Minima (denn die
Zahlen $a_{1},a_{2},\ldots,a_{n}$ und somit auch ihre Summe $a_{1}%
+a_{2}+\cdots+a_{n}$ sind positiv). Ferner gilt
\begin{equation}
f_{a_{1}+a_{2}+\cdots+a_{n},b_{1}+b_{2}+\cdots+b_{n}}=f_{a_{1},b_{1}}%
+f_{a_{2},b_{2}}+\cdots+f_{a_{n},b_{n}}, \label{pf.thm.cs-engel.1}%
\end{equation}
denn f\"{u}r jedes $x\in\mathbb{R}$ gilt%
\begin{align*}
&  f_{a_{1}+a_{2}+\cdots+a_{n},b_{1}+b_{2}+\cdots+b_{n}}\left(  x\right) \\
&  =\left(  a_{1}+a_{2}+\cdots+a_{n}\right)  x^{2}+2\left(  b_{1}+b_{2}%
+\cdots+b_{n}\right)  x\\
&  =\underbrace{\left(  a_{1}x^{2}+2b_{1}x\right)  }_{=f_{a_{1},b_{1}}\left(
x\right)  }+\underbrace{\left(  a_{2}x^{2}+2b_{2}x\right)  }_{=f_{a_{2},b_{2}%
}\left(  x\right)  }+\cdots+\underbrace{\left(  a_{n}x^{2}+2b_{n}x\right)
}_{=f_{a_{n},b_{n}}\left(  x\right)  }\\
&  =f_{a_{1},b_{1}}\left(  x\right)  +f_{a_{2},b_{2}}\left(  x\right)
+\cdots+f_{a_{n},b_{n}}\left(  x\right) \\
&  =\left(  f_{a_{1},b_{1}}+f_{a_{2},b_{2}}+\cdots+f_{a_{n},b_{n}}\right)
\left(  x\right)  .
\end{align*}
Proposition \ref{prop.sum-min.n} (angewandt auf $f_{i}=f_{a_{i},b_{i}}$)
ergibt nun
\begin{align*}
&  \min\left(  f_{a_{1},b_{1}}\right)  +\min\left(  f_{a_{2},b_{2}}\right)
+\cdots+\min\left(  f_{a_{n},b_{n}}\right) \\
&  \leq\min\underbrace{\left(  f_{a_{1},b_{1}}+f_{a_{2},b_{2}}+\cdots
+f_{a_{n},b_{n}}\right)  }_{\substack{=f_{a_{1}+a_{2}+\cdots+a_{n},b_{1}%
+b_{2}+\cdots+b_{n}}\\\text{(nach (\ref{pf.thm.cs-engel.1}))}}}\\
&  =\min\left(  f_{a_{1}+a_{2}+\cdots+a_{n},b_{1}+b_{2}+\cdots+b_{n}}\right)
\\
&  =\dfrac{-\left(  b_{1}+b_{2}+\cdots+b_{n}\right)  ^{2}}{a_{1}+a_{2}%
+\cdots+a_{n}}%
\end{align*}
(laut Proposition \ref{eq.prop.min.quadratic.min}, angewandt auf
$a=a_{1}+a_{2}+\cdots+a_{n}$ und $b=b_{1}+b_{2}+\cdots+b_{n}$). Also ist
\begin{align*}
&  \dfrac{-\left(  b_{1}+b_{2}+\cdots+b_{n}\right)  ^{2}}{a_{1}+a_{2}%
+\cdots+a_{n}}\\
&  \geq\min\left(  f_{a_{1},b_{1}}\right)  +\min\left(  f_{a_{2},b_{2}%
}\right)  +\cdots+\min\left(  f_{a_{n},b_{n}}\right) \\
&  =\sum_{k=1}^{n}\underbrace{\min\left(  f_{a_{k},b_{k}}\right)
}_{\substack{=\dfrac{-b_{k}^{2}}{a_{k}}\\\text{(laut Proposition
\ref{eq.prop.min.quadratic.min},}\\\text{angewandt auf }a=a_{k}\text{ und
}b=b_{k}\text{)}}}=\sum_{k=1}^{n}\dfrac{-b_{k}^{2}}{a_{k}}.
\end{align*}
Multiplizieren wir beide Seiten dieser Ungleichung mit $-1$, dann erhalten wir%
\[
\dfrac{\left(  b_{1}+b_{2}+\cdots+b_{n}\right)  ^{2}}{a_{1}+a_{2}+\cdots
+a_{n}}\leq-\sum_{k=1}^{n}\dfrac{-b_{k}^{2}}{a_{k}}=\sum_{k=1}^{n}\dfrac
{b_{k}^{2}}{a_{k}}=\dfrac{b_{1}^{2}}{a_{1}}+\dfrac{b_{2}^{2}}{a_{2}}%
+\cdots+\dfrac{b_{n}^{2}}{a_{n}}.
\]
Damit ist Satz \ref{thm.cs-engel} bewiesen.
\end{proof}

\begin{remark}
Die Ungleichung (\ref{eq.thm.cs-engel.eq}) in Satz \ref{thm.cs-engel} wird
genau dann zur Gleichheit, wenn $\dfrac{b_{1}}{a_{1}}=\dfrac{b_{2}}{a_{2}%
}=\cdots=\dfrac{b_{n}}{a_{n}}$ gilt. Dies kann der Leser nachpr\"{u}fen; dazu
muss er nur die letzte Aussage von Proposition \ref{prop.min.quadratic} mit
der Gleichheitsanalyse in Bemerkung \ref{rmk.sum-min.n.equa} verkn\"{u}pfen.
\end{remark}

Satz \ref{thm.cs-engel} wird \"{o}fters \textit{Titus Lemma} genannt (und von
schreibfaulen IMO-Teilnehmern gerne \textit{T2s Lemma} abgek\"{u}rzt). Die
altbekannte Cauchy--Schwarz-Ungleichung (Satz \ref{thm.cs-REPEAT}) l\"{a}\ss t
sich unschwer aus ihm herleiten:

\begin{proof}
[Zweiter Beweis von Satz \ref{thm.cs-REPEAT}.]\textit{Schritt 1:} Wir nehmen
o. B. d. A. an, dass $n\neq0$ ist (denn sonst l\"{a}uft Satz
\ref{thm.cs-REPEAT} auf $0\geq0$ hinaus).

\textit{Schritt 2:} Nun beweisen wir Satz \ref{thm.cs-REPEAT} in dem Fall,
wenn die Zahlen $a_{1},a_{2},\ldots,a_{n}$ von $0$ verschieden sind.

In der Tat nehmen wir an, dass die Zahlen $a_{1},a_{2},\ldots,a_{n}$ von $0$
verschieden sind. Daher sind ihre Quadrate $a_{1}^{2},a_{2}^{2},\ldots
,a_{n}^{2}$ positiv. Somit k\"{o}nnen wir Satz \ref{thm.cs-engel} auf
$a_{i}^{2}$ und $a_{i}b_{i}$ statt $a_{i}$ und $b_{i}$ anwenden. Dadurch
erhalten wir%
\[
\dfrac{\left(  a_{1}b_{1}\right)  ^{2}}{a_{1}^{2}}+\dfrac{\left(  a_{2}%
b_{2}\right)  ^{2}}{a_{2}^{2}}+\cdots+\dfrac{\left(  a_{n}b_{n}\right)  ^{2}%
}{a_{n}^{2}}\geq\dfrac{\left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)
^{2}}{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}.
\]
Die linke Seite dieser Ungleichung vereinfacht sich aber zu $b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}$. Somit wird die Ungleichung zu%
\[
b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\geq\dfrac{\left(  a_{1}b_{1}+a_{2}%
b_{2}+\cdots+a_{n}b_{n}\right)  ^{2}}{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}.
\]
Multiplizieren wir diese Ungleichung mit der (offensichtlich nichtnegativen)
Zahl $a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}$, so erhalten wir%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]
Damit ist Satz \ref{thm.cs-REPEAT} also bewiesen in dem Fall, wenn die Zahlen
$a_{1},a_{2},\ldots,a_{n}$ von $0$ verschieden sind.

\textit{Schritt 3:} Jetzt beweisen wir Satz \ref{thm.cs-REPEAT} im allgemeinen
Fall. Wir k\"{o}nnen dies auf zwei Wegen tun:

\textit{Erster Weg:} Wir f\"{u}hren ein Stetigkeitsargument durch: In Schritt
2 haben wir bereits gezeigt, dass die Ungleichung%
\begin{align}
&  \left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right) \nonumber\\
&  \geq\left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)  ^{2}
\label{pf.thm.cs-REPEAT.by-min.s3.1}%
\end{align}
gilt, wenn die Zahlen $a_{1},a_{2},\ldots,a_{n}$ von $0$ verschieden sind. Wir
wollen nun zeigen, dass sie auch allgemein gilt (also f\"{u}r beliebige
$a_{1},a_{2},\ldots,a_{n}$).

Seien also $a_{1},a_{2},\ldots,a_{n}$ beliebige reelle Zahlen. F\"{u}r jede
hinreichend kleine reelle Zahl $\varepsilon>0$ sind dann die $n$ Zahlen
$a_{1}+\varepsilon,a_{2}+\varepsilon,\ldots,a_{n}+\varepsilon$ alle von $0$
verschieden (warum?). Somit k\"{o}nnen wir die bereits bewiesene Ungleichung
(\ref{pf.thm.cs-REPEAT.by-min.s3.1}) auf $a_{1}+\varepsilon,a_{2}%
+\varepsilon,\ldots,a_{n}+\varepsilon$ statt $a_{1},a_{2},\ldots,a_{n}$
anwenden (f\"{u}r hinreichend kleine reelle Zahlen $\varepsilon>0$). Wir
erhalten damit%
\begin{align*}
&  \left(  \left(  a_{1}+\varepsilon\right)  ^{2}+\left(  a_{2}+\varepsilon
\right)  ^{2}+\cdots+\left(  a_{n}+\varepsilon\right)  ^{2}\right)  \left(
b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right) \\
&  \geq\left(  \left(  a_{1}+\varepsilon\right)  b_{1}+\left(  a_{2}%
+\varepsilon\right)  b_{2}+\cdots+\left(  a_{n}+\varepsilon\right)
b_{n}\right)  ^{2}%
\end{align*}
f\"{u}r jede hinreichend kleine reelle Zahl $\varepsilon>0$. \"{U}bergang zum
Grenzwert ergibt also%
\begin{align*}
&  \lim\limits_{\varepsilon\rightarrow0}\left(  \left(  \left(  a_{1}%
+\varepsilon\right)  ^{2}+\left(  a_{2}+\varepsilon\right)  ^{2}%
+\cdots+\left(  a_{n}+\varepsilon\right)  ^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \right) \\
&  \geq\lim\limits_{\varepsilon\rightarrow0}\left(  \left(  a_{1}%
+\varepsilon\right)  b_{1}+\left(  a_{2}+\varepsilon\right)  b_{2}%
+\cdots+\left(  a_{n}+\varepsilon\right)  b_{n}\right)  ^{2}.
\end{align*}
Wegen%
\begin{align*}
&  \lim\limits_{\varepsilon\rightarrow0}\left(  \left(  \left(  a_{1}%
+\varepsilon\right)  ^{2}+\left(  a_{2}+\varepsilon\right)  ^{2}%
+\cdots+\left(  a_{n}+\varepsilon\right)  ^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \right) \\
&  =\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right)
\end{align*}
und%
\[
\lim\limits_{\varepsilon\rightarrow0}\left(  \left(  a_{1}+\varepsilon\right)
b_{1}+\left(  a_{2}+\varepsilon\right)  b_{2}+\cdots+\left(  a_{n}%
+\varepsilon\right)  b_{n}\right)  ^{2}=\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}%
\]
vereinfacht sich dies zu%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]
Somit haben wir Satz \ref{thm.cs-REPEAT} auch im allgemeinen Fall
bewiesen.\footnote{Es sei darauf hingewiesen, dass dieses einfache
Grenzwertargument leider einen beachtlichen Nachteil hat: Es sagt nichts
\"{u}ber den Gleichheitsfall aus. In der Tat wird eine strikte Ungleichung der
Form $f\left(  \varepsilon\right)  >g\left(  \varepsilon\right)  $ beim
Grenzwert\"{u}bergang nur zu einer nicht-strikten Ungleichung $\lim
\limits_{\varepsilon\rightarrow0}f\left(  \varepsilon\right)  \geq
\lim\limits_{\varepsilon\rightarrow0}g\left(  \varepsilon\right)  $; dies
macht es unm\"{o}glich, den Gleichheitsfall (wie in Bemerkung
\ref{rmk.eqcases.1}) durch den Beweis nachzuzeichnen.}

\textit{Zweiter Weg:} In Schritt 2 haben wir bereits gezeigt, dass die
Ungleichung%
\begin{align}
&  \left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right) \nonumber\\
&  \geq\left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)  ^{2}
\label{pf.thm.cs-REPEAT.by-min.s3.5}%
\end{align}
gilt, wenn die Zahlen $a_{1},a_{2},\ldots,a_{n}$ von $0$ verschieden sind. Wir
wollen nun zeigen, dass sie auch allgemein gilt (also f\"{u}r beliebige
$a_{1},a_{2},\ldots,a_{n}$).

Seien also $a_{1},a_{2},\ldots,a_{n}$ beliebige reelle Zahlen. Seien
$i_{1},i_{2},\ldots,i_{k}$ (mit $i_{1}<i_{2}<\cdots<i_{k}$) alle diejenigen
Elemente $i\in\left\{  1,2,\ldots,n\right\}  $, die $a_{i}\neq0$ erf\"{u}llen.
Dann ist%
\begin{equation}
a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}=a_{i_{1}}^{2}+a_{i_{2}}^{2}%
+\cdots+a_{i_{k}}^{2} \label{pf.thm.cs-REPEAT.by-min.s3.6a}%
\end{equation}
(denn in der Summe $a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}$ sind alle Summanden
bis auf $a_{i_{1}}^{2},a_{i_{2}}^{2},\ldots,a_{i_{k}}^{2}$ gleich $0$ und
k\"{o}nnen daher weggelassen werden) und%
\begin{equation}
a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}=a_{i_{1}}b_{i_{1}}+a_{i_{2}}b_{i_{2}%
}+\cdots+a_{i_{k}}b_{i_{k}} \label{pf.thm.cs-REPEAT.by-min.s3.6c}%
\end{equation}
(aus \"{a}hnlichen Gr\"{u}nden) und schlie\ss lich%
\begin{equation}
b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\geq b_{i_{1}}^{2}+b_{i_{2}}^{2}%
+\cdots+b_{i_{k}}^{2} \label{pf.thm.cs-REPEAT.by-min.s3.6b}%
\end{equation}
(denn $b_{i_{1}}^{2}+b_{i_{2}}^{2}+\cdots+b_{i_{k}}^{2}$ ist eine Teilsumme
der Summe $b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}^{2}$, und alle in ihr nicht
enthaltenen Summanden sind nach Satz \ref{thm.xsquare} nichtnegativ). Wir
k\"{o}nnen die Gleichung (\ref{pf.thm.cs-REPEAT.by-min.s3.6a}) mit der
Ungleichung (\ref{pf.thm.cs-REPEAT.by-min.s3.6b}) multiplizieren (denn beide
Seiten von (\ref{pf.thm.cs-REPEAT.by-min.s3.6a}) sind als Summen von Quadraten
automatisch nichtnegativ); dadurch erhalten wir%
\begin{align}
&  \left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right) \nonumber\\
&  \geq\left(  a_{i_{1}}^{2}+a_{i_{2}}^{2}+\cdots+a_{i_{k}}^{2}\right)
\left(  b_{i_{1}}^{2}+b_{i_{2}}^{2}+\cdots+b_{i_{k}}^{2}\right)  .
\label{pf.thm.cs-REPEAT.by-min.s3.7}%
\end{align}
Doch die Zahlen $a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}$ sind von $0$
verschieden (denn laut Definition von $i_{1},i_{2},\ldots,i_{k}$ gilt
$a_{i}\neq0$ f\"{u}r jedes $i\in\left\{  i_{1},i_{2},\ldots,i_{k}\right\}  $).
Daher k\"{o}nnen wir (\ref{pf.thm.cs-REPEAT.by-min.s3.5}) auf $k$, $\left(
a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\right)  $ und $\left(  b_{i_{1}}%
,b_{i_{2}},\ldots,b_{i_{k}}\right)  $ statt $n$, $\left(  a_{1},a_{2}%
,\ldots,a_{n}\right)  $ und $\left(  b_{1},b_{2},\ldots,b_{n}\right)  $
anwenden. Wir erhalten somit%
\begin{align}
&  \left(  a_{i_{1}}^{2}+a_{i_{2}}^{2}+\cdots+a_{i_{k}}^{2}\right)  \left(
b_{i_{1}}^{2}+b_{i_{2}}^{2}+\cdots+b_{i_{k}}^{2}\right) \nonumber\\
&  \geq a_{i_{1}}b_{i_{1}}+a_{i_{2}}b_{i_{2}}+\cdots+a_{i_{k}}b_{i_{k}}.
\label{pf.thm.cs-REPEAT.by-min.s3.8}%
\end{align}
Aus (\ref{pf.thm.cs-REPEAT.by-min.s3.7}) wird daher%
\begin{align*}
&  \left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right) \\
&  \geq\left(  a_{i_{1}}^{2}+a_{i_{2}}^{2}+\cdots+a_{i_{k}}^{2}\right)
\left(  b_{i_{1}}^{2}+b_{i_{2}}^{2}+\cdots+b_{i_{k}}^{2}\right) \\
&  \geq a_{i_{1}}b_{i_{1}}+a_{i_{2}}b_{i_{2}}+\cdots+a_{i_{k}}b_{i_{k}%
}\ \ \ \ \ \ \ \ \ \ \left(  \text{wegen (\ref{pf.thm.cs-REPEAT.by-min.s3.8}%
)}\right) \\
&  =a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\ \ \ \ \ \ \ \ \ \ \left(
\text{wegen (\ref{pf.thm.cs-REPEAT.by-min.s3.6c})}\right)  .
\end{align*}
Somit haben wir Satz \ref{thm.cs-REPEAT} auch im allgemeinen Fall bewiesen.
\end{proof}

Auch die H\"{o}lder-Ungleichung (Satz \ref{thm.holder}) l\"{a}\ss t sich aus
Proposition \ref{prop.sum-min.n} herleiten (\cite{AleKur91}):

\begin{exercise}
Beweise Satz \ref{thm.holder} mithilfe von Proposition \ref{prop.sum-min.n}.

[\textbf{Hinweis:} Sei $\mathbb{R}_{+}:=\left\{  z\in\mathbb{R}\ \mid
\ z\geq0\right\}  $. Sei $I$ die Menge aller Paare $\left(  x,y\right)
\in\mathbb{R}_{+}^{2}$ mit $xy=1$. (Dies ist ein Ast der Standardhyperbel
$xy=1$.) F\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $ sei
$f_{i}:I\rightarrow\mathbb{R}$ die Funktion, die jedes Paar $\left(
x,y\right)  \in I$ auf $\dfrac{a_{i}^{p}x^{p}}{p}+\dfrac{b_{i}^{q}y^{q}}{q}$
abbildet. Zeige mithilfe der Young--Ungleichung, dass $\min\left(
f_{i}\right)  =a_{i}b_{i}$ ist. Was ist $\min\left(  f_{1}+f_{2}+\cdots
+f_{n}\right)  $, und was folgt hieraus nach Proposition \ref{prop.sum-min.n}?]
\end{exercise}

Hier noch ein paar weitere Aufgaben:

\begin{exercise}
Verallgemeinere Proposition \ref{prop.sum-min.n} durch Ersetzen von Minima
durch Infima.

(Einige Details: Ist $S$ eine Menge von reellen Zahlen, dann ist das
\textit{Infimum} von $S$ definiert als die gr\"{o}\ss te reelle Zahl, die
kleiner oder gleich allen Elementen von $S$ ist (falls eine solche Zahl denn
existiert). Dieses Infimum wird mit $\inf S$ bezeichnet. Beispielsweise ist
$\inf\left\{  \dfrac{1}{1},\dfrac{1}{2},\dfrac{1}{3},\ldots\right\}  =0$.
Unter dem \textit{Infimum} einer Funktion $f:I\rightarrow\mathbb{R}$ verstehen
wir das Infimum der Bildmenge $f\left(  I\right)  =\left\{  f\left(  x\right)
\ \mid\ x\in I\right\}  $, falls ein solches existiert. Dieses Infimum
bezeichnen wir mit $\inf f$. Nun soll Proposition \ref{prop.sum-min.n}
verallgemeinert werden, indem jedes Vorkommen von \textquotedblleft
Minimum\textquotedblright\ oder \textquotedblleft$\min$\textquotedblright%
\ durch \textquotedblleft Infimum\textquotedblright\ bzw. \textquotedblleft%
$\inf$\textquotedblright\ ersetzt wird.)
\end{exercise}

\begin{noncompile}
The AoPS thread: https://artofproblemsolving.com/community/c6h15125p107331 .
\end{noncompile}

\newpage

\section{L\"{o}sungen und L\"{o}sungshinweise}

Im Folgenden zeige ich L\"{o}sungen zu den oben gestellten Aufgaben.

\subsection{zu Kapitel \ref{chp.AM-GM}}

\subsubsection{zu Aufgabe \ref{exe.piab-logconc}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.piab-logconc}.]\textbf{(a)} Wir haben%
\[
2\left(  a^{2}+b^{2}\right)  =a^{2}+b^{2}+\underbrace{\left(  a^{2}%
+b^{2}\right)  }_{\substack{\geq2ab\\\text{(nach Satz \ref{thm.2ab}
\textbf{(a)})}}}\geq a^{2}+b^{2}+2ab=\left(  a+b\right)  ^{2}.
\]
Damit ist Aufgabe \ref{exe.piab-logconc} \textbf{(a)} gel\"{o}st.

\textbf{(b)} Wir nehmen an, dass $ab\geq0$ ist oder $m$ ungerade ist. Dann ist
also $\left(  ab\right)  ^{m-1}\geq0$ (denn wenn $ab\geq0$ ist, dann ist dies
offensichtlich; sonst ist aber $m$ ungerade, und somit $m-1$ gerade, und daher
gilt wieder $\left(  ab\right)  ^{m-1}\geq0$).

Nach Satz \ref{thm.2ab} \textbf{(a)} gilt aber $a^{2}+b^{2}\geq2ab$.
Multiplizieren wir beide Seiten dieser Ungleichung mit $\left(  ab\right)
^{m-1}$, so erhalten wir%
\begin{align}
\left(  ab\right)  ^{m-1}\left(  a^{2}+b^{2}\right)   &  \geq\left(
ab\right)  ^{m-1}\cdot2ab\ \ \ \ \ \ \ \ \ \ \left(  \text{denn }\left(
ab\right)  ^{m-1}\geq0\right) \nonumber\\
&  =2\underbrace{\left(  ab\right)  ^{m-1}ab}_{=\left(  ab\right)  ^{m}%
=a^{m}b^{m}}=2a^{m}b^{m}. \label{sol.piab-logconc.b.1}%
\end{align}


Wir haben $p_{m+1}=a^{m+1}+b^{m+1}$ (nach Definition von $p_{m+1}$) und
$p_{m-1}=a^{m-1}+b^{m-1}$ (analog). Multiplizieren wir diese zwei Gleichungen,
so erhalten wir%
\begin{align*}
p_{m+1}p_{m-1}  &  =\left(  a^{m+1}+b^{m+1}\right)  \left(  a^{m-1}%
+b^{m-1}\right) \\
&  =\underbrace{a^{m+1}a^{m-1}}_{=a^{2m}}+\underbrace{a^{m+1}b^{m-1}%
}_{=\left(  ab\right)  ^{m-1}a^{2}}+\underbrace{a^{m-1}b^{m+1}}_{=\left(
ab\right)  ^{m-1}b^{2}}+\underbrace{b^{m+1}b^{m-1}}_{=b^{2m}}\\
&  =\underbrace{a^{2m}}_{=\left(  a^{m}\right)  ^{2}}+\underbrace{\left(
ab\right)  ^{m-1}a^{2}+\left(  ab\right)  ^{m-1}b^{2}}_{\substack{=\left(
ab\right)  ^{m-1}\left(  a^{2}+b^{2}\right)  \\\geq2a^{m}b^{m}\\\text{(nach
(\ref{sol.piab-logconc.b.1}))}}}+\underbrace{b^{2m}}_{=\left(  b^{m}\right)
^{2}}\\
&  \geq\left(  a^{m}\right)  ^{2}+2a^{m}b^{m}+\left(  b^{m}\right)
^{2}=\left(  a^{m}+b^{m}\right)  ^{2}=p_{m}^{2}%
\end{align*}
(denn die Definition von $p_{m}$ ergibt $p_{m}=a^{m}+b^{m}$). Damit ist
Aufgabe \ref{exe.piab-logconc} \textbf{(b)} gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.3(aa+bb+cc)}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.3(aa+bb+cc)}.]\textbf{(a)} Eine einfache
Rechnung ergibt%
\begin{align*}
&  3\left(  a^{2}+b^{2}+c^{2}\right)  -\left(  \left(  b-c\right)
^{2}+\left(  c-a\right)  ^{2}+\left(  a-b\right)  ^{2}\right) \\
&  =a^{2}+b^{2}+c^{2}+2ab+2ac+2bc=\left(  a+b+c\right)  ^{2}\geq0
\end{align*}
(nach Satz \ref{thm.xsquare}, angewandt auf $x=a+b+c$). Hieraus folgt
$3\left(  a^{2}+b^{2}+c^{2}\right)  \geq\left(  \left(  b-c\right)
^{2}+\left(  c-a\right)  ^{2}+\left(  a-b\right)  ^{2}\right)  $. Dadurch ist
Aufgabe \ref{exe.3(aa+bb+cc)} \textbf{(a)} gel\"{o}st.

\textbf{(b)} Beispiel \ref{exa.aa+bb+cc} (angewendet auf $bc,ca,ab$ statt
$a,b,c$) ergibt%
\[
\left(  bc\right)  ^{2}+\left(  ca\right)  ^{2}+\left(  ab\right)  ^{2}\geq
ca\cdot ab+ab\cdot bc+bc\cdot ca.
\]
Nun ist%
\begin{align*}
b^{2}c^{2}+c^{2}a^{2}+a^{2}b^{2}  &  =\left(  bc\right)  ^{2}+\left(
ca\right)  ^{2}+\left(  ab\right)  ^{2}\geq ca\cdot ab+ab\cdot bc+bc\cdot ca\\
&  =a^{2}bc+ab^{2}c+abc^{2}=abc\left(  a+b+c\right)  .
\end{align*}
Dadurch ist Aufgabe \ref{exe.3(aa+bb+cc)} \textbf{(b)} gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.1/2(a+b+c+d)sq}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.1/2(a+b+c+d)sq}.]\textbf{(a)} Eine kurze
Rechnung ergibt
\begin{align*}
&  \dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}-\left(  \left(  a+c\right)
\left(  b+d\right)  +2\left(  ac+bd\right)  \right) \\
&  =\dfrac{1}{2}\left(  \underbrace{a^{2}+c^{2}}_{\substack{\geq
2ac\\\text{(nach Satz \ref{thm.2ab},}\\\text{angewandt auf }c\text{ statt
}a\text{)}}}+\underbrace{b^{2}+d^{2}}_{\substack{\geq2bd\\\text{(nach Satz
\ref{thm.2ab},}\\\text{angewandt auf }b\text{ und }d\\\text{statt }a\text{ und
}b\text{)}}}\right)  -ac-bd\\
&  \geq\dfrac{1}{2}\left(  2ac+2bd\right)  -ac-bd=0.
\end{align*}
Also ist $\dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}\geq\left(  a+c\right)
\left(  b+d\right)  +2\left(  ac+bd\right)  $. Damit ist Aufgabe
\ref{exe.1/2(a+b+c+d)sq} \textbf{(a)} gel\"{o}st.

\textbf{(b)} \textit{Erste L\"{o}sung zu Aufgabe \ref{exe.1/2(a+b+c+d)sq}
\textbf{(b)}:} Aufgabe \ref{exe.1/2(a+b+c+d)sq} \textbf{(a)} ergibt
\begin{equation}
\dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}\geq\left(  a+c\right)  \left(
b+d\right)  +2\left(  ac+bd\right)  . \label{sol.1/2(a+b+c+d)sq.b.1}%
\end{equation}
Allerdings gilt auch%
\begin{align}
\dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}  &  =\dfrac{1}{2}\left(
a+c+b+d\right)  ^{2}\nonumber\\
&  \geq\left(  a+b\right)  \left(  c+d\right)  +2\left(  ab+cd\right)
\label{sol.1/2(a+b+c+d)sq.b.2}%
\end{align}
(laut Aufgabe \ref{exe.1/2(a+b+c+d)sq} \textbf{(a)}, angewandt auf $c$ und $b$
statt $b$ und $c$) und%
\begin{align}
\dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}  &  =\dfrac{1}{2}\left(
a+b+d+c\right)  ^{2}\nonumber\\
&  \geq\left(  a+d\right)  \left(  b+c\right)  +2\left(  ad+bc\right)
\label{sol.1/2(a+b+c+d)sq.b.3}%
\end{align}
(laut Aufgabe \ref{exe.1/2(a+b+c+d)sq} \textbf{(a)}, angewandt auf $d$ und $c$
statt $c$ und $d$).

Nun wollen wir die drei Ungleichungen (\ref{sol.1/2(a+b+c+d)sq.b.1}),
(\ref{sol.1/2(a+b+c+d)sq.b.2}) und (\ref{sol.1/2(a+b+c+d)sq.b.3})
zusammenaddieren. Wir erhalten auf diese Weise%
\begin{align*}
&  \dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}+\dfrac{1}{2}\left(
a+b+c+d\right)  ^{2}+\dfrac{1}{2}\left(  a+b+c+d\right)  ^{2}\\
&  \geq\left(  \left(  a+c\right)  \left(  b+d\right)  +2\left(  ac+bd\right)
\right)  +\left(  \left(  a+b\right)  \left(  c+d\right)  +2\left(
ab+cd\right)  \right) \\
&  \ \ \ \ \ \ \ \ \ \ +\left(  \left(  a+d\right)  \left(  b+c\right)
+2\left(  ad+bc\right)  \right)  .
\end{align*}
Diese Ungleichung vereinfacht sich schnell zu
\[
\dfrac{3}{2}\left(  a+b+c+d\right)  ^{2}\geq4\left(  ab+ac+ad+bc+bd+cd\right)
\]
(denn ihre linke Seite ist $\dfrac{3}{2}\left(  a+b+c+d\right)  ^{2}$, und
ihre rechte Seite ist \newline$4\left(  ab+ac+ad+bc+bd+cd\right)  $).
Multiplizieren wir beide Seiten mit $2$, so erhalten wir schlie\ss lich%
\[
3\left(  a+b+c+d\right)  ^{2}\geq8\left(  ab+ac+ad+bc+bd+cd\right)  .
\]
Damit ist Aufgabe \ref{exe.1/2(a+b+c+d)sq} \textbf{(b)} gel\"{o}st.

\textit{Zweite L\"{o}sung zu Aufgabe \ref{exe.1/2(a+b+c+d)sq} \textbf{(b)}:}
Eine kurze Rechnung zeigt%
\begin{align*}
&  3\left(  a+b+c+d\right)  ^{2}-8\left(  ab+ac+ad+bc+bd+cd\right) \\
&  =\underbrace{\left(  a-b\right)  ^{2}}_{\substack{\geq0\\\text{(nach Satz
\ref{thm.xsquare})}}}+\underbrace{\left(  a-c\right)  ^{2}}_{\substack{\geq
0\\\text{(nach Satz \ref{thm.xsquare})}}}+\underbrace{\left(  a-d\right)
^{2}}_{\substack{\geq0\\\text{(nach Satz \ref{thm.xsquare})}}%
}+\underbrace{\left(  b-c\right)  ^{2}}_{\substack{\geq0\\\text{(nach Satz
\ref{thm.xsquare})}}}+\underbrace{\left(  b-d\right)  ^{2}}_{\substack{\geq
0\\\text{(nach Satz \ref{thm.xsquare})}}}+\underbrace{\left(  c-d\right)
^{2}}_{\substack{\geq0\\\text{(nach Satz \ref{thm.xsquare})}}}\\
&  \geq0,
\end{align*}
also $3\left(  a+b+c+d\right)  ^{2}\geq8\left(  ab+ac+ad+bc+bd+cd\right)  $.
Damit ist Aufgabe \ref{exe.1/2(a+b+c+d)sq} \textbf{(b)} gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.nesbitt-n}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.nesbitt-n}.]Wir \"{a}ffen im Wesentlichen
unseren Beweis von Beispiel \ref{exa.nesbitt-3} nach. Wir setzen also%
\begin{equation}
x_{i}=a_{1}+a_{2}+\cdots+a_{i-1}+a_{i+1}+\cdots+a_{n}
\label{sol.exe.nesbitt-n.xi=}%
\end{equation}
f\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $. Damit haben wir $n$
positive reelle Zahlen $x_{1},x_{2},\ldots,x_{n}$ definiert. Ferner setzen wir%
\begin{equation}
s=a_{1}+a_{2}+\cdots+a_{n}. \label{sol.exe.nesbitt-n.s=}%
\end{equation}


F\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $ gilt also%
\begin{align*}
s  &  =a_{1}+a_{2}+\cdots+a_{n}=\underbrace{\left(  a_{1}+a_{2}+\cdots
+a_{i-1}+a_{i+1}+\cdots+a_{n}\right)  }_{\substack{=x_{i}\\\text{(nach
(\ref{sol.exe.nesbitt-n.xi=}))}}}+a_{i}\\
&  =x_{i}+a_{i}%
\end{align*}
und damit%
\begin{equation}
a_{i}=s-x_{i}. \label{sol.exe.nesbitt-n.ai=s-xi}%
\end{equation}


Weiterhin ist%
\[
a_{1}+a_{2}+\cdots+a_{n}=\sum_{i=1}^{n}\underbrace{a_{i}}_{\substack{=s-x_{i}%
\\\text{(nach (\ref{sol.exe.nesbitt-n.ai=s-xi}))}}}=\sum_{i=1}^{n}\left(
s-x_{i}\right)  =\underbrace{\sum_{i=1}^{n}s}_{=ns}-\underbrace{\sum_{i=1}%
^{n}x_{i}}_{=\sum_{j=1}^{n}x_{j}}=ns-\sum_{j=1}^{n}x_{j}.
\]
Aus (\ref{sol.exe.nesbitt-n.s=}) folgt also%
\[
s=a_{1}+a_{2}+\cdots+a_{n}=ns-\sum_{j=1}^{n}x_{j}.
\]
Daher ist%
\[
\sum_{j=1}^{n}x_{j}=ns-s=\left(  n-1\right)  s.
\]
Wir k\"{o}nnen diese Gleichung nach $s$ aufl\"{o}sen (denn $n\geq2>1$ und
damit $n-1\neq0$), und erhalten%
\begin{equation}
s=\dfrac{1}{n-1}\sum_{j=1}^{n}x_{j}. \label{sol.exe.nesbitt-n.s-via-x}%
\end{equation}


F\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $ gilt nun%
\[
\dfrac{a_{i}}{x_{i}}=\dfrac{a_{i}}{a_{1}+a_{2}+\cdots+a_{i-1}+a_{i+1}%
+\cdots+a_{n}}\ \ \ \ \ \ \ \ \ \ \left(  \text{nach
(\ref{sol.exe.nesbitt-n.xi=})}\right)
\]
und damit%
\begin{align}
&  \dfrac{a_{i}}{a_{1}+a_{2}+\cdots+a_{i-1}+a_{i+1}+\cdots+a_{n}}\nonumber\\
&  =\dfrac{a_{i}}{x_{i}}=\dfrac{s-x_{i}}{x_{i}}\ \ \ \ \ \ \ \ \ \ \left(
\text{nach (\ref{sol.exe.nesbitt-n.ai=s-xi})}\right) \nonumber\\
&  =\dfrac{s}{x_{i}}-1=s\cdot\dfrac{1}{x_{i}}-1=\left(  \dfrac{1}{n-1}%
\sum_{j=1}^{n}x_{j}\right)  \cdot\dfrac{1}{x_{i}}-1\ \ \ \ \ \ \ \ \ \ \left(
\text{nach (\ref{sol.exe.nesbitt-n.s-via-x})}\right) \nonumber\\
&  =\dfrac{1}{n-1}\sum_{j=1}^{n}\underbrace{x_{j}\cdot\dfrac{1}{x_{i}}%
}_{=\dfrac{x_{j}}{x_{i}}}-1=\dfrac{1}{n-1}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}%
}-1. \label{sol.exe.nesbitt-n.4}%
\end{align}


Nun ist%
\begin{align}
&  \sum_{i=1}^{n}\underbrace{\dfrac{a_{i}}{a_{1}+a_{2}+\cdots+a_{i-1}%
+a_{i+1}+\cdots+a_{n}}}_{\substack{=\dfrac{1}{n-1}\sum_{j=1}^{n}\dfrac{x_{j}%
}{x_{i}}-1\\\text{(by (\ref{sol.exe.nesbitt-n.4}))}}}\nonumber\\
&  =\sum_{i=1}^{n}\left(  \dfrac{1}{n-1}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}%
}-1\right)  =\dfrac{1}{n-1}\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}%
}-\underbrace{\sum_{i=1}^{n}1}_{=n}\nonumber\\
&  =\dfrac{1}{n-1}\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}}-n.
\label{sol.exe.nesbitt-n.6}%
\end{align}


Nun werden wir zeigen, dass
\begin{equation}
\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}}\geq n^{2}
\label{sol.exe.nesbitt-n.7}%
\end{equation}
gilt. Dazu wenden wir den \textquotedblleft Kleiner-Gauss\textquotedblright%
-Trick an: Wir haben%
\begin{align}
2\cdot\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}}  &  =\underbrace{\sum
_{i=1}^{n}\sum_{j=1}^{n}}_{=\sum_{j=1}^{n}\sum_{i=1}^{n}}\dfrac{x_{j}}{x_{i}%
}+\underbrace{\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}}}%
_{\substack{=\sum_{j=1}^{n}\sum_{i=1}^{n}\dfrac{x_{i}}{x_{j}}\\\text{(hier
haben wir die}\\\text{Summationsindizes }i\text{ und }j\\\text{in }j\text{ und
}i\text{ unbenannt)}}}\nonumber\\
&  =\sum_{j=1}^{n}\sum_{i=1}^{n}\dfrac{x_{j}}{x_{i}}+\sum_{j=1}^{n}\sum
_{i=1}^{n}\dfrac{x_{i}}{x_{j}}\nonumber\\
&  =\sum_{j=1}^{n}\sum_{i=1}^{n}\left(  \dfrac{x_{j}}{x_{i}}+\dfrac{x_{i}%
}{x_{j}}\right)  . \label{sol.exe.nesbitt-n.8}%
\end{align}
Doch $x_{1},x_{2},\ldots,x_{n}$ sind positive reelle Zahlen. F\"{u}r beliebige
Elemente $i$ und $j$ von $\left\{  1,2,\ldots,n\right\}  $ gilt also%
\begin{equation}
\dfrac{x_{j}}{x_{i}}+\dfrac{x_{i}}{x_{j}}\geq2 \label{sol.exe.nesbitt-n.9}%
\end{equation}
(nach Satz \ref{thm.2ab} \textbf{(d)}, angewandt auf $a=x_{j}$ und $b=x_{i}$).
Somit wird (\ref{sol.exe.nesbitt-n.8}) zu%
\[
2\cdot\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}}=\sum_{j=1}^{n}%
\sum_{i=1}^{n}\underbrace{\left(  \dfrac{x_{j}}{x_{i}}+\dfrac{x_{i}}{x_{j}%
}\right)  }_{\substack{\geq2\\\text{(nach (\ref{sol.exe.nesbitt-n.9}))}}%
}\geq\sum_{j=1}^{n}\underbrace{\sum_{i=1}^{n}2}_{=n\cdot2=2n}=\sum_{j=1}%
^{n}2n=n\cdot2n=2n^{2}.
\]
Dividieren wir diese Ungleichung durch $2$, so erhalten wir%
\begin{equation}
\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}}{x_{i}}\geq n^{2}.
\label{sol.exe.nesbitt-n.10}%
\end{equation}
Damit wird (\ref{sol.exe.nesbitt-n.6}) zu%
\begin{align*}
&  \sum_{i=1}^{n}\dfrac{a_{i}}{a_{1}+a_{2}+\cdots+a_{i-1}+a_{i+1}+\cdots
+a_{n}}=\dfrac{1}{n-1}\underbrace{\sum_{i=1}^{n}\sum_{j=1}^{n}\dfrac{x_{j}%
}{x_{i}}}_{\substack{\geq n^{2}\\\text{(nach (\ref{sol.exe.nesbitt-n.10}))}%
}}-n\\
&  \geq\dfrac{1}{n-1}n^{2}-n\ \ \ \ \ \ \ \ \ \ \left(  \text{denn }\dfrac
{1}{n-1}\geq0\right) \\
&  =\dfrac{n}{n-1}.
\end{align*}
Damit ist Aufgabe \ref{exe.nesbitt-n} gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.cs.proof-by-amgm}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.cs.proof-by-amgm}.]Wir wollen Satz
\ref{thm.cs} beweisen. Sei dazu $n\in\mathbb{N}$ beliebig, und seien
$a_{1},a_{2},\ldots,a_{n}$ sowie $b_{1},b_{2},\ldots,b_{n}$ beliebige reelle Zahlen.

Wir definieren zwei nichtnegative reelle Zahlen
\[
A=\sqrt{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}\ \ \ \ \ \ \ \ \ \ \text{und}%
\ \ \ \ \ \ \ \ \ \ B=\sqrt{b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}^{2}}.
\]
(Diese zwei Quadratwurzeln sind wohldefiniert, denn wegen Satz
\ref{thm.xsquare} sind $a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}$ und $b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}$ nichtnegativ.) Nach der Definition von $A$
gilt $A^{2}=a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}=\sum_{i=1}^{n}a_{i}^{2}$.
Nach der Definition von $B$ gilt $B^{2}=b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}%
^{2}=\sum_{i=1}^{n}b_{i}^{2}$. Nun ist%
\begin{align}
&  2A^{2}B^{2}\nonumber\\
&  =\underbrace{A^{2}}_{=\sum_{i=1}^{n}a_{i}^{2}}B^{2}+\underbrace{B^{2}%
}_{=\sum_{i=1}^{n}b_{i}^{2}}A^{2}=\sum_{i=1}^{n}a_{i}^{2}B^{2}+\sum_{i=1}%
^{n}b_{i}^{2}A^{2}=\sum_{i=1}^{n}\left(  \underbrace{a_{i}^{2}B^{2}}_{=\left(
a_{i}B\right)  ^{2}}+\underbrace{b_{i}^{2}A^{2}}_{=\left(  b_{i}A\right)
^{2}}\right) \nonumber\\
&  =\sum_{i=1}^{n}\underbrace{\left(  \left(  a_{i}B\right)  ^{2}+\left(
b_{i}A\right)  ^{2}\right)  }_{\substack{\geq2a_{i}Bb_{i}A\\\text{(nach Satz
\ref{thm.2ab} \textbf{(a)},}\\\text{angewandt auf }a_{i}B\text{ und }%
b_{i}A\\\text{statt }a\text{ und }b\text{)}}}\geq\sum_{i=1}^{n}%
\underbrace{2a_{i}Bb_{i}A}_{=2ABa_{i}b_{i}}=\sum_{i=1}^{n}2ABa_{i}%
b_{i}=2AB\sum_{i=1}^{n}a_{i}b_{i}.\nonumber
\end{align}
Dividieren wir diese Ungleichung durch $2$, so erhalten wir%
\begin{equation}
A^{2}B^{2}\geq AB\sum_{i=1}^{n}a_{i}b_{i}. \label{sol.cs.proof-by-amgm.1}%
\end{equation}


Nun w\"{a}re es gut, wenn wir diese Ungleichung durch $AB$ teilen und
quadrieren k\"{o}nnten. Leider ist dies beides nicht ganz einfach: Die
Division kann schieflaufen, wenn $AB=0$ ist, und das Quadrieren k\"{o}nnte
theoretisch die Ungleichung verletzen, wenn die rechte Seite negativ ist.
Diese beiden Hindernisse werden wir nun umschiffen.

Dazu fassen wir erst einmal als Lemma zusammen, was wir bereits gezeigt haben:

\begin{lemma}
\label{lem.sol.cs.proof-by-amgm.lem}Sei $n\in\mathbb{N}$. Seien $a_{1}%
,a_{2},\ldots,a_{n}$ sowie $b_{1},b_{2},\ldots,b_{n}$ beliebige reelle Zahlen.
Seien $A=\sqrt{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}$ und $B=\sqrt{b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}}$. Dann gilt%
\[
A^{2}B^{2}\geq AB\sum_{i=1}^{n}a_{i}b_{i}.
\]

\end{lemma}

Hieraus erhalten wir unschwer folgenden Sonderfall von Satz \ref{thm.cs}:

\begin{lemma}
\label{lem.sol.cs.proof-by-amgm.lem2}Sei $n\in\mathbb{N}$. Seien $a_{1}%
,a_{2},\ldots,a_{n}$ sowie $b_{1},b_{2},\ldots,b_{n}$ beliebige reelle Zahlen.
Angenommen, es gilt $\sum_{i=1}^{n}a_{i}b_{i}>0$. Dann ist%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]

\end{lemma}

\begin{proof}
[Beweis von Lemma \ref{lem.sol.cs.proof-by-amgm.lem2}.]Wir definieren zwei
nichtnegative reelle Zahlen
\[
A=\sqrt{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}\ \ \ \ \ \ \ \ \ \ \text{und}%
\ \ \ \ \ \ \ \ \ \ B=\sqrt{b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}^{2}}.
\]
(Wie schon oben gezeigt, sind diese beiden Quadratwurzeln wohldefiniert.) Laut
Annahme ist $\sum_{i=1}^{n}a_{i}b_{i}>0$. Also sind \textbf{nicht} alle $n$
Zahlen $a_{1},a_{2},\ldots,a_{n}$ gleich $0$ (denn sonst w\"{a}re $a_{i}=0$
f\"{u}r jedes $i\in\left\{  1,2,\ldots,n\right\}  $, woraus wir $\sum
_{i=1}^{n}\underbrace{a_{i}}_{=0}b_{i}=\sum_{i=1}^{n}0b_{i}=0$ erhalten
w\"{u}rden, was im Widerspruch zu $\sum_{i=1}^{n}a_{i}b_{i}>0$ st\"{u}nde).
Folglich ist $A$ positiv\footnote{\textit{Beweis:} Die $n$ Zahlen $a_{1}%
,a_{2},\ldots,a_{n}$ sind reell, und (laut einer der zwei Annahmen, die wir
gerade gemacht haben) nicht alle gleich $0$. Ihre Quadrate $a_{1}^{2}%
,a_{2}^{2},\ldots,a_{n}^{2}$ sind somit nichtnegativ (nach Satz
\ref{thm.xsquare}), und nicht alle gleich $0$. Die Summe $a_{1}^{2}+a_{2}%
^{2}+\cdots+a_{n}^{2}$ dieser Quadrate ist also positiv (denn die Summanden
dieser Summe sind nichtnegativ und nicht alle gleich $0$; daher ist mindestens
einer der Summanden positiv). Somit ist auch ihre Quadratwurzel $\sqrt
{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}$ positiv. Das hei\ss t, $A$ ist positiv
(denn $A=\sqrt{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}$).}. Aus analogen
Gr\"{u}nden ist $B$ positiv. Somit ist auch das Produkt $AB$ positiv. Nach
Lemma \ref{lem.sol.cs.proof-by-amgm.lem} gilt aber%
\[
A^{2}B^{2}\geq AB\sum_{i=1}^{n}a_{i}b_{i}.
\]
Wir k\"{o}nnen diese Ungleichung durch $AB$ dividieren (denn $AB$ ist
positiv), und erhalten%
\[
AB\geq\sum_{i=1}^{n}a_{i}b_{i}.
\]
Wegen $AB>0$ (denn $AB$ ist positiv) und $\sum_{i=1}^{n}a_{i}b_{i}>0$
k\"{o}nnen wir diese Ungleichung quadrieren, und erhalten somit%
\[
\left(  AB\right)  ^{2}\geq\left(  \sum_{i=1}^{n}a_{i}b_{i}\right)  ^{2}.
\]
Wegen%
\begin{align*}
\left(  AB\right)  ^{2}  &  =\underbrace{A^{2}}_{\substack{=a_{1}^{2}%
+a_{2}^{2}+\cdots+a_{n}^{2}\\\text{(nach Definition von }A\text{)}%
}}\ \ \underbrace{B^{2}}_{\substack{=b_{1}^{2}+b_{2}^{2}+\cdots+b_{n}%
^{2}\\\text{(nach Definition von }B\text{)}}}\\
&  =\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right)
\end{align*}
und $\sum_{i=1}^{n}a_{i}b_{i}=a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}$
l\"{a}\ss t sich dies umschreiben als%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]
Damit ist Lemma \ref{lem.sol.cs.proof-by-amgm.lem2} bewiesen.
\end{proof}

Nun beweisen wir Satz \ref{thm.cs} endlich in seiner allgemeinen Form:

\begin{proof}
[Beweis von Satz \ref{thm.cs}.]Wir unterscheiden die folgenden drei F\"{a}lle:

\textit{Fall 1:} Es gilt $\sum_{i=1}^{n}a_{i}b_{i}>0$.

\textit{Fall 2:} Es gilt $\sum_{i=1}^{n}a_{i}b_{i}=0$.

\textit{Fall 3:} Es gilt $\sum_{i=1}^{n}a_{i}b_{i}<0$.

In Fall 1 folgt Satz \ref{thm.cs} aus Lemma
\ref{lem.sol.cs.proof-by-amgm.lem2}. Wir m\"{u}ssen also nur die anderen
beiden F\"{a}lle untersuchen.

Betrachten wir nun Fall 2. In diesem Fall ist $\sum_{i=1}^{n}a_{i}b_{i}=0$.
Also ist $a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}=\sum_{i=1}^{n}a_{i}b_{i}=0$
und somit%
\begin{equation}
\left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)  ^{2}=0^{2}=0.
\label{sol.cs.proof-by-amgm.f2.2}%
\end{equation}
Aus Satz \ref{thm.xsquare} folgen aber schnell die zwei Ungleichungen
$a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\geq0$ und $b_{1}^{2}+b_{2}^{2}%
+\cdots+b_{n}^{2}\geq0$. Multiplizieren wir sie, so erhalten wir%
\begin{align*}
&  \left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}%
^{2}+b_{2}^{2}+\cdots+b_{n}^{2}\right) \\
&  \geq0=\left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)
^{2}\ \ \ \ \ \ \ \ \ \ \left(  \text{nach (\ref{sol.cs.proof-by-amgm.f2.2}%
)}\right)  .
\end{align*}
Damit ist Satz \ref{thm.cs} in Fall 2 bewiesen.

Schlie\ss lich betrachten wir Fall 3. In diesem Fall ist $\sum_{i=1}^{n}%
a_{i}b_{i}<0$. Also ist $\sum_{i=1}^{n}\left(  -a_{i}\right)  b_{i}%
=-\underbrace{\sum_{i=1}^{n}a_{i}b_{i}}_{<0}>0$. Also k\"{o}nnen wir Lemma
\ref{lem.sol.cs.proof-by-amgm.lem2} auf $-a_{i}$ statt $a_{i}$ anwenden. Wir
erhalten somit%
\begin{align*}
&  \left(  \left(  -a_{1}\right)  ^{2}+\left(  -a_{2}\right)  ^{2}%
+\cdots+\left(  -a_{n}\right)  ^{2}\right)  \left(  b_{1}^{2}+b_{2}^{2}%
+\cdots+b_{n}^{2}\right) \\
&  \geq\left(  \left(  -a_{1}\right)  b_{1}+\left(  -a_{2}\right)
b_{2}+\cdots+\left(  -a_{n}\right)  b_{n}\right)  ^{2}.
\end{align*}
Wegen%
\[
\underbrace{\left(  -a_{1}\right)  ^{2}}_{=a_{1}^{2}}+\underbrace{\left(
-a_{2}\right)  ^{2}}_{=a_{2}^{2}}+\cdots+\underbrace{\left(  -a_{n}\right)
^{2}}_{=a_{n}^{2}}=a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}%
\]
und%
\begin{align*}
\left(  \underbrace{\left(  -a_{1}\right)  b_{1}+\left(  -a_{2}\right)
b_{2}+\cdots+\left(  -a_{n}\right)  b_{n}}_{=-\left(  a_{1}b_{1}+a_{2}%
b_{2}+\cdots+a_{n}b_{n}\right)  }\right)  ^{2}  &  =\left(  -\left(
a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)  \right)  ^{2}\\
&  =\left(  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\right)  ^{2}%
\end{align*}
vereinfacht sich dies zu%
\[
\left(  a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\right)  \left(  b_{1}^{2}%
+b_{2}^{2}+\cdots+b_{n}^{2}\right)  \geq\left(  a_{1}b_{1}+a_{2}b_{2}%
+\cdots+a_{n}b_{n}\right)  ^{2}.
\]
Damit ist Satz \ref{thm.cs} in Fall 3 bewiesen.

Wir haben damit Satz \ref{thm.cs} in allen drei F\"{a}llen bewiesen; also gilt
Satz \ref{thm.cs} immer.
\end{proof}

Aufgabe \ref{exe.cs.proof-by-amgm} ist damit endlich gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.mantel2}}

\begin{proof}
[L\"{o}sungsskizze zu Aufgabe \ref{exe.mantel2}.]Dies ist im Wesentlichen eine
Analyse des Gleichheitsfalls in Beispiel \ref{exa.mantel}. Wir werden also
weitgehend wie in der L\"{o}sung von Beispiel \ref{exa.mantel} verfahren.

F\"{u}r jeden Knoten $v$ von $G$ sei $N\left(  v\right)  $ die Menge aller zu
$v$ benachbarten Knoten von $G$. Sei $V$ die Menge aller Knoten von $G$. Dann
ist also $\left\vert V\right\vert =n$ (denn $G$ hat $n$ Knoten). Wir
m\"{u}ssen zeigen, dass $G$ bipartierbar ist. Wenn $V=\varnothing$ ist, dann
ist dies trivial; wir nehmen also o. B. d. A. an, dass $V\neq\varnothing$ ist.
Wir w\"{a}hlen nun einen Knoten $v$ von $G$, f\"{u}r den $\left\vert N\left(
v\right)  \right\vert $ maximal ist. (Dies ist m\"{o}glich, denn
$V\neq\varnothing$.) Dann gilt also%
\begin{equation}
\left\vert N\left(  x\right)  \right\vert \leq\left\vert N\left(  v\right)
\right\vert \ \ \ \ \ \ \ \ \ \ \text{f\"{u}r jeden Knoten }x\in V.
\label{solexe.mantel2.NxNv}%
\end{equation}


Eine Kante von $G$ hei\ss e \textit{gut}, wenn sie durch \textbf{genau} einen
Knoten $x\in V\setminus N\left(  v\right)  $ verl\"{a}uft; sonst hei\ss e sie
\textit{schlecht}. Wie in der L\"{o}sung von Beispiel \ref{exa.mantel} sehen
wir nun, dass jede Kante von $G$ durch mindestens einen Knoten $x\in
V\setminus N\left(  v\right)  $ verl\"{a}uft. Jede schlechte Kante von $G$
verl\"{a}uft also durch \textbf{zwei} Knoten $x\in V\setminus N\left(
v\right)  $. Folglich gilt%
\begin{align}
&  \sum_{x\in V\setminus N\left(  v\right)  }\left(  \text{Anzahl aller Kanten
von }G\text{, die durch }x\text{ verlaufen}\right) \nonumber\\
&  =\left(  \text{Anzahl aller guten Kanten von }G\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ +2\cdot\left(  \text{Anzahl aller schlechten Kanten von
}G\right)  . \label{solexe.mantel2.3}%
\end{align}


Wir werden nun zeigen, dass jede Kante von $G$ gut ist.

[\textit{Beweis:} Nehmen wir das Gegenteil an. Dann hat $G$ also mindestens
eine schlechte Kante. Das hei\ss t,%
\[
\left(  \text{Anzahl aller schlechten Kanten von }G\right)  >0
\]
und damit%
\begin{align*}
&  2\cdot\left(  \text{Anzahl aller schlechten Kanten von }G\right) \\
&  >\left(  \text{Anzahl aller schlechten Kanten von }G\right)  .
\end{align*}
Aus (\ref{solexe.mantel2.3}) wird somit%
\begin{align*}
&  \sum_{x\in V\setminus N\left(  v\right)  }\left(  \text{Anzahl aller Kanten
von }G\text{, die durch }x\text{ verlaufen}\right) \\
&  =\left(  \text{Anzahl aller guten Kanten von }G\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\underbrace{2\cdot\left(  \text{Anzahl aller
schlechten Kanten von }G\right)  }_{>\left(  \text{Anzahl aller schlechten
Kanten von }G\right)  }\\
&  >\left(  \text{Anzahl aller guten Kanten von }G\right)  +\left(
\text{Anzahl aller schlechten Kanten von }G\right) \\
&  =\left(  \text{Anzahl aller Kanten von }G\right)  .
\end{align*}
Somit ist%
\begin{align*}
&  \left(  \text{Anzahl aller Kanten von }G\right) \\
&  <\sum_{x\in V\setminus N\left(  v\right)  }\underbrace{\left(  \text{Anzahl
aller Kanten von }G\text{, die durch }x\text{ verlaufen}\right)  }_{=\left(
\text{Anzahl aller Nachbarn von }x\right)  =\left\vert N\left(  x\right)
\right\vert }\\
&  =\sum_{x\in V\setminus N\left(  v\right)  }\underbrace{\left\vert N\left(
x\right)  \right\vert }_{\substack{\leq\left\vert N\left(  v\right)
\right\vert \\\text{(nach (\ref{solexe.mantel2.NxNv}))}}}\leq\sum_{x\in
V\setminus N\left(  v\right)  }\left\vert N\left(  v\right)  \right\vert
=\left\vert V\setminus N\left(  v\right)  \right\vert \cdot\left\vert N\left(
v\right)  \right\vert ,
\end{align*}
also%
\begin{equation}
\left\vert V\setminus N\left(  v\right)  \right\vert \cdot\left\vert N\left(
v\right)  \right\vert >\left(  \text{Anzahl aller Kanten von }G\right)
=n^{2}/4 \label{solexe.mantel2.4}%
\end{equation}
(denn $G$ hat genau $n^{2}/4$ Kanten). Doch wegen $N\left(  v\right)
\subseteq V$ gilt $\left\vert V\setminus N\left(  v\right)  \right\vert
=\left\vert V\right\vert -\left\vert N\left(  v\right)  \right\vert $ und
somit $\left\vert V\setminus N\left(  v\right)  \right\vert +\left\vert
N\left(  v\right)  \right\vert =\left\vert V\right\vert =n$. Also ist
$n=\left\vert V\setminus N\left(  v\right)  \right\vert +\left\vert N\left(
v\right)  \right\vert $, daher%
\begin{align*}
n^{2}  &  =\left(  \left\vert V\setminus N\left(  v\right)  \right\vert
+\left\vert N\left(  v\right)  \right\vert \right)  ^{2}\geq4\cdot
\underbrace{\left\vert V\setminus N\left(  v\right)  \right\vert
\cdot\left\vert N\left(  v\right)  \right\vert }_{\substack{>n^{2}%
/4\\\text{(nach (\ref{pf.exa.mantel.4}))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{laut Satz \ref{thm.2ab} \textbf{(b)},
angewandt auf }a=\left\vert V\setminus N\left(  v\right)  \right\vert \text{
und }b=\left\vert N\left(  v\right)  \right\vert \right) \\
&  >4\cdot n^{2}/4=n^{2},
\end{align*}
was absurd ist. Dieser Widerspruch zeigt, dass unsere Annahme falsch war.
Damit ist gezeigt, dass jede Kante von $G$ gut ist.]

Wir wissen nun, dass jede Kante von $G$ gut ist. Das hei\ss t: Jede Kante von
$G$ verl\"{a}uft durch \textbf{genau} einen Knoten $x\in V\setminus N\left(
v\right)  $ (denn so haben wir \textquotedblleft gute Kanten\textquotedblright%
\ ja definiert). Mit anderen Worten: Jede Kante von $G$ hat einen Endknoten in
$V\setminus N\left(  v\right)  $ und einen Endknoten in $N\left(  v\right)  $
(denn ein Knoten, der nicht in $V\setminus N\left(  v\right)  $ liegt, muss
nat\"{u}rlich in $N\left(  v\right)  $ liegen). Somit l\"{a}\ss t sich die
Knotenmenge $V$ des Graphen $G$ unterteilen in zwei disjunkte Teilmengen $A$
und $B$ mit der Eigenschaft, dass jede Kante von $G$ einen Endknoten in $A$
und einen Endknoten in $B$ hat (n\"{a}mlich $A=V\setminus N\left(  v\right)  $
und $B=N\left(  v\right)  $). Das hei\ss t, der Graph $G$ ist bipartierbar
(nach der Definition von \textquotedblleft bipartierbar\textquotedblright%
).\ Damit ist Aufgabe \ref{exe.mantel2} gel\"{o}st.
\end{proof}

Eine st\"{a}rkere Version von Aufgabe \ref{exe.mantel2} wurde in \cite[problem
1]{Rollin16} bewiesen: Und zwar lassen sich die Worte \textquotedblleft%
$n^{2}/4$ Kanten\textquotedblright\ in der Aufgabe durch \textquotedblleft
mehr als $\left(  n-1\right)  ^{2}/4+1$ Kanten\textquotedblright\ ersetzen.
(Die obige L\"{o}sung von Aufgabe \ref{exe.mantel2} ist aber f\"{u}r diese
st\"{a}rkere Version nicht mehr geeignet.)

\subsubsection{zu Aufgabe \ref{exe.friendship-paradox}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.friendship-paradox}.]Wir haben%
\[
q_{v}=\sum_{\substack{e\in E;\\v\text{ liegt auf }e}}\dfrac{\deg\left(
e/v\right)  }{\deg v}\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r jeden Knoten }v\in V
\]
(nach Definition von $q_{v}$). Addieren wir diese Gleichungen f\"{u}r alle
$v\in V$ zusammen, so erhalten wir%
\begin{align}
\sum_{v\in V}q_{v}  &  =\underbrace{\sum_{v\in V}\ \ \sum_{\substack{e\in
E;\\v\text{ liegt auf }e}}}_{=\sum_{e\in E}\ \ \sum_{\substack{v\in
V;\\v\text{ liegt auf }e}}}\dfrac{\deg\left(  e/v\right)  }{\deg v}\nonumber\\
&  =\sum_{e\in E}\ \ \sum_{\substack{v\in V;\\v\text{ liegt auf }e}%
}\dfrac{\deg\left(  e/v\right)  }{\deg v}. \label{sol.friendship-paradox.1}%
\end{align}


Doch f\"{u}r jede Kante $e\in E$ gilt%
\begin{equation}
\sum_{\substack{v\in V;\\v\text{ liegt auf }e}}\dfrac{\deg\left(  e/v\right)
}{\deg v}\geq2. \label{sol.friendship-paradox.geq2}%
\end{equation}


[\textit{Beweis von (\ref{sol.friendship-paradox.geq2}):} Sei $e$ eine Kante.
Seien $p$ und $q$ die zwei Endknoten von $e$. Dann gilt $e/p=q$ und $e/q=p$.
Ferner liegt der Knoten $p$ auf mindestens einer Kante (denn $p$ liegt auf der
Kante $e$); somit ist $\deg p\geq1>0$. Das hei\ss t, $\deg p$ ist positiv.
Analog sehen wir, dass $\deg q$ positiv ist.

Nun gibt es aber genau zwei Knoten $v\in V$, die auf $e$ liegen -- n\"{a}mlich
$p$ und $q$ (denn $p$ und $q$ sind die zwei Endknoten von $e$). Also ist%
\begin{align*}
\sum_{\substack{v\in V;\\v\text{ liegt auf }e}}\dfrac{\deg\left(  e/v\right)
}{\deg v}  &  =\dfrac{\deg\left(  e/p\right)  }{\deg p}+\dfrac{\deg\left(
e/q\right)  }{\deg q}\\
&  =\dfrac{\deg q}{\deg p}+\dfrac{\deg p}{\deg q}\ \ \ \ \ \ \ \ \ \ \left(
\text{denn }e/p=q\text{ und }e/q=p\right) \\
&  \geq2
\end{align*}
(nach Satz \ref{thm.2ab} \textbf{(d)}, angewandt auf $a=\deg q$ und $b=\deg
p$). Damit ist (\ref{sol.friendship-paradox.geq2}) bewiesen.]

Nun wird (\ref{sol.friendship-paradox.1}) zu%
\begin{align}
\sum_{v\in V}q_{v}  &  =\sum_{e\in E}\ \ \underbrace{\sum_{\substack{v\in
V;\\v\text{ liegt auf }e}}\dfrac{\deg\left(  e/v\right)  }{\deg v}%
}_{\substack{\geq2\\\text{(nach (\ref{sol.friendship-paradox.geq2}))}}%
}\geq\sum_{e\in E}2\nonumber\\
&  =\left\vert E\right\vert \cdot2=2\left\vert E\right\vert .
\label{sol.friendship-paradox.4}%
\end{align}


F\"{u}r jeden Knoten $v$ gilt aber%
\begin{align*}
\deg v  &  =\left(  \text{der Grad von }v\right)  =\left(  \text{die Anzahl
aller Kanten, die }v\text{ enthalten}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{laut der Definition
des Grades von }v\right) \\
&  =\sum_{\substack{e\in E;\\v\text{ liegt auf }e}}1
\end{align*}
(denn%
\begin{align*}
\sum_{\substack{e\in E;\\v\text{ liegt auf }e}}1  &  =\left(  \text{die Anzahl
aller }e\in E\text{ mit der Eigenschaft, dass }v\text{ auf }e\text{
liegt}\right)  \cdot1\\
&  =\left(  \text{die Anzahl aller }e\in E\text{ mit der Eigenschaft, dass
}v\text{ auf }e\text{ liegt}\right) \\
&  =\left(  \text{die Anzahl aller Kanten }e\in E\text{, auf denen }v\text{
liegt}\right) \\
&  =\left(  \text{die Anzahl aller Kanten, die }v\text{ enthalten}\right)
\end{align*}
). Addieren wir diese Gleichungen f\"{u}r alle $v\in V$ zusammen, so erhalten
wir%
\begin{align*}
\sum_{v\in V}\deg v  &  =\underbrace{\sum_{v\in V}\ \ \sum_{\substack{e\in
E;\\v\text{ liegt auf }e}}}_{=\sum_{e\in E}\ \ \sum_{\substack{v\in
V;\\v\text{ liegt auf }e}}}1=\sum_{e\in E}\ \ \underbrace{\sum_{\substack{v\in
V;\\v\text{ liegt auf }e}}1}_{\substack{=1+1\\\text{(denn es gibt genau
zwei}\\\text{Knoten }v\in V\text{, die auf }e\text{ liegen}\\\text{(denn die
Kante }e\text{ verbindet}\\\text{genau zwei Knoten))}}}\\
&  =\sum_{e\in E}\underbrace{\left(  1+1\right)  }_{=2}=\sum_{e\in
E}2=\left\vert E\right\vert \cdot2=2\left\vert E\right\vert .
\end{align*}
Somit k\"{o}nnen wir (\ref{sol.friendship-paradox.4}) folgenderma\ss en
umschreiben:%
\[
\sum_{v\in V}q_{v}\geq\sum_{v\in V}\deg v.
\]
Damit ist (\ref{eq.exe.friends-neighbors.claim}) bewiesen. Das hei\ss t,
Aufgabe \ref{exe.friendship-paradox} ist gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.extcomb.Si-wo-Sj}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.extcomb.Si-wo-Sj}.]Wir haben $\left\vert
S\right\vert =n$ (denn $S$ ist eine $n$-elementige Menge).

Sei $K$ die Menge $\left\{  1,2,\ldots,k\right\}  $. Dann ist $\left\vert
K\right\vert =k$. Nun erinnern wir uns aber: Die Mengen $S_{1},S_{2}%
,\ldots,S_{k}$ sind Teilmengen von $S$. Das hei\ss t, f\"{u}r jedes $i\in K$
ist $S_{i}$ eine Teilmenge von $S$ (denn $K=\left\{  1,2,\ldots,k\right\}  $).

Wir definieren ein \textit{gutes Tripel} als ein Tripel $\left(  s,i,j\right)
$ mit $s\in S$ und $i,j\in K$ und $s\in S_{i}\setminus S_{j}$. Wir behaupten
nun folgendes: F\"{u}r jedes $s\in S$ gilt%
\begin{align}
&  \left(  \text{die Anzahl aller guten Tripel, deren erster Eintrag }s\text{
ist}\right) \nonumber\\
&  \leq\dfrac{k^{2}}{4}. \label{sol.extcomb.Si-wo-Sj.leqkk4}%
\end{align}


[\textit{Beweis von (\ref{sol.extcomb.Si-wo-Sj.leqkk4}):} Sei $s\in S$. Sei
$A$ die Menge aller $i\in K$, die $s\in S_{i}$ erf\"{u}llen. Sei $B$ die Menge
aller $i\in K$, die $s\notin S_{i}$ erf\"{u}llen. Jedes $i\in K$ erf\"{u}llt
entweder $s\in S_{i}$ oder $s\notin S_{i}$. Mit anderen Worten: Jedes $i\in K$
erf\"{u}llt entweder $i\in A$ oder $i\in B$ (nach den Definitionen von $A$ und
$B$). Also ist $A\cup B=K$ (denn $A$ und $B$ sind Teilmengen von $K$); hieraus
folgt $\left\vert A\cup B\right\vert =\left\vert K\right\vert =k$. Ferner sind
die Mengen $A$ und $B$ disjunkt (denn ein $i\in K$ kann nicht gleichzeitig
$s\in S_{i}$ und $s\notin S_{i}$ erf\"{u}llen). Also gilt $\left\vert A\cup
B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert $, und daher
$\left\vert A\right\vert +\left\vert B\right\vert =\left\vert A\cup
B\right\vert =k$. Aus Satz \ref{thm.2ab} \textbf{(b)} (angewandt auf
$a=\left\vert A\right\vert $ und $b=\left\vert B\right\vert $) folgt also
$\left(  \left\vert A\right\vert +\left\vert B\right\vert \right)  ^{2}%
\geq4\cdot\left\vert A\right\vert \cdot\left\vert B\right\vert $ (denn
$\left\vert A\right\vert $ und $\left\vert B\right\vert $ sind nichtnegativ).
Wegen $\left\vert A\right\vert +\left\vert B\right\vert =k$ vereinfacht sich
dies zu $k^{2}\geq4\cdot\left\vert A\right\vert \cdot\left\vert B\right\vert
$. Das hei\ss t, $\left\vert A\right\vert \cdot\left\vert B\right\vert
\leq\dfrac{k^{2}}{4}$.

Nun betrachten wir die guten Tripel, deren erster Eintrag $s$ ist. Diese guten
Tripel haben die Form $\left(  s,i,j\right)  $, wobei $i$ und $j$ zwei
Elemente von $K$ sind, die $s\in S_{i}\setminus S_{j}$ erf\"{u}llen. Die
Anzahl dieser guten Tripel ist also gleich der Anzahl aller Paare $\left(
i,j\right)  $ von zwei Elementen von $K$, die $s\in S_{i}\setminus S_{j}$
erf\"{u}llen. Das hei\ss t, wir haben%
\begin{align*}
&  \left(  \text{die Anzahl aller guten Tripel, deren erster Eintrag }s\text{
ist}\right) \\
&  =\left(  \text{die Anzahl aller Paare }\left(  i,j\right)  \in K^{2}\text{
mit }s\in S_{i}\setminus S_{j}\right) \\
&  =\left(  \text{die Anzahl aller Paare }\left(  i,j\right)  \in K^{2}\text{
mit }s\in S_{i}\text{ und }s\notin S_{j}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{denn die Aussage
\textquotedblleft}s\in S_{i}\setminus S_{j}\text{\textquotedblright\ ist
\"{a}quivalent zu \textquotedblleft}s\in S_{i}\text{ und }s\notin
S_{j}\text{\textquotedblright}\right) \\
&  =\left(  \text{die Anzahl aller Paare }\left(  i,j\right)  \in K^{2}\text{
mit }i\in A\text{ und }j\in B\right) \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{denn die Aussage \textquotedblleft}s\in S_{i}\text{\textquotedblright%
\ ist \"{a}quivalent zu \textquotedblleft}i\in A\text{\textquotedblright%
\ (wegen der}\\
\text{Definition von }A\text{), und die Aussage \textquotedblleft}s\notin
S_{j}\text{\textquotedblright\ ist}\\
\text{\"{a}quivalent zu \textquotedblleft}j\in B\text{\textquotedblright%
\ (wegen der Definition von }B\text{)}%
\end{array}
\right) \\
&  =\left(  \text{die Anzahl aller Paare }\left(  i,j\right)  \in A\times
B\right) \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{denn die Paare }\left(  i,j\right)  \in K^{2}\text{ mit }i\in A\text{
und }j\in B\\
\text{sind genau die Paare }\left(  i,j\right)  \in A\times B\text{ (weil
}A\text{ und }B\text{ Teilmengen}\\
\text{von }K\text{ sind)}%
\end{array}
\right) \\
&  =\left\vert A\times B\right\vert =\left\vert A\right\vert \cdot\left\vert
B\right\vert \leq\dfrac{k^{2}}{4}.
\end{align*}
Damit ist (\ref{sol.extcomb.Si-wo-Sj.leqkk4}) bewiesen.]

Wir wollen nun die Anzahl aller guten Tripel auf zweierlei Weisen z\"{a}hlen.

Zum einen wissen wir: Jedes gute Tripel hat die Form $\left(  s,i,j\right)  $
f\"{u}r ein $s\in S$ (und zwei weitere Eintr\"{a}ge $i$ und $j$, die uns
gerade nicht interessieren). Also ist
\begin{align}
&  \left(  \text{die Anzahl aller guten Tripel}\right) \nonumber\\
&  =\sum_{s\in S}\underbrace{\left(  \text{die Anzahl aller guten Tripel,
deren erster Eintrag }s\text{ ist}\right)  }_{\substack{\leq\dfrac{k^{2}}%
{4}\\\text{(nach (\ref{sol.extcomb.Si-wo-Sj.leqkk4}))}}}\nonumber\\
&  \leq\sum_{s\in S}\dfrac{k^{2}}{4}=\underbrace{\left\vert S\right\vert
}_{=n}\cdot\dfrac{k^{2}}{4}=n\cdot\dfrac{k^{2}}{4}.
\label{sol.extcomb.Si-wo-Sj.1}%
\end{align}


Zum anderen wissen wir aber: Jedes gute Tripel hat die Form $\left(
s,i,j\right)  $ f\"{u}r ein Paar $\left(  i,j\right)  \in K^{2}$ und ein
Element $s\in S$. Das Paar $\left(  i,j\right)  $ muss dabei $i\neq j$
erf\"{u}llen\footnote{\textit{Beweis:} Sei $\left(  s,i,j\right)  $ ein gutes
Tripel. Wir m\"{u}ssen zeigen, dass $i\neq j$ gilt.
\par
In der Tat nehmen wir das Gegenteil an. Dann ist also $i=j$. Aber da $\left(
s,i,j\right)  $ ein gutes Tripel ist, gilt $s\in S_{i}\setminus S_{j}$ (nach
der Definition eines \textquotedblleft guten Tripels\textquotedblright). Wegen
$i=j$ ist aber $S_{i}\setminus S_{j}=S_{j}\setminus S_{j}=\varnothing$.
Folglich ist $s\in S_{i}\setminus S_{j}=\varnothing$, was aber absurd ist
(denn die leere Menge hat kein Element). Damit haben wir einen Widerspruch
erhalten. Dieser Widerspruch zeigt, dass unsere Annahme falsch war. Damit ist
$i\neq j$ bewiesen (wie gew\"{u}nscht).}. Also ist
\begin{align*}
&  \left(  \text{die Anzahl aller guten Tripel}\right) \\
&  =\sum_{\substack{\left(  i,j\right)  \in K^{2};\\i\neq j}%
}\underbrace{\left(  \text{die Anzahl aller guten Tripel, deren letzte zwei
Eintr\"{a}ge }i\text{ und }j\text{ sind}\right)  }_{\substack{=\left(
\text{die Anzahl aller }s\in S\text{, f\"{u}r die }\left(  s,i,j\right)
\text{ ein gutes Tripel ist}\right)  \\=\left(  \text{die Anzahl aller }s\in
S\text{, die }s\in S_{i}\setminus S_{j}\text{ erf\"{u}llen}\right)
\\\text{(denn das Tripel }\left(  s,i,j\right)  \text{ f\"{u}r ein }s\in
S\text{ ist genau dann ein gutes Tripel,}\\\text{wenn }s\in S_{i}\setminus
S_{j}\text{ erf\"{u}llt ist)}}}\\
&  =\sum_{\substack{\left(  i,j\right)  \in K^{2};\\i\neq j}%
}\underbrace{\left(  \text{die Anzahl aller }s\in S\text{, die }s\in
S_{i}\setminus S_{j}\text{ erf\"{u}llen}\right)  }_{\substack{=\left\vert
S_{i}\setminus S_{j}\right\vert \\\text{(denn }S_{i}\setminus S_{j}\text{ ist
eine Teilmenge von }S\text{)}}}\\
&  =\sum_{\substack{\left(  i,j\right)  \in K^{2};\\i\neq j}}\left\vert
S_{i}\setminus S_{j}\right\vert .
\end{align*}
Somit ist%
\begin{align}
\sum_{\substack{\left(  i,j\right)  \in K^{2};\\i\neq j}}\left\vert
S_{i}\setminus S_{j}\right\vert  &  =\left(  \text{die Anzahl aller guten
Tripel}\right) \nonumber\\
&  \leq n\cdot\dfrac{k^{2}}{4} \label{sol.extcomb.Si-wo-Sj.sumineq}%
\end{align}
(nach (\ref{sol.extcomb.Si-wo-Sj.1})).

Nun m\"{u}ssen wir zeigen, dass es zwei Zahlen $i,j\in\left\{  1,2,\ldots
,k\right\}  $ mit $i\neq j$ und $\left\vert S_{i}\setminus S_{j}\right\vert
\leq\dfrac{nk}{4\left(  k-1\right)  }$ gibt. Dies beweisen wir durch
Widerspruch: Wir nehmen also an, es g\"{a}be keine zwei solche Zahlen. F\"{u}r
je zwei Zahlen $i,j\in\left\{  1,2,\ldots,k\right\}  $ mit $i\neq j$ muss
also
\[
\left\vert S_{i}\setminus S_{j}\right\vert >\dfrac{nk}{4\left(  k-1\right)  }%
\]
gelten. Mit anderen Worten: F\"{u}r je zwei Zahlen $i,j\in K$ mit $i\neq j$
muss%
\begin{equation}
\left\vert S_{i}\setminus S_{j}\right\vert >\dfrac{nk}{4\left(  k-1\right)  }
\label{sol.extcomb.Si-wo-Sj.deny}%
\end{equation}
gelten (denn $K=\left\{  1,2,\ldots,k\right\}  $).

Die Anzahl aller Paare $\left(  i,j\right)  \in K^{2}$ ist $\left\vert
K^{2}\right\vert =\left\vert K\right\vert ^{2}=k^{2}$ (denn $\left\vert
K\right\vert =k$). Daher gibt es genau $k^{2}-k$ Paare $\left(  i,j\right)
\in K^{2}$, die $i\neq j$ erf\"{u}llen (denn die Anzahl \textbf{aller} Paare
$\left(  i,j\right)  \in K^{2}$ ist $k^{2}$, und aus diesen $k^{2}$ Paaren
m\"{u}ssen die $k$ Paare $\left(  i,j\right)  $ mit $i=j$ herausgez\"{a}hlt
werden). Das hei\ss t,%
\[
\left\vert \left\{  \left(  i,j\right)  \in K^{2}\ \mid\ i\neq j\right\}
\right\vert =k^{2}-k.
\]
Also ist%
\begin{align}
\left\vert \left\{  \left(  i,j\right)  \in K^{2}\ \mid\ i\neq j\right\}
\right\vert  &  =k^{2}-k=\underbrace{k}_{\geq2>0}\underbrace{\left(
k-1\right)  }_{\substack{>0\\\text{(denn }k\geq2>1\text{)}}%
}\label{sol.extcomb.Si-wo-Sj.num-prs}\\
&  >0.\nonumber
\end{align}
Das hei\ss t, die Menge $\left\{  \left(  i,j\right)  \in K^{2}\ \mid\ i\neq
j\right\}  $ ist nichtleer. Folglich ist\footnote{Wir werden hier gleich die
Tatsache benutzen, dass eine \textbf{nichtleere} Summe von strikten
Ungleichungen wieder eine strikte Ungleichung ist. Das hei\ss t, wir werden
folgendes Lemma benutzen:
\par
\begin{statement}
\textit{Lemma:} Sei $T$ eine \textbf{nichtleere} Menge. F\"{u}r jedes $t\in T$
seien $a_{t}$ und $b_{t}$ zwei reelle Zahlen, die $a_{t}>b_{t}$ erf\"{u}llen.
Dann gilt $\sum_{t\in T}a_{t}>\sum_{t\in T}b_{t}$.
\end{statement}
\par
Man beachte, dass hier $T$ als nichtleer vorausgesetzt wird; sonst gilt
n\"{a}mlich $\sum_{t\in T}a_{t}=\sum_{t\in T}b_{t}$ (weil beide Seiten als
leere Summen gleich $0$ sind).
\par
In unserem Fall werden wir das Lemma auf die nichtleere Menge $T=\left\{
\left(  i,j\right)  \in K^{2}\ \mid\ i\neq j\right\}  $ und auf die Elemente
$a_{\left(  i,j\right)  }=\left\vert S_{i}\setminus S_{j}\right\vert $ und
$b_{\left(  i,j\right)  }=\dfrac{nk}{4\left(  k-1\right)  }$ anwenden. (Dass
die Menge $\left\{  \left(  i,j\right)  \in K^{2}\ \mid\ i\neq j\right\}  $
dabei tats\"{a}chlich nichtleer ist, haben wir vorhin gezeigt.)}%
\begin{align*}
\sum_{\substack{\left(  i,j\right)  \in K^{2};\\i\neq j}%
}\underbrace{\left\vert S_{i}\setminus S_{j}\right\vert }_{\substack{>\dfrac
{nk}{4\left(  k-1\right)  }\\\text{(nach (\ref{sol.extcomb.Si-wo-Sj.deny}))}%
}}  &  >\sum_{\substack{\left(  i,j\right)  \in K^{2};\\i\neq j}}\dfrac
{nk}{4\left(  k-1\right)  }=\underbrace{\left\vert \left\{  \left(
i,j\right)  \in K^{2}\ \mid\ i\neq j\right\}  \right\vert }%
_{\substack{=k\left(  k-1\right)  \\\text{(nach
(\ref{sol.extcomb.Si-wo-Sj.num-prs}))}}}\cdot\dfrac{nk}{4\left(  k-1\right)
}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{denn }\sum_{t\in T}c=\left\vert T\right\vert \cdot c\text{ f\"{u}r jede
endliche Menge }T\\
\text{und jede Zahl }c
\end{array}
\right) \\
&  =k\left(  k-1\right)  \cdot\dfrac{nk}{4\left(  k-1\right)  }=n\cdot
\dfrac{k^{2}}{4}.
\end{align*}
Dies widerspricht aber (\ref{sol.extcomb.Si-wo-Sj.sumineq}). Dieser
Widerspruch zeigt, dass unsere Annahme falsch war. Somit haben wir gezeigt,
dass es zwei Zahlen $i,j\in K$ mit $i\neq j$ und $\left\vert S_{i}\setminus
S_{j}\right\vert \leq\dfrac{nk}{4\left(  k-1\right)  }$ gibt. Aufgabe
\ref{exe.extcomb.Si-wo-Sj} ist damit gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.extcomb.chess-amgm-gen}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.extcomb.chess-amgm-gen}.]Folgende
Verallgemeinerung von Beispiel \ref{exa.chess-amgm} wurde von David Schmitz vorgeschlagen:

\begin{theorem}
\label{thm.extcomb.chess-amgm-gen-1}Sei $n\in\mathbb{N}$ beliebig. Sei $d$
eine positive ganze Zahl. Seien $X_{1},X_{2},\ldots,X_{d}$ beliebige endliche
Mengen. Sei $X=X_{1}\times X_{2}\times\cdots\times X_{d}$. F\"{u}r jedes
$d$-Tupel $x\in X$ und jedes $i\in\left\{  1,2,\ldots,d\right\}  $ werden wir
den $i$-ten Eintrag von $x$ mit $x_{i}$ bezeichnen. (Es gilt also $x=\left(
x_{1},x_{2},\ldots,x_{d}\right)  $ f\"{u}r jedes $x\in X$.)

Sei $f:X\rightarrow\left\{  1,2,\ldots,n\right\}  $ eine beliebige Abbildung.
F\"{u}r jedes $j\in\left\{  1,2,\ldots,n\right\}  $ sei $a_{j}$ die Anzahl
aller $x\in X$, die $f\left(  x\right)  =j$ erf\"{u}llen. Sei
\[
C=\dfrac{d\left(  \sqrt[d]{a_{1}}+\sqrt[d]{a_{2}}+\cdots+\sqrt[d]{a_{n}%
}\right)  }{\left\vert X_{1}\right\vert +\left\vert X_{2}\right\vert
+\cdots+\left\vert X_{d}\right\vert }.
\]
(Wir nehmen an, dass der Nenner hier von $0$ verschieden ist.) Dann gibt es
ein $i\in\left\{  1,2,\ldots,d\right\}  $ und ein $z\in X_{i}$ mit der
Eigenschaft, dass
\[
\left\vert \left\{  f\left(  x\right)  \ \mid\ x\in X\text{ und }%
x_{i}=z\right\}  \right\vert \geq C
\]
gilt (d.h. mit der Eigenschaft, dass die Abbildung $f$ auf der Menge aller
$x\in X$ mit $x_{i}=z$ mindestens $C$ verschiedene Werte annimmt).
\end{theorem}

Bevor wir Satz \ref{thm.extcomb.chess-amgm-gen-1} beweisen, sind ein paar
Worte zu seiner Bedeutung angesagt, um eine Intuition f\"{u}r seine Aussage zu
vermitteln. Wir betrachten den Fall, wenn jede der $d$ Mengen $X_{i}$ die Form
$X_{i}=\left\{  1,2,\ldots,m_{i}\right\}  $ f\"{u}r ein $m_{i}\in\mathbb{N}$
hat. (Dieser Fall ist de-facto der Allgemeinfall, denn wir k\"{o}nnen die
Elemente von $X_{i}$ beliebig umbenennen, und auf diese Weise erreichen wir,
dass $X_{i}$ tats\"{a}chlich diese Form hat.) Die Menge $X=X_{1}\times
X_{2}\times\cdots\times X_{d}$ kann man sich dann als ein \textquotedblleft%
$d$-dimensionales verallgemeinertes Schachbrett\textquotedblright\ vorstellen,
das die Form eines Hyperquaders hat (mit Kantenl\"{a}ngen $m_{1},m_{2}%
,\ldots,m_{d}$). Dieses verallgemeinerte Schachbrett ist in $1\times
1\times\cdots\times1$-Hyperw\"{u}rfel unterteilt, die wir die \textit{Felder}
dieses Schachbretts nennen. Eine Abbildung $f:X\rightarrow\left\{
1,2,\ldots,n\right\}  $ k\"{o}nnen wir uns also vorstellen als eine
M\"{o}glichkeit, Zahlen zwischen $1$ und $n$ in diese Felder einzutragen
(jeweils genau eine Zahl pro Feld). F\"{u}r jedes $j\in\left\{  1,2,\ldots
,n\right\}  $ ist dann $a_{j}$ die Anzahl aller Felder, deren Eintrag $j$ ist.
Die Behauptung von Satz \ref{thm.extcomb.chess-amgm-gen-1} ist dann, dass es
mindestens eine \textquotedblleft Hyperzeile\textquotedblright\ des
verallgemeinerten Schachbretts (d. h. einen Querschnitt mit einer
achsenparallelen Hyperbene) gibt, die mindestens $C$ verschiedene Zahlen
enth\"{a}lt. (Im Falle von $d=2$ sind solche \textquotedblleft
Hyperzeilen\textquotedblright\ genau die Zeilen und die Spalten des Schachbretts.)

\begin{proof}
[Beweis von Satz \ref{thm.extcomb.chess-amgm-gen-1}.]F\"{u}r jedes
$i\in\left\{  1,2,\ldots,d\right\}  $ und jedes $z\in X_{i}$ sei%
\begin{equation}
p_{i,z}=\left\vert \left\{  f\left(  x\right)  \ \mid\ x\in X\text{ und }%
x_{i}=z\right\}  \right\vert . \label{pf.thm.extcomb.chess-amgm-gen-1.piz=}%
\end{equation}


F\"{u}r jedes $i\in\left\{  1,2,\ldots,d\right\}  $ und jedes $k\in\left\{
1,2,\ldots,n\right\}  $ sei%
\begin{equation}
q_{i,k}=\left\vert \left\{  x_{i}\ \mid\ x\in X\text{ und }f\left(  x\right)
=k\right\}  \right\vert . \label{pf.thm.extcomb.chess-amgm-gen-1.qik=}%
\end{equation}


F\"{u}r jedes $i\in\left\{  1,2,\ldots,d\right\}  $ gilt dann%
\begin{equation}
\sum_{z\in X_{i}}p_{i,z}=\sum_{k=1}^{n}q_{i,k}.
\label{pf.thm.extcomb.chess-amgm-gen-1.sums=}%
\end{equation}


[\textit{Beweis von (\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=}):} Sei
$i\in\left\{  1,2,\ldots,d\right\}  $ beliebig.

Ein Paar $\left(  z,k\right)  \in X_{i}\times\left\{  1,2,\ldots,n\right\}  $
hei\ss e ein \textit{F-Paar}, wenn es ein $x\in X$ gibt, das $x_{i}=z$ und
$f\left(  x\right)  =k$ erf\"{u}llt. Wie viele F-Paare gibt es? Einerseits ist
der erste Eintrag eines jeden F-Paares ein Element $z$ von $X_{i}$. Somit ist%
\begin{align}
&  \left(  \text{die Anzahl aller F-Paare}\right) \nonumber\\
&  =\sum_{z\in X_{i}}\left(  \text{die Anzahl aller F-Paare, deren erster
Eintrag }z\text{ ist}\right)  .
\label{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.3a}%
\end{align}
Doch f\"{u}r jedes $z\in X_{i}$ ist%
\begin{align}
&  \left(  \text{die Anzahl aller F-Paare, deren erster Eintrag }z\text{
ist}\right) \nonumber\\
&  =\left(  \text{die Anzahl aller }k\in\left\{  1,2,\ldots,n\right\}  \text{,
f\"{u}r die }\left(  z,k\right)  \text{ ein F-Paar ist}\right) \nonumber\\
&  =\left(  \text{die Anzahl aller }k\in\left\{  1,2,\ldots,n\right\}  \text{,
die die}\right. \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{Form }k=f\left(  x\right)  \text{ f\"{u}r
ein }x\in X\text{ mit }x_{i}=z\text{ haben}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{nach der Definition
eines F-Paares}\right) \nonumber\\
&  =\left\vert \left\{  f\left(  x\right)  \ \mid\ x\in X\text{ und }%
x_{i}=z\right\}  \right\vert \nonumber\\
&  =p_{i,z}\ \ \ \ \ \ \ \ \ \ \left(  \text{nach
(\ref{pf.thm.extcomb.chess-amgm-gen-1.piz=})}\right)  .
\label{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.3b}%
\end{align}
Damit wird (\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.3a}) zu%
\begin{align}
&  \left(  \text{die Anzahl aller F-Paare}\right) \nonumber\\
&  =\sum_{z\in X_{i}}\underbrace{\left(  \text{die Anzahl aller F-Paare, deren
erster Eintrag }z\text{ ist}\right)  }_{\substack{=p_{i,z}\\\text{(nach
(\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.3b}))}}}\nonumber\\
&  =\sum_{z\in X_{i}}p_{i,z}.
\label{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.3c}%
\end{align}


Andererseits ist der zweite Eintrag eines jeden F-Paares ein Element $k$ von
$\left\{  1,2,\ldots,n\right\}  $. Somit ist%
\begin{align}
&  \left(  \text{die Anzahl aller F-Paare}\right) \nonumber\\
&  =\sum_{k=1}^{n}\left(  \text{die Anzahl aller F-Paare, deren zweiter
Eintrag }k\text{ ist}\right)  .
\label{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.4a}%
\end{align}
Doch f\"{u}r jedes $k\in\left\{  1,2,\ldots,n\right\}  $ ist%
\begin{align}
&  \left(  \text{die Anzahl aller F-Paare, deren zweiter Eintrag }k\text{
ist}\right) \nonumber\\
&  =\left(  \text{die Anzahl aller }z\in X_{i}\text{, f\"{u}r die }\left(
z,k\right)  \text{ ein F-Paar ist}\right) \nonumber\\
&  =\left(  \text{die Anzahl aller }z\in X_{i}\text{, die die}\right.
\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{Form }z=x_{i}\text{ f\"{u}r ein }x\in
X\text{ mit }f\left(  x\right)  =k\text{ haben}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{nach der Definition
eines F-Paares}\right) \nonumber\\
&  =\left\vert \left\{  x_{i}\ \mid\ x\in X\text{ und }f\left(  x\right)
=k\right\}  \right\vert \nonumber\\
&  =q_{i,k}\ \ \ \ \ \ \ \ \ \ \left(  \text{nach
(\ref{pf.thm.extcomb.chess-amgm-gen-1.qik=})}\right)  .
\label{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.4b}%
\end{align}
Damit wird (\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.4a}) zu%
\begin{align*}
&  \left(  \text{die Anzahl aller F-Paare}\right) \\
&  =\sum_{k=1}^{n}\underbrace{\left(  \text{die Anzahl aller F-Paare, deren
zweiter Eintrag }k\text{ ist}\right)  }_{\substack{=q_{i,k}\\\text{(nach
(\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.4b}))}}}\\
&  =\sum_{z\in X_{i}}q_{i,k}.
\end{align*}
Vergleichen wir diese Gleichung mit
(\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=.pf.3c}), so erhalten wir
$\sum_{z\in X_{i}}p_{i,z}=\sum_{k=1}^{n}q_{i,k}$. Damit ist
(\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=}) bewiesen.]

Nun ist%
\begin{align}
&  \sum_{i=1}^{d}\underbrace{\sum_{z\in X_{i}}p_{i,z}}_{\substack{=\sum
_{k=1}^{n}q_{i,k}\\\text{(nach (\ref{pf.thm.extcomb.chess-amgm-gen-1.sums=}%
))}}}\nonumber\\
&  =\underbrace{\sum_{i=1}^{d}\ \ \sum_{k=1}^{n}}_{=\sum_{k=1}^{n}%
\ \ \sum_{i=1}^{d}}q_{i,k}=\sum_{k=1}^{n}\ \ \underbrace{\sum_{i=1}^{d}%
q_{i,k}}_{=q_{1,k}+q_{2,k}+\cdots+q_{d,k}}\nonumber\\
&  =\sum_{k=1}^{n}\underbrace{\left(  q_{1,k}+q_{2,k}+\cdots+q_{d,k}\right)
}_{\substack{\geq d\sqrt[d]{q_{1,k}q_{2,k}\cdots q_{d,k}}\\\text{(nach Theorem
\ref{thm.am-gm} \textbf{(b)},}\\\text{angewandt auf }d\text{ und }%
q_{i,k}\\\text{statt }n\text{ und }a_{i}\text{)}}}\nonumber\\
&  \geq\sum_{k=1}^{n}d\sqrt[d]{q_{1,k}q_{2,k}\cdots q_{d,k}}=d\sum_{k=1}%
^{n}\sqrt[d]{q_{1,k}q_{2,k}\cdots q_{d,k}}.
\label{pf.thm.extcomb.chess-amgm-gen-1.sumineq}%
\end{align}


Andererseits gilt%
\begin{equation}
q_{1,k}q_{2,k}\cdots q_{d,k}\geq a_{k}
\label{pf.thm.extcomb.chess-amgm-gen-1.prodgeq}%
\end{equation}
f\"{u}r jedes $k\in\left\{  1,2,\ldots,n\right\}  $.

[\textit{Beweis von (\ref{pf.thm.extcomb.chess-amgm-gen-1.prodgeq}):} Sei
$k\in\left\{  1,2,\ldots,n\right\}  $ beliebig. F\"{u}r jedes $i\in\left\{
1,2,\ldots,d\right\}  $ definieren wir eine Menge%
\[
Q_{i,k}=\left\{  x_{i}\ \mid\ x\in X\text{ und }f\left(  x\right)  =k\right\}
.
\]
F\"{u}r jedes $i\in\left\{  1,2,\ldots,d\right\}  $ gilt also%
\begin{equation}
\left\vert Q_{i,k}\right\vert =\left\vert \left\{  x_{i}\ \mid\ x\in X\text{
und }f\left(  x\right)  =k\right\}  \right\vert =q_{i,k}
\label{pf.thm.extcomb.chess-amgm-gen-1.prodgeq.pf.1}%
\end{equation}
(nach (\ref{pf.thm.extcomb.chess-amgm-gen-1.qik=})).

Doch $a_{k}$ ist definiert als die Anzahl aller $x\in X$, die $f\left(
x\right)  =k$ erf\"{u}llen. Das hei\ss t,%
\begin{equation}
a_{k}=\left\vert \left\{  x\in X\ \mid\ f\left(  x\right)  =k\right\}
\right\vert . \label{pf.thm.extcomb.chess-amgm-gen-1.prodgeq.pf.3}%
\end{equation}
Jedoch ist leicht einzusehen, dass%
\[
\left\{  x\in X\ \mid\ f\left(  x\right)  =k\right\}  \subseteq Q_{1,k}\times
Q_{2,k}\times\cdots\times Q_{d,k}%
\]
gilt\footnote{\textit{Beweis:} Sei $y\in\left\{  x\in X\ \mid\ f\left(
x\right)  =k\right\}  $. Dann ist $y$ ein $x\in X$ mit der Eigenschaft, dass
$f\left(  x\right)  =k$ gilt. Das hei\ss t, $y\in X$ und $f\left(  y\right)
=k$. Wegen $y\in X=X_{1}\times X_{2}\times\cdots\times X_{d}$ ist $y$ ein
$d$-Tupel; es gilt also $y=\left(  y_{1},y_{2},\ldots,y_{d}\right)  $. F\"{u}r
jedes $i\in\left\{  1,2,\ldots,d\right\}  $ ist%
\begin{align*}
y_{i}  &  \in\left\{  x_{i}\ \mid\ x\in X\text{ und }f\left(  x\right)
=k\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{denn wir haben }y_{i}=x_{i}\text{ f\"{u}r ein }x\in X\text{ mit der
Eigenschaft }f\left(  x\right)  =k\\
\text{(n\"{a}mlich, f\"{u}r }x=y\text{)}%
\end{array}
\right) \\
&  =Q_{i,k}\ \ \ \ \ \ \ \ \ \ \left(  \text{nach der Definition von }%
Q_{i,k}\right)  .
\end{align*}
Das hei\ss t, $\left(  y_{1},y_{2},\ldots,y_{d}\right)  \in Q_{1,k}\times
Q_{2,k}\times\cdots\times Q_{d,k}$. Wegen $y=\left(  y_{1},y_{2},\ldots
,y_{d}\right)  $ l\"{a}\ss t sich dies umschreiben als $y\in Q_{1,k}\times
Q_{2,k}\times\cdots\times Q_{d,k}$.
\par
Vergessen wir nun, dass wir $y$ fixiert haben. Wir haben somit gezeigt, dass
$y\in Q_{1,k}\times Q_{2,k}\times\cdots\times Q_{d,k}$ f\"{u}r jedes
$y\in\left\{  x\in X\ \mid\ f\left(  x\right)  =k\right\}  $ gilt. Das
hei\ss t, wir haben $\left\{  x\in X\ \mid\ f\left(  x\right)  =k\right\}
\subseteq Q_{1,k}\times Q_{2,k}\times\cdots\times Q_{d,k}$.}. Hieraus folgt%
\begin{align*}
\left\vert \left\{  x\in X\ \mid\ f\left(  x\right)  =k\right\}  \right\vert
&  \leq\left\vert Q_{1,k}\times Q_{2,k}\times\cdots\times Q_{d,k}\right\vert
\\
&  =\left\vert Q_{1,k}\right\vert \cdot\left\vert Q_{2,k}\right\vert
\cdot\cdots\cdot\left\vert Q_{d,k}\right\vert =\prod_{i=1}^{d}%
\underbrace{\left\vert Q_{i,k}\right\vert }_{\substack{=q_{i,k}\\\text{(nach
(\ref{pf.thm.extcomb.chess-amgm-gen-1.prodgeq.pf.1}))}}}=\prod_{i=1}%
^{d}q_{i,k}\\
&  =q_{1,k}q_{2,k}\cdots q_{d,k}.
\end{align*}
Somit ist%
\[
q_{1,k}q_{2,k}\cdots q_{d,k}\geq\left\vert \left\{  x\in X\ \mid\ f\left(
x\right)  =k\right\}  \right\vert =a_{k}\ \ \ \ \ \ \ \ \ \ \left(  \text{nach
(\ref{pf.thm.extcomb.chess-amgm-gen-1.prodgeq.pf.3})}\right)  .
\]
Damit ist (\ref{pf.thm.extcomb.chess-amgm-gen-1.prodgeq}) bewiesen.]

Nun wird (\ref{pf.thm.extcomb.chess-amgm-gen-1.sumineq}) zu%
\begin{align}
\sum_{i=1}^{d}\sum_{z\in X_{i}}p_{i,z}  &  \geq d\sum_{k=1}^{n}%
\underbrace{\sqrt[d]{q_{1,k}q_{2,k}\cdots q_{d,k}}}_{\substack{\geq
\sqrt[d]{a_{k}}\\\text{(denn (\ref{pf.thm.extcomb.chess-amgm-gen-1.prodgeq}%
)}\\\text{ergibt }q_{1,k}q_{2,k}\cdots q_{d,k}\geq a_{k}\text{)}}}\geq
d\sum_{k=1}^{n}\sqrt[d]{a_{k}}\nonumber\\
&  =d\left(  \sqrt[d]{a_{1}}+\sqrt[d]{a_{2}}+\cdots+\sqrt[d]{a_{n}}\right)
\label{pf.thm.extcomb.chess-amgm-gen-1.sumineq2}%
\end{align}


Nun kommen wir zum Finale des Beweises: Wir m\"{u}ssen zeigen, dass es ein
$i\in\left\{  1,2,\ldots,d\right\}  $ und ein $z\in X_{i}$ gibt mit der
Eigenschaft, dass
\[
\left\vert \left\{  f\left(  x\right)  \ \mid\ x\in X\text{ und }%
x_{i}=z\right\}  \right\vert \geq C
\]
gilt. Wir beweisen dies durch Widerspruch: Wir nehmen also an, dass es kein
solches Paar gibt. Das hei\ss t, f\"{u}r jedes $i\in\left\{  1,2,\ldots
,d\right\}  $ und jedes $z\in X_{i}$ gilt%
\begin{equation}
\left\vert \left\{  f\left(  x\right)  \ \mid\ x\in X\text{ und }%
x_{i}=z\right\}  \right\vert <C. \label{pf.thm.extcomb.chess-amgm-gen-1.1}%
\end{equation}


Wir haben angenommen, dass die Zahl $\left\vert X_{1}\right\vert +\left\vert
X_{2}\right\vert +\cdots+\left\vert X_{d}\right\vert $ (dies ist der Nenner in
der Definition von $C$) von $0$ verschieden ist. Also ist mindestens eine der
$d$ Mengen $X_{1},X_{2},\ldots,X_{d}$ nichtleer. Das hei\ss t, es gibt
mindestens ein Paar $\left(  i,z\right)  $ mit $i\in\left\{  1,2,\ldots
,d\right\}  $ und $z\in X_{i}$.

F\"{u}r jedes $i\in\left\{  1,2,\ldots,d\right\}  $ und jedes $z\in X_{i}$ ist
aber%
\begin{align}
p_{i,z}  &  =\left\vert \left\{  f\left(  x\right)  \ \mid\ x\in X\text{ und
}x_{i}=z\right\}  \right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{nach der
Definition von }p_{i,z}\right) \nonumber\\
&  <C\ \ \ \ \ \ \ \ \ \ \left(  \text{nach
(\ref{pf.thm.extcomb.chess-amgm-gen-1.1})}\right)  .
\label{pf.thm.extcomb.chess-amgm-gen-1.5}%
\end{align}
Summieren wir diese Ungleichung \"{u}ber alle $i\in\left\{  1,2,\ldots
,d\right\}  $ und alle $z\in X_{i}$ auf, so erhalten wir%
\[
\sum_{i=1}^{d}\sum_{z\in X_{i}}p_{i,z}<\sum_{i=1}^{d}\sum_{z\in X_{i}}C.
\]
(Hierbei haben wir tats\"{a}chlich eine strikte Ungleichung erhalten, denn
unsere Doppelsumme ist nichtleer\footnote{In etwas mehr Detail: Wir haben die
Ungleichung (\ref{pf.thm.extcomb.chess-amgm-gen-1.5}) \"{u}ber alle Paare
$\left(  i,z\right)  $ mit $i\in\left\{  1,2,\ldots,d\right\}  $ und $z\in
X_{i}$ aufsummiert. Da wir wissen, dass es mindestens ein solches Paar gibt,
war dies eine nichtleere Summe. Doch eine nichtleere Summe von strikten
Ungleichungen ist immer eine strikte Ungleichung.}.) Es gilt also%
\begin{align*}
\sum_{i=1}^{d}\sum_{z\in X_{i}}p_{i,z}  &  <\sum_{i=1}^{d}\underbrace{\sum
_{z\in X_{i}}C}_{=\left\vert X_{i}\right\vert C}=\sum_{i=1}^{d}\left\vert
X_{i}\right\vert C=\left(  \left\vert X_{1}\right\vert +\left\vert
X_{2}\right\vert +\cdots+\left\vert X_{d}\right\vert \right)  C\\
&  =d\left(  \sqrt[d]{a_{1}}+\sqrt[d]{a_{2}}+\cdots+\sqrt[d]{a_{n}}\right)
\end{align*}
(denn $C=\dfrac{d\left(  \sqrt[d]{a_{1}}+\sqrt[d]{a_{2}}+\cdots+\sqrt[d]%
{a_{n}}\right)  }{\left\vert X_{1}\right\vert +\left\vert X_{2}\right\vert
+\cdots+\left\vert X_{d}\right\vert }$). Dies steht im Widerspruch zu
(\ref{pf.thm.extcomb.chess-amgm-gen-1.sumineq2}). Damit ist der gew\"{u}nschte
Widerspruch erhalten; Satz \ref{thm.extcomb.chess-amgm-gen-1} ist also bewiesen.
\end{proof}

Warum ist Satz \ref{thm.extcomb.chess-amgm-gen-1} eine Verallgemeinerung von
Beispiel \ref{exa.chess-amgm}? Um dies einzusehen, betrachten wir ein $n\times
n$-Schachbrett, welches (gem\"{a}\ss \ den Bedingungen von Beispiel
\ref{exa.chess-amgm}) mit Zahlen gef\"{u}llt wurde. Wir setzen $d=2$ und
$X_{1}=\left\{  1,2,\ldots,n\right\}  $ und $X_{2}=\left\{  1,2,\ldots
,n\right\}  $. Dann ist $X=X_{1}\times X_{2}$. Sei nun $f:X\rightarrow\left\{
1,2,\ldots,n\right\}  $ die Abbildung, die jedes Paar $\left(  i,j\right)  \in
X_{1}\times X_{2}$ \"{u}berf\"{u}hrt in den Eintrag in der $i$-ten Zeile und
der $j$-ten Spalte dieses $n\times n$-Schachbretts. Laut den Bedingungen von
Beispiel \ref{exa.chess-amgm} steht jede der $n$ Zahlen $1,2,\ldots,n$ in
genau $n$ Feldern des $n\times n$-Schachbretts; das hei\ss t, f\"{u}r jedes
$j\in\left\{  1,2,\ldots,n\right\}  $ gibt es genau $n$ verschiedene $x\in X$,
die $f\left(  x\right)  =j$ erf\"{u}llen. Die in Satz
\ref{thm.extcomb.chess-amgm-gen-1} definierten Zahlen $a_{1},a_{2}%
,\ldots,a_{n}$ sind also alle gleich $n$. Die in Satz
\ref{thm.extcomb.chess-amgm-gen-1} definierte Zahl $C$ ist damit gleich%
\begin{align*}
C  &  =\dfrac{2\left(  \sqrt[2]{n}+\sqrt[2]{n}+\cdots+\sqrt[2]{n}\right)
}{n+n}\ \ \ \ \ \ \ \ \ \ \left(  \text{wobei im Z\"{a}hler genau }n\text{
Wurzeln stehen}\right) \\
&  =\dfrac{2n\sqrt[2]{n}}{n+n}=\sqrt[2]{n}=\sqrt{n}.
\end{align*}
Satz \ref{thm.extcomb.chess-amgm-gen-1} behauptet also, dass es ein
$i\in\left\{  1,2,\ldots,d\right\}  $ und ein $z\in X_{i}$ gibt mit der
Eigenschaft, dass
\[
\left\vert \left\{  f\left(  x\right)  \ \mid\ x\in X\text{ und }%
x_{i}=z\right\}  \right\vert \geq\sqrt{n}%
\]
gilt. Das hei\ss t, es gibt mindestens eine Zeile oder Spalte des
Schachbretts, die mindestens $\sqrt{n}$ verschiedene Zahlen enth\"{a}lt (und
zwar ist es die $z$-te Zeile, wenn $i=1$ ist, und es ist die $z$-te Spalte,
wenn $i=2$ ist). Daher folgt Beispiel \ref{exa.chess-amgm} aus Satz
\ref{thm.extcomb.chess-amgm-gen-1}. Wir haben mit Satz
\ref{thm.extcomb.chess-amgm-gen-1} also tats\"{a}chlich Beispiel
\ref{exa.chess-amgm} verallgemeinert.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.a/b-sum-3}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.a/b-sum-3}.]Satz \ref{thm.3abc} \textbf{(b)}
(angewandt auf $\dfrac{a}{b},\dfrac{b}{c},\dfrac{c}{a}$ statt $a,b,c$) ergibt%
\begin{align*}
\dfrac{a}{b}+\dfrac{b}{c}+\dfrac{c}{a}  &  \geq3\sqrt[3]{\dfrac{a}{b}%
\cdot\dfrac{b}{c}\cdot\dfrac{c}{a}}=3\sqrt[3]{1}\ \ \ \ \ \ \ \ \ \ \left(
\text{denn }\dfrac{a}{b}\cdot\dfrac{b}{c}\cdot\dfrac{c}{a}=1\right) \\
&  =3.
\end{align*}
Damit ist Aufgabe \ref{exe.a/b-sum-3} gel\"{o}st.
\end{proof}

Es sei angemerkt, dass sich Aufgabe \ref{exe.a/b-sum-3} leicht auf $n$
positive reelle Zahlen verallgemeinern l\"{a}\ss t. (F\"{u}r die L\"{o}sung
braucht man dann nat\"{u}rlich Satz \ref{thm.am-gm} \textbf{(b)}.)

\subsubsection{zu Aufgabe \ref{exe.hung.sumab(b+c)}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.hung.sumab(b+c)}.]Satz \ref{thm.3abc}
\textbf{(b)} (angewandt auf $ab^{2},bc^{2},ca^{2}$ statt $a,b,c$) ergibt%
\begin{align}
ab^{2}+bc^{2}+ca^{2}  &  \geq3\sqrt[3]{ab^{2}\cdot bc^{2}\cdot ca^{2}%
}\nonumber\\
&  =3\sqrt[3]{a^{3}b^{3}c^{3}}\ \ \ \ \ \ \ \ \ \ \left(  \text{denn }%
ab^{2}\cdot bc^{2}\cdot ca^{2}=a^{3}b^{3}c^{3}\right) \nonumber\\
&  =3abc. \label{sol.hung.sumab(b+c).1st.1}%
\end{align}
Satz \ref{thm.3abc} \textbf{(b)} (angewandt auf $a^{2}b,b^{2}c,c^{2}a$ statt
$a,b,c$) ergibt%
\begin{align}
a^{2}b+b^{2}c+c^{2}a  &  \geq3\sqrt[3]{a^{2}b\cdot b^{2}c\cdot c^{2}%
a}\nonumber\\
&  =3\sqrt[3]{a^{3}b^{3}c^{3}}\ \ \ \ \ \ \ \ \ \ \left(  \text{denn }%
a^{2}b\cdot b^{2}c\cdot c^{2}a=a^{3}b^{3}c^{3}\right) \nonumber\\
&  =3abc. \label{sol.hung.sumab(b+c).1st.2}%
\end{align}
Nun sieht man aber durch blinde Nachrechnung, dass%
\begin{align*}
&  \dfrac{2}{9}\left(  a+b+c\right)  ^{3}-\left(  ab\left(  b+c\right)
+bc\left(  c+a\right)  +ca\left(  a+b\right)  \right) \\
&  =\dfrac{2}{9}\left(  b\underbrace{\left(  a-b\right)  ^{2}}_{\substack{\geq
0\\\text{(nach Satz \ref{thm.xsquare})}}}+c\underbrace{\left(  b-c\right)
^{2}}_{\substack{\geq0\\\text{(nach Satz \ref{thm.xsquare})}}%
}+a\underbrace{\left(  c-a\right)  ^{2}}_{\substack{\geq0\\\text{(nach Satz
\ref{thm.xsquare})}}}\right) \\
&  \ \ \ \ \ \ \ \ \ \ +\dfrac{4}{9}\underbrace{\left(  a^{2}b+b^{2}%
c+c^{2}a-3abc\right)  }_{\substack{\geq0\\\text{(nach
(\ref{sol.hung.sumab(b+c).1st.2}))}}}+\dfrac{1}{9}\underbrace{\left(
ab^{2}+bc^{2}+ca^{2}-3abc\right)  }_{\substack{\geq0\\\text{(nach
(\ref{sol.hung.sumab(b+c).1st.1}))}}}\\
&  \geq\dfrac{2}{9}\left(  b\cdot0+c\cdot0+a\cdot0\right)  +\dfrac{4}{9}%
\cdot0+\dfrac{1}{9}\cdot0=0
\end{align*}
gilt. Also ist%
\[
ab\left(  b+c\right)  +bc\left(  c+a\right)  +ca\left(  a+b\right)  \leq
\dfrac{2}{9}\left(  a+b+c\right)  ^{3}.
\]
Damit ist Aufgabe \ref{exe.hung.sumab(b+c)} gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.mse192763}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.mse192763}.]Wir haben%
\[
a+b+c+d+e+f=\left(  a+d\right)  +\left(  b+e\right)  +\left(  c+f\right)
\geq3\sqrt[3]{\left(  a+d\right)  \left(  b+e\right)  \left(  c+f\right)  }%
\]
(nach Satz \ref{thm.3abc} \textbf{(b)}, angewandt auf $a+d,b+e,c+f$ statt
$a,b,c$). Nehmen wir beide Seiten dieser Ungleichung in die $3$-te Potenz, so
erhalten wir%
\begin{align*}
&  \left(  a+b+c+d+e+f\right)  ^{3}\\
&  \geq\left(  3\sqrt[3]{\left(  a+d\right)  \left(  b+e\right)  \left(
c+f\right)  }\right)  ^{3}=27\underbrace{\left(  a+d\right)  \left(
b+e\right)  \left(  c+f\right)  }_{=abc+bcd+cde+def+efa+fab+ace+bdf}\\
&  =27\left(  abc+bcd+cde+def+efa+fab+\underbrace{ace}_{\geq0}%
+\underbrace{bdf}_{\geq0}\right) \\
&  \geq27\left(  abc+bcd+cde+def+efa+fab\right)  .
\end{align*}
Dividieren wir diese Ungleichung durch $27$, so erhalten wir%
\[
\dfrac{1}{27}\left(  a+b+c+d+e+f\right)  ^{3}\geq abc+bcd+cde+def+efa+fab.
\]
Damit ist Aufgabe \ref{exe.mse192763} gel\"{o}st.
\end{proof}

\subsubsection{zu Aufgabe \ref{exe.holder.proof-by-young}}

\begin{proof}
[L\"{o}sung zu Aufgabe \ref{exe.holder.proof-by-young}.]Dies ist \"{a}hnlich
zu unserer obigen L\"{o}sung zu Aufgabe \ref{exe.cs.proof-by-amgm}, aber
einfacher, da die Zahlen $a_{1},a_{2},\ldots,a_{n}$ sowie $b_{1},b_{2}%
,\ldots,b_{n}$ nunmehr als nichtnegativ vorausgesetzt werden.

\begin{proof}
[Beweis von Satz \ref{thm.holder}.]Wir definieren zwei nichtnegative reelle
Zahlen
\[
A=\sqrt[p]{a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}}\ \ \ \ \ \ \ \ \ \ \text{und}%
\ \ \ \ \ \ \ \ \ \ B=\sqrt[q]{b_{1}^{q}+b_{2}^{q}+\cdots+b_{n}^{q}}.
\]
Nach der Definition von $A$ gilt
\begin{equation}
A^{p}=a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}=\sum_{i=1}^{n}a_{i}^{p}.
\label{sol.holder.proof-by-young.Ap=}%
\end{equation}
Nach der Definition von $B$ gilt
\begin{equation}
B^{q}=b_{1}^{q}+b_{2}^{q}+\cdots+b_{n}^{q}=\sum_{i=1}^{n}b_{i}^{q}.
\label{sol.holder.proof-by-young.Bq=}%
\end{equation}


Wir m\"{u}ssen zeigen, dass
\[
\sqrt[p]{a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}}\cdot\sqrt[q]{b_{1}^{q}%
+b_{2}^{q}+\cdots+b_{n}^{q}}\geq a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}%
\]
gilt. Wegen $A=\sqrt[p]{a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}}$ und
$B=\sqrt[q]{b_{1}^{q}+b_{2}^{q}+\cdots+b_{n}^{q}}$ k\"{o}nnen wir dies
folgenderma\ss en umformulieren: Wir m\"{u}ssen zeigen, dass
\begin{equation}
AB\geq a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}
\label{sol.holder.proof-by-young.goal2}%
\end{equation}
gilt. Wenn alle $n$ Zahlen $a_{1},a_{2},\ldots,a_{n}$ gleich $0$ sind, dann
ist (\ref{sol.holder.proof-by-young.goal2}) leicht zu
beweisen\footnote{\textit{Beweis:} Wir nehmen an, dass alle $n$ Zahlen
$a_{1},a_{2},\ldots,a_{n}$ gleich $0$ sind. Nun ist
\begin{align*}
A  &  =\sqrt[p]{a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}}\\
&  =\sqrt[p]{0^{p}+0^{p}+\cdots+0^{p}}\ \ \ \ \ \ \ \ \ \ \left(  \text{denn
alle }n\text{ Zahlen }a_{1},a_{2},\ldots,a_{n}\text{ sind gleich }0\right) \\
&  =0,
\end{align*}
also $AB=0B=0$. Ferner ist%
\begin{align*}
&  a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}\\
&  =0b_{1}+0b_{2}+\cdots+0b_{n}\ \ \ \ \ \ \ \ \ \ \left(  \text{denn alle
}n\text{ Zahlen }a_{1},a_{2},\ldots,a_{n}\text{ sind gleich }0\right) \\
&  =0.
\end{align*}
Somit sind beide Seiten der Ungleichung (\ref{sol.holder.proof-by-young.goal2}%
) gleich $0$. Die Ungleichung (\ref{sol.holder.proof-by-young.goal2}) ist
damit erf\"{u}llt (denn $0\geq0$).}. Wir nehmen also o. B. d. A. an, dass
nicht alle $n$ Zahlen $a_{1},a_{2},\ldots,a_{n}$ gleich $0$ sind. Mit
derselben Begr\"{u}ndung nehmen wir o. B. d. A. an, dass nicht alle $n$ Zahlen
$b_{1},b_{2},\ldots,b_{n}$ gleich $0$ sind.

Die Zahlen $A$ und $B$ sind positiv\footnote{\textit{Beweis:} Die $n$ Zahlen
$a_{1},a_{2},\ldots,a_{n}$ sind nichtnegativ, und mindestens eine von ihnen
ist positiv (denn nicht alle $n$ Zahlen $a_{1},a_{2},\ldots,a_{n}$ sind gleich
$0$; aber sie sind alle nichtnegativ). Somit gilt das gleiche f\"{u}r ihre
$p$-ten Potenzen. Das hei\ss t, die $n$ Zahlen $a_{1}^{p},a_{2}^{p}%
,\ldots,a_{n}^{p}$ sind nichtnegativ, und mindestens eine von ihnen ist
positiv. Daher ist die Summe $a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}$ dieser $n$
Zahlen positiv. Also ist auch die $p$-te Wurzel $\sqrt[p]{a_{1}^{p}+a_{2}%
^{p}+\cdots+a_{n}^{p}}$ dieser Summe positiv. Mit anderen Worten: $A$ ist
positiv (denn $A=\sqrt[p]{a_{1}^{p}+a_{2}^{p}+\cdots+a_{n}^{p}}$). Ein
analoges Argument zeigt, dass $B$ positiv ist.}. F\"{u}r jedes $i\in\left\{
1,2,\ldots,n\right\}  $ gilt also%
\[
\dfrac{\left(  a_{i}/A\right)  ^{p}}{p}+\dfrac{\left(  b_{i}/B\right)  ^{q}%
}{q}\geq\left(  a_{i}/A\right)  \left(  b_{i}/B\right)  .
\]
(nach Satz \ref{thm.young}, angewandt auf $a=a_{i}/A$ und $b=b_{i}/B$).
Summieren wir diese Ungleichung \"{u}ber alle $i\in\left\{  1,2,\ldots
,n\right\}  $ auf, so erhalten wir%
\[
\sum_{i=1}^{n}\left(  \dfrac{\left(  a_{i}/A\right)  ^{p}}{p}+\dfrac{\left(
b_{i}/B\right)  ^{q}}{q}\right)  \geq\sum_{i=1}^{n}\left(  a_{i}/A\right)
\left(  b_{i}/B\right)  .
\]
Wegen%
\begin{align*}
\sum_{i=1}^{n}\left(  \dfrac{\left(  a_{i}/A\right)  ^{p}}{p}+\dfrac{\left(
b_{i}/B\right)  ^{q}}{q}\right)   &  =\sum_{i=1}^{n}\dfrac{\left(
a_{i}/A\right)  ^{p}}{p}+\sum_{i=1}^{n}\dfrac{\left(  b_{i}/B\right)  ^{q}}%
{q}\\
&  =\dfrac{1}{p}\sum_{i=1}^{n}\underbrace{\left(  a_{i}/A\right)  ^{p}%
}_{=a_{i}^{p}/A^{p}}+\dfrac{1}{q}\sum_{i=1}^{n}\underbrace{\left(
b_{i}/B\right)  ^{q}}_{=b_{i}^{q}/B^{q}}\\
&  =\dfrac{1}{p}\underbrace{\sum_{i=1}^{n}a_{i}^{p}/A^{p}}_{\substack{=\left(
\sum_{i=1}^{n}a_{i}^{p}\right)  /A^{p}=1\\\text{(nach
(\ref{sol.holder.proof-by-young.Ap=}))}}}+\dfrac{1}{q}\underbrace{\sum
_{i=1}^{n}b_{i}^{q}/B^{q}}_{\substack{=\left(  \sum_{i=1}^{n}b_{i}^{q}\right)
/B^{q}=1\\\text{(nach (\ref{sol.holder.proof-by-young.Bq=}))}}}\\
&  =\dfrac{1}{p}+\dfrac{1}{q}=1
\end{align*}
und%
\[
\sum_{i=1}^{n}\left(  a_{i}/A\right)  \left(  b_{i}/B\right)  =\left(
\sum_{i=1}^{n}a_{i}b_{i}\right)  /\left(  AB\right)
\]
l\"{a}\ss t sich dies umschreiben als%
\[
1\geq\left(  \sum_{i=1}^{n}a_{i}b_{i}\right)  /\left(  AB\right)  .
\]
Da $AB$ positiv ist (denn $A$ und $B$ sind positiv), k\"{o}nnen wir diese
Ungleichung mit $AB$ multiplizieren; dadurch erhalten wir%
\[
AB\geq\sum_{i=1}^{n}a_{i}b_{i}=a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}.
\]
Damit ist (\ref{sol.holder.proof-by-young.goal2}) bewiesen. Wie schon gesagt,
ist damit Satz \ref{thm.holder} bewiesen.
\end{proof}

Aufgabe \ref{exe.holder.proof-by-young} ist damit gel\"{o}st.
\end{proof}

\newpage

\bigskip

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[AleKur91]{AleKur91}P. Alekseev, L. Kurlyandchik, \textit{Summa
minimumov i minimum summy}, Kvant 1991/3, pp. 49--55.\newline\url{http://kvant.mccme.ru/1991/03/summa_minimumov_i_minimum_summ.htm}

\bibitem[AndDos10]{AndDos}\href{https://bookstore.ams.org/xyz-13}{Titu
Andreescu, Gabriel Dospinescu, \textit{Problems from the Book}, 2nd edition,
XYZ Press 2010}.

\bibitem[AndDos12]{AndDosS}\href{https://bookstore.ams.org/xyz-6}{Titu
Andreescu, Gabriel Dospinescu, \textit{Straight from the Book}, XYZ Press
2012}.

\bibitem[Bosch20]{Bosch20}%
\href{https://doi.org/10.1007/978-3-662-61649-9}{Siegfried Bosch,
\textit{Algebra}, 9te Auflage, Springer 2020}.

\bibitem[Brande05]{Brande05}Martin Brandenburg (Martin\_Infinite),
\textit{Symmetrische Polynome}, 14.2.2005, Matheplanet.\newline\url{https://matheplanet.com/matheplanet/nuke/html/article.php?sid=738}

\bibitem[Chen20]{ChenEvan}Evan Chen, \textit{various notes and problem
collections on mathematical olympiads}, \url{https://web.evanchen.cc/} .

\bibitem[Cirtoa06]{Cirtoa06}%
\href{https://cut-the-knot.org/arithmetic/algebra/VasileCirtoaje.pdf}{Vasile
Cirtoaje, \textit{Algebraic inequalities: old and new methods}, Gil, Zal\u{a}u
2006}.

\bibitem[Conlon11]{Conlon11}David Conlon, \textit{Extremal graph theory},
2011.\newline\url{https://www.its.caltech.edu/~dconlon/Extremal-course.html}

\bibitem[DJMP11]{IMOcomp}%
\href{http://mathksar.weebly.com/uploads/1/4/4/0/14403348/the-imo-compendium-1959_2009.pdf}{Dusan
Djukic, Vladimir Jankovic, Ivan Matic, Nikola Petrovic, \textit{The IMO
Compendium: A Collection of Problems Suggested for The International
Mathematical Olympiads: 1959-2009}, 2nd edition, Springer 2011}.\newline See
\url{https://www.imomath.com/index.php?options=350&lmm=0} for errata.

\bibitem[Edward05]{Edwards-Essays}%
\href{https://doi.org/10.1007/b138656}{Harold M. Edwards, \textit{Essays in
Constructive Mathematics}, Springer 2005}.

\bibitem[Geissi05]{Geissi05}Christoph Gei\ss inger, \textit{Artikel 10:
Ungleichungen}, in: Richard Bamler, Christian Reiher et al., \textit{Ein-Blick
in die Mathematik}, Aulis Verlag Deubner, K\"{o}ln 2005.

\bibitem[GelAnd17]{GelAnd}%
\href{https://doi.org/10.1007/978-3-319-58988-6}{R\u{a}zvan Gelca, Titu
Andreescu, \textit{Putnam and Beyond}, 2nd edition, Springer 2017}.

\bibitem[Grinbe07]{Grinbe-vor-schur}Darij Grinberg, \textit{The Vornicu-Schur
inequality and its variations}, 13 August 2007.\newline\url{http://www.cip.ifi.lmu.de/~grinberg/VornicuS.pdf}

\bibitem[Hung07]{Hung07}%
\href{http://refkol.ro/matek/mathbooks/!Books!/Secrets in Inequalities (volume 1) Pham Kim Hung.pdf}{Pham
Kim Hung, \textit{Secrets in Inequalities, volume 1}, GIL 2007}.

\bibitem[Jainta02]{Jainta02}Paul Jainta, $\sqrt{\text{\textit{WURZEL}}}%
$\textit{-Werkstatt Mathematik: Polynome -- Teil V: Elementarsymmetrische
Polynome}, WURZEL ca. 2002.\newline\url{http://www.wurzel.org/werkstatt/polynome5.pdf}

\bibitem[Kerber04]{Kerber04}Adalbert Kerber, \textit{Lineare Algebra, WS
2002/2003}, 4. Oktober 2004.\newline\url{http://www.mathe2.uni-bayreuth.de/lina02/alles.pdf}

\bibitem[Khrabr03]{Khrabr03}Alexander I. Khrabrov, \textit{I snova neravenstvo
Cauchy--Bunyakovskogo (Cauchy--Bunyakovsky inequality)} (Russian), Appendix
to: St Petersburg mathematical olympiad, 2003. Nevsky Dialekt, St Petersburg,
2003, pp. 118--152.\newline\url{http://www.aikhrabrov.narod.ru/papers/cbs.zip}

\bibitem[Lee07]{Lee07}Hojoo Lee, \textit{Topics in Inequalities: Theorems and
Techniques}, 8 August 2007.\newline\url{https://www.isinj.com/mt-usamo/Topics in Inequalities 1st edition - Hojoo Lee (2007).pdf}

\bibitem[Lehn15]{Lehn15}Manfred Lehn, \textit{Vorlesungen \"{u}ber Algebra:
Wintersemester 2015}, 10. Dezember 2015.\newline\url{https://download.uni-mainz.de/mathematik/Topologie und Geometrie/Lehre/WS 15-16/Algebra 1/Vorlesungstext.pdf}

\bibitem[LeLoPo08]{infinity}Hojoo Lee, Tom Lovering, and Cosmin Pohoata,
\textit{Infinity}, 19 October 2008.\newline\url{http://prac.im.pwr.wroc.pl/~kwasnicki/pl/o/infinity.pdf}

\bibitem[Lin12]{Lin12}\href{https://doi.org/10.1007/s00283-012-9292-1}{Minghua
Lin, \textit{The AM-GM Inequality and CBS Inequality Are Equivalent}, The
Mathematical Intelligencer \textbf{34} (2012), p. 6}.

\bibitem[Mildor06]{Mildor06}Thomas J. Mildorf, \textit{Olympiad Inequalities},
4 August 2006.\newline\url{https://www.isinj.com/mt-usamo/Olympiad Inequalities - Thomas Mildorf (2006).pdf}

\bibitem[Rollin16]{Rollin16}Jonathan Rollin, \textit{KIT Summer Term 2016,
Extremal graph theory: Solutions to problem sheet 1}, 2016.\newline%
\url{https://www.math.kit.edu/iag6/lehre/extremalgt2016s/media/01-solution.pdf}\newline
Teil von einem Kurs von Maria Axenovich; siehe
\url{https://www.math.kit.edu/iag6/lehre/extremalgt2016s} f\"{u}r den gesamten Kurs.

\bibitem[ShChYa62]{ShChYa62}%
\href{https://www.isinj.com/mt-usamo/USSR Olympiad Problem Book (The) - Shklasrsky, Chentzov, and Yaglom (1993, Dover) (1-1).pdf}{David
Oskarovich Shklarsky, Nikolai Nikolaevich Chentzov, Isaak Moiseevich Yaglom,
\textit{The USSR Olympiad Problem Book}, Freeman 1962 (reprinted by Dover
1993)}.

\bibitem[SpQuBa20]{SpQuBa20}%
\href{https://doi.org/10.1007/978-3-662-61166-1}{Eckard Specht, Erhard
Quaisser, Patrick Bauermann, \textit{50 Jahre Bundeswettbewerb Mathematik: Die
sch\"{o}nsten Aufgaben}, 2te Auflage, Springer 2020}.

\bibitem[Steele04]{Steele04}%
\href{http://www.ma.huji.ac.il/~ehudf/courses/Ineq09/The Cauchy-Schwarz Master Class .pdf}{J.
Michael Steele, \textit{The Cauchy--Schwarz Master Class: An Introduction to
the Art of Mathematical Inequalities}, Cambridge University Press
2004}.\newline Siehe
\url{http://www-stat.wharton.upenn.edu/~steele/Publications/Books/CSMC/CSMC_Errata.pdf}
f\"{u}r Errata.

\bibitem[Swanso20]{Swanso20}Irene Swanson, \textit{Introduction with Analysis
with Complex Numbers}, 2020.\newline\url{https://web.archive.org/web/20201012174324/https://people.reed.edu/~iswanson/analysisconstructR.pdf}

\bibitem[YagYag64]{YagYag64}Akiva M.\ Yaglom, Isaac M. Yaglom,
\textit{Challenging Mathematical Problems with Elementary Solutions, volume I:
Combinatorial Analysis and Probability Theory}, Holden-Day 1964 (reprinted by
Dover 1987).

\bibitem[YagYag67]{YagYag67}Akiva M.\ Yaglom, Isaac M. Yaglom,
\textit{Challenging Mathematical Problems with Elementary Solutions, volume
II: Problems from Various Branches of Mathematics}, Holden-Day 1967 (reprinted
by Dover 1987).

\bibitem[ZawHit09]{ZawHit09}%
\href{https://darithmathblog.files.wordpress.com/2017/04/a-primer-for-math-competition.pdf}{Alexander
Zawaira, Gavin Hitchcock, \textit{A Primer for Mathematics Competitions},
Oxford University Press 2009}.

\bibitem[Zeitz17]{Zeitz17}Paul Zeitz, \textit{The Art and Craft of Problem
Solving}, 3rd edition, Wiley 2017.

\bibitem[Zhao20]{Zhao}Yufei Zhao, \textit{Math Olympiad training handouts},
\url{https://yufeizhao.com/olympiad/} .
\end{thebibliography}


\end{document}