Aufgabe:
Beweisen Sie:
Eine Liste der Länge n sei mit k Farben gültig gefärbt. Dann bilden die lokalen Minima der Farben eine
unabhängige Menge der Größe mindestens n/(2k −2)−1.
Zeigen Sie, dass je 2k −2 aufeinander folgende Listenelemente die Farbe
0 enthalten müssen.
Problem/Ansatz:
Habe folgenden ähnlichen Beweis:
Beweisen Sie: Eine Liste der Länge n sei mit k Farben gültig gefärbt. Dann bilden die lokalen Minima der Farben eine
unabhängige Menge der Größe mindestens (n/2k)−1.
Zeigen Sie, dass je 2k aufeinander folgende Listenelemente mindestens ein lokales Minimum enthalten müssen. Die
−1 wird für den Rand gebraucht.
Seien die Farben x[1], .., x[2k]
Widerspruchsbeweis: Annahme: 2k aufeinander folgende Listenelemente enthalten kein lokales Minimum.
Dann gibt es kein i (für 1 < i < 2k) mit x[i - 1] > x[i] < x[i + 1]
Also gilt für alle i: x[i - 1] < x[i] < x[i + 1],
x[i - 1] > x[i] > x[i + 1], oder
x[i - 1] < x[i] > x[i + 1]
Setze i = k.
Im ersten Fall folgt aus x[k - 1] < x[k] < x[k + 1] auch x[k - 2] < x[k - 1] < x[k] < x[k + 1], sonst wäre k - 1 ein lokales Minimum. Rekursiv folgt also x[1] < x[2] < ... < x[k] < x[k + 1].
Das sind k + 1 Elemente, die unterschiedliche Farben haben, aber es gibt nur k Farben. Widerspruch!
Im zweiten Fall folgt analog: x[k - 1] > x[k] > x[k + 1] > ... > x[2k] und derselbe Widerspruch.
Im letzten Fall folgt: x[1] < x[2] < ... < x[k]
Das sind k Elemente, also x[1] = 0, .., x[k] = k - 1
Da x[k] != x[k+1] und x[k+1] <= k, folgt x[k] > x[k + 1], also x[k] > x[k + 1] > .. > x[2k]
Das sind k + 1 Element, also x[k] = k - 1, x[k + 1] = k - 2, .., x[2k] = k - 1 - k = -1.
Widerspruch!
Wie kann man diesen richtig für den obigen Beweis umwandeln, jemand eine Idee?
Sehe beim Beispiel auch nicht so ganz den Beweis für mindestens (n/2k)−1.
