Sortieren und Nachbarn vergleichen

Stell dir sortierte Punkte vor: Ein nichtbenachbarter Abstand ist die Summe positiver Nachbarlücken – er kann nicht kleiner als alle sein.

Die Summe der Nachbarlücken ist $x_n-x_1$. Minimum und Maximum der Lücken liegen auf verschiedenen Seiten ihres Durchschnitts.

Idee: Eine nicht aufsteigende Folge hat eine benachbarte Inversion – ihr Tausch senkt die Inversionszahl.

Viele Punkte in einer beschränkten Strecke erzwingen eine kleine Nachbarlücke – Intervalle werden Schubfächer.

Eine nichtnegative ganzzahlige Inversionszahl kann nicht unbegrenzt sinken – der Prozess endet.