Manfred Börgens - Problem 69 - Hinweis 2

Im Fall  m = n/2 + 1  muss  n/2  ungerade sein. Zwei  m - Abschnitte überlappen sich in der Mitte mit zwei Perlen. Diese sind entweder gleichfarbig oder nicht. In beiden Fällen kann man den "Zwischenwertsatz" aus dem ersten Hinweis anwenden.

In den Fällen  m = 4 ,  6 ,  8  beschränkt man sich auf die Fälle, in denen nicht  m | n  gilt. Dann lässt sich die  n - Kette in mehrere disjunkte  m - Abschnitte und einen kleineren  h - Abschnitt einteilen (der in meiner Lösung immer an zweiter Stelle steht, aber das ist willkürlich gewählt). Enthält dieser  h/2  weiße Perlen, lässt sich wieder der Zwischenwertsatz (s.o.) anwenden. Ansonsten nimmt man (o.E.) an, dass er mehr schwarze Perlen enthält. Z.B. sind für  m = 6  die Fälle  h = 2  (mit  2  schwarzen Perlen) und  h = 4  (mit  3  oder  4  schwarzen Perlen) zu untersuchen. Die Kompatibilität lässt sich dann entweder mit dem Zwischenwertsatz zeigen oder durch Ausschneiden eines passenden  m - Abschnitts aus den ersten  m + h  Perlen (hier kann ein Programm helfen).

Manfred Börgens - Problem 69 - Hinweis 2

Publiziert 2009-11-30          Stand 2009-08-10

zurück zu Problem 69                   zur Leitseite