Ich hatte ja noch eine kleine Bonus-Aufgabe im "feedback" gestellt...
Gebe es k Teams und n Farben, so betrachten wir in einem Gesamtnetzt zunächst eines der Teams und dessen Sub-"Netz" aus Ecken und Kanten zwischen Teammitgliedern eines Teams:
Wie für 2 Farben betrachten wir hiervon eine Ecke... gehen davon 5 Kanten zu anderen Ecken dieses Netzes, so müssen darunter min. 3 Kanten eine der beiden Farben haben. Zwischen den Endpunkten dieser Kanten darf es somit nicht mehr diese Farbe geben, damit es kein perfektes Dreieck gibt. Somit sind die Endpunkte dieser Kanten untereinander alle mit der anderen Farbe verbunden und bilden somit dennoch ein perfektes Dreieck. Dies zeigt, dass wenn in einem Sub-Netz (eines Teams) mindestens eine Ecke mit Kanten zu 5 Ecken desselben Netzes gibt, also wenn ein Sub-Netz mindestens 6 Ecken besitzt = ein Team aus mindestens 6 Mitgliedern besteht, so muss es mindestens ein perfektes Dreieck geben.
Verallgemeinern wir dies auf n Farben. Dabei sei E(n) die Anzahl der Eckpunkte eines Subnetzes, so dass es bei n Farben mindestens ein perfektes Dreieck darunter geben muss. Also etwa E(1) = 3, E(2) = 6, ...
Angenommen in einem Sub-Netz gehen s*n+1 Kanten von einer Ecke ab für ein s in den natürlichen Zahlen. So muss es darunter mindestens (s+1) Kanten einer Farbe geben. Die Endpunkte dieser (s+1) Kanten dürfen somit nicht mehr mit dieser Farbe verbunden sein, da es sonst ein perfektes Dreieck dieser Farbe gebe. Betrachten wir also diese (s+1) Endpunkte dieser Kanten, so bilden diese ein weiteres Sub-Sub-Netz des Sub-Netztes, welches nun nur noch (n-1) Farben besitzen darf. Angenommen man wählt das s derart, dass s+1 = E(n-1), so muss es in diesem Sub-Sub-Netz mit (n-1) Farben mindestens ein perfektes Dreieck geben - entweder mit einer der noch verbleibenden (n-1) Farben oder mit der ursprünglichen Farbe der (s+1) Kanten. Sei also s = E(n-1) - 1, so hat man in einem Sub-Netz bei dem s*n+1 Kanten von einer Ecke ausgehen mindestens ein perfektes Dreieck bei n Farben. Dieses Sub-Netzt besitzt also s*n+2 Ecken.
Insgesamt ist somit: E(n) <= s*n + 2 = (E(n-1) - 1)*n + 2 = n*E(n-1) + (2-n)
Anmerkung: Evtl. kann man E(n) kleiner als n*E(n-1) + (2-n) wählen, aber dafür fehlt mir ein Beweis...
kennt da jemand was?
Setzen wir daher F(n) = n*F(n-1) + (2-n), F(1) = 3, so ergibt sich durch rekursive Anwendung dieser Formel eine obere Schranke für E(n):
F(n) = n! * F(1) - n! * sum_{i=1}^{n-2} [i/(i+2)!]
Durch Indexshift, Erweiterung der Summe ab i = 0 und Einsetzen von F(1) erhält man:
F(n) = n! * sum_{i=0}^{n} [(2-i) / i!]
Dies Summe lässt sich wohl nicht mehr schön vereinfachen... WolframAlpha schlägt die "incomplete gamma function" vor:
F(n) = 1 + e * Γ(n + 1, 1)
Für F(n) ergibt sich die Folge: 3, 6, 17, 66, 327, 1958, ... (dies ist wie gesagt nur eine obere Schranke für E(n), so dass es mindestens ein perfektes Dreieck in einem Sub-Netz dieses Größe mit n Farben geben muss)
Betrachten wir nun noch k Teams, so muss das ursprüngliche Netz (analog zur Lösung mit zwei Teams) mindestens k*(E(n)-1) + 1 Ecken haben, damit das Sub-Netz eines Teams mindestens aus E(n) Ecken besteht und damit mindestens ein perfektes Dreieck enthält. Sei E(k,n) die Anzahl der Ecken, so dass es bei k Teams und n Farben mindestens ein perfektes Dreieck gibt, so ergibt sich mit F(n) statt E(n) wieder eine obere Schranke für E(k,n):
E(k,n) <= k*(F(n)-1) + 1 = k * e * Γ(n + 1, 1) + 1
Insgesamt: Egal wie viele Farben und Teams man verwendet, wenn genug mitspielen, so gibt es immer ein perfektes Dreieck
Edit:
Eine einfache Abschätzung wäre noch...
E(n) <= 3 * n!
Und damit:
E(k,n) <= 3k * n! + (1-k)
