14 Lösung / Solution

[Tim.S]

Ich war mir eigentlich sicher, dass k>=49 gilt und habe basierend darauf k=49 also Antwort 9 abgegeben.
Mein Beweis ist folgender:
Die 99 Spieler werden in die fünf Ränge A;B;C;D;E mit jeweils 1;1;48;1;48 Spielern eingeteilt, jeder Spieler ist nur teil eines Ranges.
Für jede Kombination aus zwei Spielern müssen nun mindestens 48 weitere Spieler genannt werden, mit denen das Paar gut zusammenspielt. Solche Dreiergruppen werden im folgenen als "gut" bezeichnet. Diese benannten Spieler sind hinter dem Pfeil (->) angezeigt.
A,A (Geht nicht, weil A nur ein Spieler hat)
A,B -> C (48) 
A,C -> B (1) und C (48-1)
A,D -> E (48)
A,E -> D (1) und E (48-1)
B,B (Geht nicht, weil B nur ein Spieler hat)
B,C -> A (1) und C (48-1)
B,D -> E (48)
B,E -> D (1) und E (48-1)
C,C -> A (1) und B (1) und C (48-2)
C,D -> E (48)
C,E -> D (1) und E (48-1)
D,D -> (Geht nicht, weil D nur ein Spieler hat)
D,E -> A (1) und B(1) und C (48)
E,E -> C (48)
Bei allen gegebenen Kombination sind nun mindestens 48 weitere Spieler angegeben, weshalb die Bedingung der Aufgabenstellung für k=48 erfüllt ist.
Stellen wir nun alle guten Dreiergruppen auf, sortiert in zwei Hälften.
Hälfte 1:
A,B,C
A,C,C
B,C,C
C,C,C
Hälfte 2;
A,D,E
A,E,E
B,D,E
B,E,E
C,D,E
C,E,E
Da es keinen gute Dreiergruppe der einen Hälfte gibt, die einen Buchstaben enthält, durch dessen Auswechselung man eine gute Dreiergruppe der anderen Hälfte erhalten würde, ist es nicht möglich, nach der Wahl der ersten Dreiergruppe noch eine gute Dreiergruppe der anderen Hälfte zu wählen. Somit muss k mindestens 48+1 sein also 49 oder noch mehr sein, damit es vielleicht immer möglich ist. Da es mir für eine höhrere Zahl k nicht mehr gelungen ist, vermute ich k=49 als Lösung. Über eine Erklärung, wo bei meinem Beweis eine Lücke ist, würde ich mich freuen, wenn tatsächlich eine vorliegen sollte.

Habe ich die Aufgabe missverstanden? Hier enthält doch die zweite Hälfte alle Buchstaben, also alle Personen, und wenn man mit einer Dreiergruppe innerhalb dieser Hälfte anfängt, kann man damit alle Dreiergruppen darin und auch alle Personen erreichen, also ist hier das Auswechseln problemlos möglich. So wie ich es verstanden hatte, darf der Trainer sich aussuchen, mit welcher Dreiergruppe er anfängt, und muss nur alle Personen mindestens einmal erreichen, nicht alle guten Dreiergruppen.

Da habe ich wohl beim Lösen die Aufgabenstellung halb vergessen! Vielen Dank! Das ist genau der Punkt, den ich übersehen habe.

[PhiSigma]

Wenn ich mir diesen Thread so ansehe, würde ich vermuten, wenn nicht in den nächsten zwei Tagen noch irgendwas Krasses kommt, dass diese Aufgabe die niedrigste Quote an richtigen Antworten hat. Bei den meisten anderen Aufgaben, bei denen ich die Beweise schwierig fand, hatte ich den Eindruck, dass man auch ohne Beweis die Lösung noch ganz gut erraten kann, hier wäre ich ohne zumindest einen der beiden Teilbeweise (obere oder untere Schranke) nie auf eine Einerziffer von 3 gekommen (wenn ich mal meiner Lösung vertraue.) Intuitiv dachte ich erst an k=2 als Antwort, bis mir mein Computer das schöne Gegenbeispiel für k=2, n=9 ausgespuckt hat. (Ich weiß gar nicht mehr, wie ich meinen Brute-Force-Algorithmus so effizient bekommen habe, dass er mit n=9 noch klar kam. Dieser hatte dann für n=4,..,9 jedenfalls floor(n/3) bestätigt als das niedrigste k, bei dem man garantieren kann, alle Spieler zu erreichen - bei 4 und 5 reicht k=1 dafür, bei 6 bis 8 braucht man k=2 und bei 9 dann k=3.)

Eine Antwortquote von 4% ist aber extrem niedrig, wenn man bedenkt, dass selbst ein Zufallsgenerator noch eine Chance von 10% hat, richtig zu antworten.

