0 Daumen
128 Aufrufe

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community