Manfred Börgens
Mathematische Probleme  # 69
Liste aller Probleme mit Lösungen
voriges Problem      nächstes Problem
zur Leitseite


Ein Kettenproblem


Eine Kette hat  n  Perlen, die je zur Hälfte weiß und schwarz sind. Die Kette kann geschlossen oder offen sein, so wie im folgenden Bild:

Ketten


Aus der Kette soll ein zusammenhängendes Teilstück der Länge  m  geschnitten werden, in dem ebenfalls gleich viele weiße und schwarze Perlen sind. Es stellt sich die Frage, ob das immer geht. Durch Ausprobieren erhält man schnell Gegenbeispiele, z.B.  n = 12 ,  m = 8  für die offene Kette (schreibt man weiße Perlen als  0  und schwarze als  1 , so lässt sich aus der Kette  000111111000  kein Teilstück der Länge  8  schneiden, das je vier weiße und schwarze Perlen enthält).

Wir wollen nun das Problem präzise formulieren.  n  und  m  sollen gerade Zahlen sein mit  2  m < n . Eine Kette (geschlossen oder offen) soll  n/2  weiße und  n/2  schwarze Perlen enthalten; dabei ist jede Reihenfolge möglich. Das Zahlenpaar (n,m) soll kompatibel heißen, wenn zu jeder Kette der Länge  n  (n - Kette) ein Teilabschnitt der Länge  m  (m - Abschnitt) existiert, in dem jeweils  m/2  weiße und schwarze Perlen sind. Nicht kompatible Paare (n,m) nennen wir inkompatibel.

Im einfachsten Fall der offenen Kette ist  m = n/2 . Dann kann man die  n - Kette in zwei disjunkte  m - Abschnitte einteilen, und darin liegt auch schon die Beweisidee für (n,m) kompatibel. Das kann man zunächst an kleinen Beispielen wie (n,m) = (8,4) ausprobieren. Eine naheliegende Verallgemeinerung ist dann die Kompatibiltät bei  m | n  ( m  ist Teiler von  n ). Wer hierzu einen Tipp haben möchte, kann den Hinweis lesen. Was man aus diesem einfachen Fall lernt, lässt sich mit kleinen Modifikationen auf die folgenden Aussagen anwenden, die bewiesen werden sollen :

Sei nun die Kette offen.
In den folgenden Fällen ist (n,m) ein kompatibles Paar : Im folgenden Fall ist (n,m) ein inkompatibles Paar : Man kann sich also bei weiteren Überlegungen auf  m < n/2  beschränken. Dafür gilt, dass (n,m) in den folgenden Fällen kompatibel ist : Mit diesen Resultaten findet man dann recht schnell inkompatible Paare (n,m) wie z.B. (n,m) = (12,8) (siehe oben) oder mit  m = 10 < n/2 . Es empfiehlt sich aber, ein kleines Programm zu schreiben, das die Permutationen der Kettenelemente und die  m - Abschnitte überprüft. (Auch für den Fall  m = 8 < n/2 , in dem die Kompatibilität gezeigt werden soll, lassen sich zwar mit vertretbarem Aufwand die möglichen Fälle von Hand darstellen, aber der Rechner ist natürlich schneller.) Es stellen sich noch die folgenden Fragen : Wenn man dieses inkompatible Paar gefunden hat, kann man das Ergebnis verallgemeinern, um die letzte Frage zu beantworten :
Noch ein paar Tipps




Lösung



Die grundlegende Beobachtung bei geschlossenen und offenen Ketten ist :  Verschiebt man einen  m - Abschnitt um eine Position, so bleibt die Anzahl der weißen (bzw. schwarzen) Perlen entweder gleich oder ändert sich um  ± 1 . Macht man mehrere solcher Verschiebungen, kommen alle Anzahlen weißer Perlen zwischen der Anzahl am Anfang (vor den Verschiebungen) und am Ende (nach den Verschiebungen) vor.

Beginnt man beispielsweise mit einem Abschnitt, der  6  weiße Perlen enthält, verrückt dann diesen Abschnitt um beliebig viele Positionen, und zählt dann  13  weiße Perlen, so muss es für jede Zahl  k  {6, 7, ... , 13}  eine Zwischenposition mit genau  k  weißen Perlen gegeben haben. Das scheint offensichtlich, soll aber bewiesen werden :

