Svea und Rike haben sich für ein Wochenende am Meer verabredet. Endlich ist es soweit. Es weht zwar schon ein frischer Wind, aber mit dicker Jacke und Mütze können sie die tolle Atmosphäre genießen. Die neuen Tournament-Aufgaben sind erschienen und bieten genügend Gesprächsstoff, doch zuerst wollen sie noch den Zusammenhang zwischen der minimalen Anzahl n der Ecken eines Graphen G = Gn(s) und der maximalen Anzahl c seiner Zusammenhangskomponenten besprechen. Dabei ist s eine gegebene arithmetische Zahlenfolge und zwei Ecken (Vertices) des Graphen G sind nur dann verbunden, wenn die Summe ihrer Nummern in der Folge s enthalten ist. Sie hatten bereits die Lösung des bulgarischen Teams gutgeheißen, die allerdings nur für hinreichend große n funktioniert:
Dabei ist d die Differenz zweier Folgenglieder. Das deutsche Team A hat eine ähnliche Formel
für den Fall der Folge
s = (d, 2d, 3d, …)
aufgestellt. Doch in der Formel stimmt die Bedingung an n nicht.
Sveas 1. Beispiel
Svea Lass uns noch einmal ein kleines, aber nichttriviales Beispiel ansehen.
Rike Klar. Zeig mal.
Svea Hier, ich nehme die Folge
s = (3, 6, 9, …)
Für diese Folge würde ich gern das kleinste n bestimmen, den kleinesten Graphen Gn also, sodass die Formel für die Anzahl der Zusammenhangskomponente c
zutrifft.
Rike Okay, dann mal los, Svea.
Svea Zuerst bestimme ich die Anzahl der Zusammenhangskomponenten nach der Formel
Wegen d = 3 bekomme ich
c = 2,
also 2 Zusammenhangskomponenten.
Rike Richtig.
Svea Um das n zu bestimmen, "gehe" ich in den im Restklassenraum modulo 3 und habe darin 2 Möglichkeiten, das Anfangsglied der Folge durch Addition zu erhalten:
0 + 0 ≡ 0 mod 3
1 + 2 ≡ 0 mod 3
Da der Graph verschiedene Vertex-Nummer hat und nur verschiedene Vertices verbunden sind, muss die Aufgabe 0 + 0 durch 2 verschiedene Vertices realisiert werden, die kleinsten davon wären die 3 und die 6. Die Anzahl n der Vertices des Graphen muss also mindestens 6 sein. Die zweite Addition 1 + 2 kann im Graphen mit den Nummern 1 und 2 realisiert werden. Es bleibt bei
n ≥ 6.
Rike Okay, das hört sich gut an.
Sveas Verallgemeinerung
Svea Ich denke, dass sollte auch allgemein gelten: Wenn s = (d, 2d, 3d, …), dann haben wir im Restklassenraum modulo d genau d Möglichkeiten, jede Zahl a von 0 bis d – 1 als Summe zu erhalten. Doch wegen der Kommutativität der Addition und weil der Graph nicht gerichtet ist, gehören zur Addition
k1 + k2 = k2 + k1 ≡ a mod d
immer dieselben Vertices k1 und k2. Ist d gerade, haben wir
Möglichkeiten, jeweils zwei Vertices zu einer Summe zu finden, das ist dann auch die Anzahl der Zusammenhangskomponenten:
Ist d ungerade, so sind ist
was die Formel
gut zusammenfasst. Folglich muss der Graph Gn(s) mit der arithmetischen Folge s:
s = (d, 2d, 3d, …)
wegen der Addition im Restklassenraum modulo d
0 + 0 ≡ 0 mod d
genau wie im Fall d = 3 einen Vertex d und einen mit der Nummer 2d enthalten. Das heißt, dass das minimale n die Bedingung
n ≥ 2d
erfüllen muss.
Rike Genau! Damit hast du die „Lösung“ des deutschen Teams A korrigiert. Glückwunsch!
Svea Danke!
Rike Und weiter?
Sveas 2. Beispiel
Svea Für die Folge
s = (1, 4, 7, …)
bekomme ich wieder 2 Zusammenhangskomponenten und finde wieder 2 Möglichkeiten der Addition modulo 3:
0 + 1 ≡ 1 mod 3
2 + 2 ≡ 1 mod 3
Die erste Addition wird durch die Vertices 3 und 1 realisiert, die zweite durch 2 und 5. Damit haben wir als kleinstes n:
n ≥ 5
gefunden.
Sveas 3. Beispiel
Rike Okay. Und wie geht es weiter?
s = (2, 5, 8, …)?
Svea Ja klar! Dann habe ich alle Fälle mit den Anfangsgliedern s1 ≤ 3 = d. Das war – glaube ich – im Sinne der Aufgabe. Für größere Anfangsglieder kann es vorkommen, dass es weniger Zusammenhangskomponenten gibt oder dass der Graph nicht zusammenhängend ist, das hatten wir ja schon diskutiert.
Rike Richtig, das hatten die anderen übersehen.
Svea Also für die Folge
s = (2, 5, 8, …)
gibt es maximal 2 Zusammenhangskomponenten. Es gibt wieder 2 Arten, das Anfangsglied 2 durch Addition modulo 3 zu erhalten:
0 + 2 ≡ 2 mod 3
1 + 1 ≡ 2 mod 3
Dazu brauchen wir die Vertices 3 und 2 bzw. 1 und 4. Dann ist das kleinste n:
n ≥ 4.
Rike Schön!
Zusammenfassung
Svea Außerdem fällt mir auf, dass in allen Fällen,
n ≥ 6 = 2d
die hinreichende Bedingung für die maximale Anzahl c von Zusammenhangskomponenten
für alle arithmetischen Folgen mit kleinem, ganzen Anfangsglied
0 ≤ s1 ≤ d
ist.
Rike Damit hast du nun endgültig die deutsche Formel korrigiert und für die Bulgaren eine hinreichende Bedingung für das n gefunden. Super!
Svea Danke, Rike!
***
Übungsaufgaben
Bestimme c und das minimale n jeweils für den Graphen Gn(s) und den Folgen
a) s = (0, 4, 8, …)
b) s = (1, 5, 9, …)
c) s = (2, 6, 10, …)
d) s = (3, 7, 11, …)