Erreichbarkeit zwischen Städten/Aufgabe/2/Lösung

Es soll ${}n\in \mathbb {N}$ Städte geben. Davon betrachten wir zunächst die Stadt ${}S_{1}$, von der man aus die Städte ${}S_{2},S_{3},...,S_{n-k}$ (${}k\in \mathbb {N}$ und ${}k\geq 2$) erreichen kann. Angenommen man kann aber von all diesen Städten nicht zu den restlichen Städten ${}S_{n-k+1},S_{n-k+2},...,S_{n}$ gelangen, dann folgt die Umkehrung: die Städte ${}S_{1},S_{2},...,S_{n-k}$ sind von den Städten ${}S_{n-k+1},S_{n-k+2},...,S_{n}$ aus erreichbar. Somit verbleiben die Städte ${}S_{n-k+1},S_{n-k+2},...,S_{n}$ als mögliche Kandidaten, die die Behauptung erfüllen könnten.

Verfolgt man nun die gleiche Argumentation, wie im Falle von Stadt ${}S_{1}$, für die Stadt ${}S_{n-k+1}$ (von ${}S_{n-k+1}$ sind die Städte ${}S_{n-k+2},S_{n-k+3},...,S_{n-k+m}$ (mit ${}m\in \mathbb {N}$ und

${}m\geq 2$) erreichbar) verkleinert man die Anzahl der möglichen Kandidaten weiter: ${}S_{n-k+m+1},S_{n-k+m+2},...,S_{n}$. Dies kann man soweit führen, bis nur noch die zwei Städte ${}S_{n-1}$ und ${}S_{n}$ als mögliche Kandidaten übrig bleiben. Da man entweder von ${}S_{n-1}$ nach ${}S_{n}$ oder andersrum gelangen kann, erfüllt einer der beiden Städte auf jeden Fall die Behauptung.

Zur gelösten Aufgabe

[[Kategorie:Erreichbarkeit zwischen Städten/Aufgabe/2/Lösungen]]

[[Kategorie:Erreichbarkeit zwischen Städten/Aufgabe/2/Lösungen]]