Diskreter Zwischenwertsatz
Eine endliche Folge natürlicher Zahlen ( r - Vektor) beginne mit  n1  und ende mit  nr . Es sei  nr > n1 . Benachbarte Folgenglieder sind entweder gleich oder haben den Abstand  1 . Dann kommt jedes natürliche  n  zwischen  n1  und  nr  in der Folge vor.
nr > n1  ist keine Einschränkung. Für  nr < n1  dreht man die Folge einfach um.

Beweis  (Vollständige Induktion über  r ;  r = 2  klar)
r  →  r + 1
Zwischen  n2  und  nr  kommen nach Induktionsvoraussetzung alle natürlichen Zahlen vor. Da nur die drei Fälle  n1 = n2 ,  n1 + 1 = n2  und  n1 - 1 = n2  in Frage kommen, kommen also insbesondere ab einschl.  n2  alle Zahlen von  n1 + 1  bis  nr  vor.

Mit dem Zwischenwertsatz ist nun die Aussage über die geschlossenen Ketten leicht nachweisbar. Wenn man annimmt, dass es keinen  m - Abschnitt mit  m/2  weißen Perlen gibt, so müssen nach dem Zwischenwertsatz alle  m - Abschnitte (o.E.) mehr als  m/2  weiße Perlen aufweisen. Es gibt  n  solcher Abschnitte. Addiert man die Anzahl weißer Perlen über alle Abschnitte, so beträgt die Summe mehr als  n·m/2 . Andererseits gibt es in der Kette genau  n/2  weiße Perlen, und jede von ihnen kommt in genau  m  Abschnitten vor, so dass die Summenbildung über die Abschnitte  n·m/2  ergeben muss. Also war die Annahme falsch.

Nun zu den offenen Ketten.

Die Kette lässt sich in  n/m  disjunkte Abschnitte aufteilen. O.E. enthalte der erste Abschnitt mehr als  m/2  weiße Perlen. Dann muss es wegen der gleichen Anzahl weißer und schwarzer Perlen in der Kette einen anderen Abschnitt geben, der weniger als  m/2  weiße Perlen enthält. Die Behauptung folgt dann aus dem Zwischenwertsatz. Wir teilen die Kette in drei Teile mit den Längen  n/2-1 ,  2 ,  n/2-1 . Der mittlere Teil ist der Überlappungsbereich des ganz linken und des ganz rechten  m - Abschnitts. O.E. enthalte wieder der erste  m - Abschnitt, bestehend aus den ersten beiden Teilen, mehr als  m/2  weiße Perlen.

Kette fuer m=n/2+1

    1. Fall :  Der mittlere Teil enthält eine weiße und eine schwarze Perle. Damit enthält der ganz linke  m - Abschnitt mehr weiße Perlen als der ganz rechte. Die Behauptung folgt dann aus dem Zwischenwertsatz.
    2. Fall :  Der mittlere Teil enthält zwei weiße Perlen. Dann enthält der erste Teil mindestens  m/2 - 1  weiße Perlen, der letzte somit höchstens  m/2 - 2  weiße Perlen. Also enthält der ganz linke  m - Abschnitt mindestens  m/2 + 1  und der ganz rechte höchstens  m/2  weiße Perlen. Die Behauptung folgt aus dem Zwischenwertsatz.
    3. Fall :  Der mittlere Teil enthält zwei schwarze Perlen. Dann enthält der erste Teil (und damit der ganz linke  m - Abschnitt) mindestens  m/2 + 1  weiße Perlen, der letzte Teil (und damit der ganz rechte  m - Abschnitt) höchstens  m/2 - 2  weiße Perlen. Die Behauptung folgt wieder aus dem Zwischenwertsatz. Man packt alle weißen Perlen in einen mittleren Block, wie im folgenden Bild :

Kette fuer m>n/2+1

Wegen  m < n  bleiben für den rechten Teil noch schwarze Perlen übrig; deren Anzahl ist  n/2 - m/2 + 1 < m/2 . Ein  m - Abschnitt mit  m/2  schwarzen Perlen müsste dann den gesamten weißen Abschnitt einschließen und somit mehr als  m/2  weiße Perlen. Damit ist die Inkompatibiltät von (n,m) gezeigt. Ab hier braucht nur noch  m < n/2  betrachtet zu werden. Da  m | n  schon behandelt wurde, muss noch  n = 4k + 2 ,  n  10  untersucht werden ( k = 1  kann ausscheiden, da in diesem Fall nur  m = 2  sein kann). Dann lässt sich die  n - Kette wie im folgenden Bild darstellen. Graue Perlen stehen für weiße oder schwarze Perlen.

