(12-22-2025, 06:10 PM)PhiSigma schrieb: Spannend, dass ihr alle andere Lösungen habt als ich. Ich kam auf k=33 als Minimum, damit immer alle Personen erreicht werden können. Bei k=32 ist es möglich, die gut/schlecht spielenden Dreierteams so zu verteilen, dass man nie alle Personen erreichen kann, bei k=33 nicht mehr.
Damit man meine Notizen lesen kann, als Erklärung: Ich habe das etwas abstrahiert zu einer Menge von 99 (bzw. n) Elementen und einer Menge von Tripeln aus dieser Menge, wobei man einen Graphen bilden kann, bei dem die Tripel verbunden sind, die ein Paar gemeinsam haben. (z.B. (1, 2, 3) und (1, 2, 4).)
Auswechseln kann man hier dann erfolgreich genau dann, wenn es mindestens eine Zusammenhangskomponente im Graphen gibt, die jedes Einzelelement (z.B. 1 oder 2) mindestens einmal enthält, bzw andersherum scheitert man, wenn jede Zusammenhangskomponente nicht jedes Element enthält.
Hier der Beweis, den ich mir notiert habe:
Generell für k >= 1 und n Elemente gilt:
Da alle Tripel, die ein bestimmtes Paar enthalten, zusammenhängen, kann man sagen, dass jedes Paar (a1,a2) in genau einer Zusammenhangskomponente enthalten ist. Dieses muss dann Tripel mit mindestens k anderen Elementen a3, ..., a_(k+2) haben. Also sind auch die k weiteren Paare (a1,a3), ..., (a1,a_(k+2)) in derselben Komponente, womit man mindestens k+1 Paare darin hat, die a1 enthalten. Ebenso sind auch (a2,a3), ..., (a2,a_(k+2)) darin.
Wenn keine Zusammenhangskomponente alle Einzel-Elemente enthalten soll, muss es eine geben ("Gruppe 1"), die ein Element a aber nicht Element b enthält. Das Paar (a,b) kann nicht darin sein, muss also in einer weiteren Komponente ("Gruppe 2") sein. Da diese ebenfalls unvollständig ist, muss es ein Element c geben, das nicht in Gruppe 2 ist. Das Paar (b,c) kann weder in Gruppe 1 noch Gruppe 2 sein, es muss dafür also auch noch "Gruppe 3" geben, also gibt es mindestens drei Zusammenhangskomponenten.
Gruppe 1 enthält a, also k+1 Paare, die a enthalten.
Gruppe 2 enthält (a,b), also gibt es auch mindestens k weitere Elemente d1,...,d_k, die darin mit a und mit b gepaart sind. Damit sind in Gruppe 2 dann k+1 andere Paare, die a enthalten.
Gruppe 3 enthält (b,c) und auch hier werden mindestens k weitere Elemente gebraucht. Würde man etwas aus d1,...,d_k mit (b,c) verknüpfen, würde das über (b,c,d_i) -> (a,b,d_i) eine Verbindung zwischen Gruppe 2 und Gruppe 3 herstellen. Also müssen es mindestens k neue Elemente d_(k+1),...,d_(2k) sein.
(a,c) darf nicht in Gruppe 2 sein, braucht also k Elemente nicht aus d1,...,d_k, die mit a und c gepaart werden.
- Wenn eins aus d_(k+1),...,d_(2k) darunter ist, ist (a,c) damit in Gruppe 3 und Gruppe 3 enthält k+1 andere Paare, die a enthalten. Damit gibt es in allen drei Gruppen jeweils k+1 verschiedene Paare mit a, also insgesamt 3k+3 Paare mit a, heißt es ist 3k+3 < n bzw. k < n/3-1.
- Wenn keins aus d_(k+1),...,d_(2k) darunter ist, hat man nochmal k weitere Elemente d_(2k+1),...,d_(3k), also gibt es neben a, b und c noch mindestens 3k andere Elemente, was nur möglich ist, also ist 3k+3 <= n bzw, k <= n/3-1.
Wenn man nicht erfolgreich auswechseln kann, muss also hier k <= 99/3-1 = 32 sein, d.h. bei k>=33 kann man es auf jeden Fall.
Und (bei n teilbar durch 3, was hier der Fall ist) kann man für k=n/3-1 (also k+1=n/3) eine Lösung konstruieren:
Gruppe 1 enthält die Tripel aus allen möglichen Paaren aus {a_1, ..., a_(k+1)} mit allen möglichen Einzelelementen aus {a_(k+2), ..., a_(2k+2)}.
Jedes Paar mit zwei Elementen aus {a_1, ..., a_(k+1)} hat also k+1 Tripel in dieser Gruppe (mit allen k+1 Elementen aus {a_(k+2), ..., a_(2k+2}), und jedes Paar aus einem Element aus {a_1, ..., a_(k+1)} und einem aus {a_(k+2), ..., a_(2k+2)} hat k Tripel in dieser Gruppe (mit allen k anderen Elementen aus {a_(k+2), ..., a_(2k+2)}).
Dann macht man das gleiche in Gruppe 2 mit den Paaren aus {a_(k+2), ..., a_(2k+2)} und den Einzelelementen aus {a_(2k+3), ..., a_(3k+3)} und in Gruppe 3 mit den Paaren aus {a_(2k+3), ..., a_(3k+3)} und den Einzelelementen aus {a_1, ..., a_(k+1)}.
Bei n=9 und k=2 sähe es z.B. so aus:
124 125 126 134 135 136 234 235 236
457 458 459 467 468 469 567 568 569
781 782 783 791 792 793 891 892 893
Damit ist jedes mögliche Paar abgedeckt, und trotzdem enthält jede Gruppe nur zwei Drittel der Elemente und nicht alle.
Hier kann man bei k=99/3-1=32 also nicht garantieren, dass das Auswechseln möglich ist, da ein Szenario aufgestellt werden kann, wo es nicht geht.
Damit ist die Grenze bei k=33 mit der Endziffer 3.
Ich glaube, du hast recht. Das klingt für mich überzeugend. Die Schwachstelle in meiner Lösung ist wahrscheinlich, dass es nicht optimal ist, vollständige Zusammenhangskomponenten zu haben.