[ThH]

Ich hatte anfangs sogar k=1 vermutet...und darüber auch länger erfolglos nachgedacht...

Mittlerweile bin ich aber auch von k=33 überzeugt, ich habe es allerdings noch nicht geschafft, PhiSigmas Lösung durchzuarbeiten.

Abstrakt geht es bei der Aufgabe um Hypergraphen, ein Gebiet von dem ich vorher noch nichts gehört hatte.
Ich werde daher auch nicht versuchen, etwas davon zu erklären.
Nach längerem Recherchieren habe ich dabei dann ein Paper aus dem Jahr 2019 gefunden,
  in dem das Problem der Aufgabe  als Ausgangspunkt behandelt wird. 
Den für mich deutlich einfacheren Teil der Aufgabe, nämlich, dass k=32 nicht reicht, möchte ich versuchen,
   mit einem Gegenbeispiel im Kontext der Aufgabe darzustellen:

Kommen die Spieler z.B. aus drei Städten, A, B und C, aus jeder Stadt gleich viele, also 33 Spieler.
Ein gutes Team bilden drei Spieler genau dann, wenn sie alle aus derselben Stadt kommen
  oder zwei aus A und eine® aus B oder aus den Städten  B, B und C bzw. auch C, C und A.

Spieler aus drei verschiedenen Städten oder etwa zwei aus B und einer aus A bilden also keine guten Teams.

Zu jedem Paar von Spielern finden sich somit entweder 64=31+33 oder nur 32 Partner, so dass sie gut zusammenspielen können,
je nachdem ob die Spieler in einem Paar aus derselben Stadt oder aus verschiedenen Städten kommen, hier gilt also tatsächlich k=32.

In der anfänglichen Aufstellung muss dann eine Stadt fehlen, d.h. kein Spieler kommt aus dieser Stadt.
Aus dieser Stadt kann aber auch nie ein Spieler eingewechselt werden.

Fehlt etwa C, so gilt anfangs AAA oder AAB. Die Einwechslung eines Spielers aus C würde dann zu AAC oder ABC führen, was kein gutes Team ergibt.
Auch die Auswechslung eines Spielers aus A gegen einen aus B, wenn AAB spielt, ist nicht möglich, da BBA nicht harmoniert.
Es bleibt also immer bei AAA oder AAB.

[Georg J. aus D.]

Ich komme auf k = 8 -> Antwort 8 und bin immer noch unsicher.

Ich habe mir überlegt, wie groß bei gegebenem k die Mannschaft sein muss, damit nicht alle Spieler ausgewechselt werden können.

Welche Spieler können überhaupt ausgewechselt werden? Zu Beginn wählt der Trainer zwei Spieler A1 und A2. Diese zwei bilden mit k weiteren Spielern B1 bis Bk jeweils ein gutes Dreierteam. Durch sofortiges Zurückwechseln kann man erreichen, dass mit A1 und A2 alle k B-Spieler eingesetzt werden können.
Man betrachte alle 2k Paare Ai, Bj. Jedes Paar bildet mit k anderen, nicht unbedingt zusätzlichen (über die 2+k bisherigen Spieler hinausgehenden) Spielern Ci ein gutes Dreierteam. Alle diese C-Spieler können auch eingesetzt werden. Dies setzt man so lange fort, bis kein neuer Spieler hinzukommt.

Diese Gruppe ist kleinstmöglich, wenn sie nur 2+k Spieler enthält. Damit man auch mit zwei beliebigen Spielern aus dieser Gruppe keinen Spieler von "außerhalb" für ein gutes Dreierteam benötigt, sollten die k "guten Dreierteam-Spieler" genau die restlichen k Spieler dieser Gruppe sein. Die Gruppe ist in diesem Sinne vollständig.

Um nicht auswechseln zu können, muss es mehr als eine Gruppe geben. Man nehme zwei Spieler aus zwei verschiedenen vollständigen Gruppen G1 und G2. Auch diese zwei bilden mit k weiteren Spielern jeweils ein gutes Dreierteam. Keiner dieser k Spieler kann in G1 oder in G2 sein, da G1 und G2 vollständig sind. Wenn die Gruppen dieser k Spieler auch vollständig sind, dann werden auch k weitere Gruppen benötigt.

Vermutung: Gibt es weniger Spieler als in 2+k Gruppen mit je 2+k Spielern passen, können alle Spieler ausgewechselt werden.
k = 8: 10 Gruppen zu je 10 Spielern. 100 Spieler sind notwendig, damit nicht alle ausgewechselt werden können. Bei 99 Spielern können alle ausgewechselt werden.

[PhiSigma]

Ich hatte anfangs sogar k=1 vermutet...und darüber auch länger erfolglos nachgedacht...