Kette fuer m=4

Wenn die linken  4  Perlen gleichverteilt sind  ( 2  weiße,  2  schwarze), ist nichts mehr zu beweisen. Also werden nur die vier Alternativen im linken unteren Teil der Graphik untersucht. Sind die beiden folgenden Perlen von verschiedener Farbe, kann man wieder den Zwischenwertsatz anwenden :  Dann muss es nämlich in mindestens einem der  k - 1  rechten  4 - Abschnitte mehr schwarze Perlen (für die ersten beiden Alternativen) bzw. mehr weiße Perlen (für die letzten beiden Alternativen) geben. Wegen der weiß/schwarz-Symmetrie der vier Alternativen kann o.E. angenommen werden, dass die beiden folgenden Perlen schwarz sind (siehe Graphik).
    Zu I :  Überschuss an weißen unter den linken  6  Perlen   →   In einem der rechten  4 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  6  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 6  (s.o.).
    Zu III und IV :  Überschuss an schwarzen unter den linken  6  Perlen   →   In einem der rechten  4 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz. Die Fälle  m = 6  und  m = 8  werden weitgehend analog zu  m = 4  behandelt und deshalb etwas komprimiert dargestellt.

Kette fuer m=6, 1. Fall

    Zu I :  Überschuss an weißen unter den linken  8  Perlen   →   In einem der rechten  6 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  8  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 8 .
    Zu III :  Überschuss an schwarzen unter den linken  8  Perlen   →   In einem der rechten  6 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz. Hier müssen zwei Fälle unterschieden werden :  4  schwarze bzw.  3  schwarze Perlen an den Positionen  7  bis  10 .

      1. Fall :
Kette fuer m=6, 2. Fall

    Zu I :  Überschuss an weißen unter den linken  10  Perlen   →   In einem der rechten  6 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  10  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 10 .
    Zu III :  Es gibt  15  mögliche Positionen für die beiden schwarzen Kugeln. Alle ergeben zusammen mit dem angrenzenden schwarzen  4 - Abschnitt einen gleichverteilten  6 - Abschnitt.
    Zu IV :  Überschuss an schwarzen unter den linken  10  Perlen   →   In einem der rechten  6 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz.

      2. Fall :
Kette fuer m=6, 3. Fall

    Zu I :  Überschuss an weißen unter den linken  10  Perlen   →   In einem der rechten  6 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  10  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 10 .
    Zu III :  Überschuss an schwarzen unter den linken  10  Perlen   →   In einem der rechten  6 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz. Kette fuer m=8, 1. Fall

    Zu I :  Überschuss an weißen unter den linken  10  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  10  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 10 .
    Zu III :  Überschuss an schwarzen unter den linken  10  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz. Hier müssen zwei Fälle unterschieden werden :  4  schwarze bzw.  3  schwarze Perlen an den Positionen  9  bis  12 .

      1. Fall :
Kette fuer m=8, 2. Fall

    Zu I :  Überschuss an weißen unter den linken  12  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  12  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 12 .
    Zu III :  Der zweite  4 - Abschnitt von links kann  0  bis  3  schwarze Perlen enthalten, so wie in der folgenden Graphik. Bei  0  und bei  3  schwarzen Perlen ist die Existenz eines gleichverteilten  8 - Abschnitts offensichtlich. In den beiden anderen Fällen muss man nur die  6  bzw.  4  Kombinationen der weißen und schwarzen Perlen im linken  4 - Abschnitt prüfen, um zum gleichen Ergebnis zu kommen.

Kette fuer m=8, 2. Fall, 3. Unterfall

    Zu IV :  Überschuss an schwarzen unter den linken  12  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz.

      2. Fall :
Kette fuer m=8, 3. Fall

    Zu I :  Überschuss an weißen unter den linken  12  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  12  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 12 .
    Zu III :  Überschuss an schwarzen unter den linken  12  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz. Hier müssen drei Fälle unterschieden werden :  6 ,  5 ,  4  schwarze Perlen an den Positionen  9  bis  14 .

      1. Fall :
