Svea und Rike haben sich bei einem Camp am Meer kennengelernt. Svea ist Gymnasiastin aus Hamburg und ein mathematisches Wunderkind. Sie hat sich die Aufgaben des International Tournament of Young Mathematicians von 2023 angeschaut und sich gewundert. Svea erklärt Rike diesen Wettbewerb.
Der ITYM-Wettbewerb
Svea Das ITYM ist ein spezieller Wettbewerb, bei dem Mannschaften gegeneinander antreten. Die Mannschaften lösen die Aufgaben im Team, aber nicht wie bei Olympiaden, wo alle in einem Klassenzimmer sitzen und nur ein weißes Blatt und einen Bleistift haben, nein, hier können die Mannschaften Hilfsmittel benutzen, an den Aufgaben arbeiten, wann immer sie Lust haben, ja, sie haben sogar einen Betreuer, den sie um Rat fragen können.
Rike Okay, ein neues Format! Nicht schlecht!
Svea Die Aufgaben stammen von Wissenschaftlern aus verschiedenen Ländern (Bulgarien, USA, UK, Frankreich, China, Deutschland, Rumänien), meist aus denen, aus denen dann auch die Mannschaften kommen. Die Aufgaben sind offen formuliert und repräsentieren aktuelle Forschungsgebiete. So kann es sein, dass gar keine allgemein gültige Lösung formuliert werden kann oder dass verschiedene Mannschaften sich verschiedenen Teilaspekten widmen und verschiedene Ergebnisse erzielen. So ist es auch bei der 1. Aufgabe: Alle Mannschaften, die überhaupt die Aufgabe gelöst haben, hatten verschiedene Lösungen.
Rike Haha, und wer gewinnt dann?
Svea Gute Frage, Rike. Die Mannschaften sollen ihre Lösung präsentieren. Eine andere Mannschaft wird auserwählt, um die präsentierte Lösung zu hinterfragen. Eine Jury entscheidet dann über den Sieg.
Rike Aha, eine Art wissenschaftlicher Diskurs?
Svea Ja, ich war ja noch nicht dabei, ich stelle es mir anstrengend vor, wenn die diskutierenden Gruppen verschiedene Ansätze haben, und vor allem, wenn die Lösungen nicht richtig sind…
Rike Haha.
Svea Die Teamlösungen von 2023 sind veröffentlicht. Die erste Aufgabe finde ich besonders interessant. Hier geht es darum, die Geometrie von Graphen – nennt man das so? – analytisch zu beschreiben.
Rike Das passt schon, das hört sich gut an.
Die Aufgabe
Svea Diese Aufgabe geht so:
1. Graphs of Sequences
Let s = s1, s2,... , sk, ... be a sequence of positive integers, and let n ∈ N be a positive integer. Consider the graph G = Gn(s) with set of vertices V = {1, 2, ..., n} and the following set of edges: two vertices x and y of G are connected by an edge if and only if the number P(x, y) = x + y is a member of the sequence s. The function P will be called the parameter of the graph G.We would like to investigate this graph when s is:
a) an arithmetic sequence: ak+1 = ak + d for some d ∈ N and all k ∈ N;
[...]
1. What is the number of connected components of G?
[...]Siehe https://www.itym.org/archive, Aufruf am 03.09.2024.
Diese erste Teilaufgabe habe ich mir angeschaut.
Rike Mir fallen 2 formale Kleinigkeiten auf: Haben die denn die Folge nicht in Klammern geschrieben? So ist es doch üblich:
s = (s1, s2,…. , sk, …)???
Außerdem werden die Folgenglieder der arithmetischen Folge mit den Kleinbuchstaben a bezeichnet, die Folge wurde aber mit s bezeichnet. Drittens fängt die Folge mit dem Index 1 an, statt üblicherweise mit 0. Naja, ist nicht so schlimm…
Svea Hmm, naja, es gibt noch eine allgemeine Notation, da steht, dass die natürlichen Zahlen mit 1 beginnen…
Rike Okay, wie weit bist du gekommen?
Svea Ich habe mir die Lösungen angeschaut, habe ein paar Beispiele mit kleinen Zahlen überlegt, um ein Gefühl für die Aufgabe zu bekommen, und habe für meine Beispiele mit kleinen Zahlen bei keiner Mannschaft die korrekte Lösung gefunden.
Rike Echt jetzt? Ist ja krass! Zeig mir mal deine Bespiele, Svea!
1. Beispiel
Svea Für den kleinsten nichtleeren Graphen G1 gibt es keine Kanten, also auch keine zusammenhängenden Kanten, egal, welche Folge s du wählst, und folglich gibt es keine Zusammenhangskomponente, die bezeichne ich mal mit der Variablen c, also ist hier
c = 0.
Rike Stimmt! Weiter, was hast du noch?
2. Beispiel
Svea Jetzt nehme ich eine Graphen G2(s) und die arithmetische Folge s:
s = (4, 5, 6, …),
die Differenz d zwischen den Folgengliedern ist hier
d = 1
Da die Folge erst mit
s1 = 4
anfängt und
1 + 2 = 3
ist, die 3 aber nicht zur Folge gehört, gibt es keine Zusammenhangskomponente, also ist
c = 0.
Rike Damit hast du herausgefunden, dass c vom Anfangsglied der Folge abhängt. Offensichtlich gibt es keine zusammenhängenden Komponenten, wenn das Anfangsglied kleiner oder gleich 3 ist:
s1 ≤ 3.
Svea Richtig, das gilt für alle arithmetischer Folgen aus natürlichen Zahlen und positiver ganzzahliger Differenz d. Dann ist c = 0. Die Abhängigkeit der Lösung vom Anfangsglied der Folge haben gar nicht alle Teams entdeckt, eigentlich nur das bulgarische Team.
Rike Oh, das ist doch so einfach…
Svea Tja…
Vergleich mit der Lösung des bulgarischen Teams
Rike Wie heißt denn die Lösung des bulgarischen Teams?
Svea Warte, hier, in unseren Notationen haben sie herausgefunden, dass
falls n hinreichend groß. [Claim 2.2. in Bulgaria-ITYM2023-Problem01.pdf]
Rike Aha, dein 2. Beispiel mit n = 2, d = 1, s1 = 4 ergibt in dieser Formel
cbulgaria = 1.
Natürlich ist n nicht hinreichend groß, das heißt, sie haben diesen Fall nicht betrachtet.
Svea Stimmt, kleine n haben sie nicht untersucht.
Rike Und andere Mannschaften?
Vergleich mit der Lösung des deutschen Teams A
Svea Die deutsche Mannschaft A hat auch eine Formel gefunden unter der Voraussetzung, dass das erste Folgenglied Null ist:
s0 = 0,
was ja formal gar nicht erlaubt war, oder besser formuliert fordern sie, dass
s1 = d.
Rike Warte, dein Beispiel beruht ja gerade auf der Idee, dass die Folge s nicht mit 0 oder d anfängt.
Svea Stimmt, mein 2. Beispiel haben sie also nicht analysiert.
Rike Was hast du noch?
3. Beispiel
Svea Ich nehme einen Graphen mit 3 Vertices, n = 3, und die Folge
s = (2, 4, 5, 6, …),
Dann sind nur 1 und 3 verbunden, weil ihre Summe gerade ist, ich habe nur eine Zusammenhangskomponente , also
c = 1.
Rike Gut, ist denn hier das n groß genug für die Bulgaren?
Svea Ich bekomme für n = 3, d = 2, s1 =2 den dritten Fall und
cbulgaria = 2,
da stimmt offensichtlich nicht, n ist also nicht groß genug für die bulgarische Formel.
Die Formel des deutschen Teams A
Rike Jetzt könntest du aber die Formel der Deutschen testen!
Svea Okay! Ihre Formel lautet:
falls
s1 = d.
[Theorem 1 in GermanyA-ITYM2023-Problem01.pdf]
Mit n = 3, d = 2 habe ich ihren ersten Fall und ihr Wert für c ist ebenfalls
cgermany-a = 2
Rike Hmm???!!!! Beide kriegen dasselbe Ergebnis, warte mal,
ist ja auch dasselbe wie
(d+2)/2
für d gerade und s1 = 2. Aber die Bedingung der Fallunterscheidung
ist nicht richtig, diese Bedingung ist ja gerade in deinem 3. Beispiel erfüllt.
4. Beispiel
Svea Okay… Ich habe mal ein weiteres Beispiel getestet, um die Aufgabe und die Geometrie besser zu verstehen, und zwar nehme ich n = 7 und die Folge der geraden Zahlen
s = (2, 4, 6, …).
In diesem Graphen sind zwei Vertices verbunden, wenn ihre Summe gerade ist, das heißt, wenn man irgend 2 ungerade Zahlen addiert oder 2 gerade. Oder man fragt sich, auf wie viele Arten man gerade Zahlen im Restklassenraum modulo 2 durch Addition zweier Zahlen erhalten kann: Die Lösung ist nämlich
0 + 0 ≡ 0 mod 2
1 + 1 ≡ 0 mod 2
Das sind genau zwei Möglichkeiten, also
c = 2.
Rike Okay. Dein Bild gefällt mir. Eine coole Geometrie, die kommt aus den Restklassen! Ich glaube, du kannst dieses Jahr ruhig beim Tournament mitmachen!
Svea Meinst du?
Rike Auf jeden Fall!
***
Übungsaufgaben
1. Prüfe die deutsche und die bulgarische Formel für das 4. Beispiel!
2. Zeichne den Graphen G7(s) mit der Folge s = (1, 3, 5, …)!
2.1. Bestimme c dafür!
2.2. Prüfe die bulgarische Formel in diesem Fall!
3. Warum klappt die Argumentation mittels die Restklassen nicht in den ersten 3 Beispielen?
4. Wie kann Svea das Vorgehen für andere Fälle verallgemeinern?