Mittlerweile bin ich aber auch von k=33 überzeugt, ich habe es allerdings noch nicht geschafft, PhiSigmas Lösung durchzuarbeiten.

Abstrakt geht es bei der Aufgabe um Hypergraphen, ein Gebiet von dem ich vorher noch nichts gehört hatte.
Ich werde daher auch nicht versuchen, etwas davon zu erklären.
Nach längerem Recherchieren habe ich dabei dann ein Paper aus dem Jahr 2019 gefunden,
  in dem das Problem der Aufgabe  als Ausgangspunkt behandelt wird. 
Den für mich deutlich einfacheren Teil der Aufgabe, nämlich, dass k=32 nicht reicht, möchte ich versuchen,
   mit einem Gegenbeispiel im Kontext der Aufgabe darzustellen:

Kommen die Spieler z.B. aus drei Städten, A, B und C, aus jeder Stadt gleich viele, also 33 Spieler.
Ein gutes Team bilden drei Spieler genau dann, wenn sie alle aus derselben Stadt kommen
  oder zwei aus A und eine® aus B oder aus den Städten  B, B und C bzw. auch C, C und A.

Spieler aus drei verschiedenen Städten oder etwa zwei aus B und einer aus A bilden also keine guten Teams.

Zu jedem Paar von Spielern finden sich somit entweder 64=31+33 oder nur 32 Partner, so dass sie gut zusammenspielen können,
je nachdem ob die Spieler in einem Paar aus derselben Stadt oder aus verschiedenen Städten kommen, hier gilt also tatsächlich k=32.

In der anfänglichen Aufstellung muss dann eine Stadt fehlen, d.h. kein Spieler kommt aus dieser Stadt.
Aus dieser Stadt kann aber auch nie ein Spieler eingewechselt werden.

Fehlt etwa C, so gilt anfangs AAA oder AAB. Die Einwechslung eines Spielers aus C würde dann zu AAC oder ABC führen, was kein gutes Team ergibt.
Auch die Auswechslung eines Spielers aus A gegen einen aus B, wenn AAB spielt, ist nicht möglich, da BBA nicht harmoniert.
Es bleibt also immer bei AAA oder AAB.

Das ist genau das Beispiel, das ich auch hatte, nur viel besser formuliert. Schön, das in so verständlicher Form zu sehen. (Nur, dass bei mir AAA, BBB, CCC nicht dabei sind, weil es auch ohne geht.)

[MatheJuergen]

Ich bin immer noch der Meinung dass k = 42 + 4 + 2 + (4 + 2)4+2)   die Lösung ist. Mein "Verteilungsbeispiel" für k = 48 des grausamen Grinch findet ihr in # 18.

[hg1]

Ich bin immer noch der Meinung dass k = 42 + 4 + 2 + (4 + 2)4+2)   die Lösung ist. Mein "Verteilungsbeispiel" für k = 48 des grausamen Grinch findet ihr in # 18.

Ich bn mir nicht ganz sicher, ob ich dein Beispiel richtig verstehe, aber ist es nicht so, dass die B_i Mengen alle Spieler abdecken?

[Kosakenzipfel]

Nach längerem Recherchieren habe ich dabei dann ein Paper aus dem Jahr 2019 gefunden,
  in dem das Problem der Aufgabe  als Ausgangspunkt behandelt wird. 

Kannst du bitte den Link posten? Oder auch gerne die Referenz.

[MatheJuergen]

Ich bin immer noch der Meinung dass k = 42 + 4 + 2 + (4 + 2)4+2)   die Lösung ist. Mein "Verteilungsbeispiel" für k = 48 des grausamen Grinch findet ihr in # 18.

Ich bn mir nicht ganz sicher, ob ich dein Beispiel richtig verstehe, aber ist es nicht so, dass die B_i Mengen alle Spieler abdecken?

Du hast recht, der Trainer muss ja gar nicht mehr in die Menge A zurückwechseln, da alle Spieler in mindestens einer der B_i sind und somit jeder Spieler eingesetzt wurde (bei meinem Beispiel könnte nur nicht jedes Paar eingesetzt werden). Da muss ich nochmal ran. Danke für deinen Hinweis. 

[ThH]

Nach längerem Recherchieren habe ich dabei dann ein Paper aus dem Jahr 2019 gefunden,
  in dem das Problem der Aufgabe  als Ausgangspunkt behandelt wird. 

Kannst du bitte den Link posten? Oder auch gerne die Referenz.

Die Aufgabe wird im ersten Satz des Abstracts bzw. Corollary 7 (R. Mycroft zugeschrieben) beantwortet:

"Forcing large tight components in 3-graphs" von
Agelos Georgakopoulos, John Haslegrave, Richard Montgomery
European Journal of Combinatorics 77 (2019) 57–67
Link zum Paper