Kette fuer m=8, 4. Fall

    Zu I :  Überschuss an weißen unter den linken  14  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  14  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 14 .
    Zu III :  Wie für  m = 8 , n = 8k + 4 , 1. Fall III teilt man wieder die linken  8  Perlen in zwei  4 - Abschnitte ; der rechte davon soll  0 ,  1  oder  2  schwarze Perlen an beliebiger Position aufweisen. Bei allen drei Möglichkeiten gibt es offensichtlich einen gleichverteilten  8 - Abschnitt innerhalb der linken  14  Perlen.
    Zu IV :  Dies geht analog zu III, mit  0 ,  1 ,  2  oder  3  schwarzen Perlen an den Positionen  5  bis  8 . Hier kann man wieder die kleine Graphik aus  m = 8 , n = 8k + 4 , 1. Fall III verwenden.
    Zu V :  Überschuss an schwarzen unter den linken  14  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz.

      2. Fall :
Kette fuer m=8, 5. Fall

    Zu I :  Überschuss an weißen unter den linken  14  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  14  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 14 .
    Zu III :  Das nächste Bild ist ganz ähnlich wie bei  m = 8 , n = 8k + 4 , 1. Fall III. Beim zweiten  4 - Abschnitt von links ist wieder nur die Anzahl schwarzer Perlen von Bedeutung, nicht deren Position. Im linken  4 - Abschnitt muss man dann nur die wenigen möglichen Kombinationen der weißen und schwarzen Perlen durchgehen. Allerdings ist bei jeder dieser Kombinationen zu beachten, dass an einer Stelle des  6 - Abschnitts (Positionen  9  bis  14 ) eine weiße Perle vorkommen muss. Bei der Überprüfung der Kombinationen wird man sehen, dass nur maximal die linken fünf Perlen dieses  6 - Abschnitts für die Auswahl eines gleichverteilten  8 - Abschnitts herangezogen werden müssen; in diesem  5 - Abschnitt (in der Graphik markiert) befindet sich dann eine oder keine weiße Perle.

Kette fuer m=8, 5. Fall, III

    Zu IV :  Überschuss an schwarzen unter den linken  14  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz.

      3. Fall :
Kette fuer m=8, 6. Fall

    Zu I :  Überschuss an weißen unter den linken  14  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr schwarze als weiße Perlen   →   Behauptung folgt mit Zwischenwertsatz.
    Zu II :  Linke  14  Perlen gleichverteilt   →   Für den Rest gilt  m | n - 14 .
    Zu III :  Überschuss an schwarzen unter den linken  14  Perlen   →   In einem der rechten  8 - Abschnitte finden sich mehr weiße als schwarze Perlen   →   Behauptung folgt mit Zwischenwertsatz. Nach den bisherigen Ergebnissen ist der erste Kandidat (8,6), und dieser erweist sich in der Tat als inkompatibel, wie die Graphik zeigt :

Kette fuer n=8, m=6 Nach den bisherigen Ergebnissen ist der erste Kandidat (22,10). Aber dieses Paar ist kompatibel. Das merkt man zwar nach einigem Probieren, aber den vollständigen Beweis überlässt man am besten einem kleinen Programm.  -  Der nächste Kandidat ist (24,10), und die Graphik zeigt die Imkompatibilität :

Kette fuer n=24, m=10 Aus der vorigen Frage gewinnt man die Idee, dass Inkompatibiltät sich leicht nachweisen lässt, wenn sich große Abschnitte von weißen Perlen abwechseln mit großen Abschnitten von schwarzen Perlen, so wie in der folgenden Graphik :

Kette fuer inkompatible Paare

In dieser Weise lassen sich beliebig lange Ketten herstellen. Wählt man nun  m  mit  a < m/2 < b , ist das Problem schon gelöst, analog zu der oben gezeigten Kette mit (n,m) = (24,10) und  a = 4 ,  b = 6 .

Man kann das noch etwas detaillierter untersuchen und die Abschnittslängen  a  und  b  ausrechnen. Wenn es  k  Abschnitte der Länge  a  gibt, gilt  a·k = b·(k-1) = n/2 . Insbesondere folgt  a = j·(k-1)  und  b = j·k . Damit lässt sich  n  darstellen als  n = 2·j·k·(k-1)  mit  j  2  und  k  3  ( j = 1  scheidet aus wegen  a < m/2 < b ,  k = 2  scheidet aus wegen  2a < m < n/2 ).

Außer den so konstruierten Paaren gibt es noch viele weitere inkompatible mit  m < n/2 , da die Abschnitte weißer bzw. schwarzer Perlen für unser Argument nicht exakt gleich lang sein müssen.





Publiziert 2009-12-27          Stand 2009-08-10


voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem


Manfred Börgens   |    zur Leitseite