Lösungsvorschläge A6

[Pierrot]

Prima Aufgabe! Ebenso wie A21 Eisfeld super!!! - beides aus der Feder des Teams Olaf Parczyk und Silas Rathke  - bitte mehr davon nächsten Dezember :-)


Ein vollständiger Graph sperrt am besten. Der vollständige Graph mit 6 Knoten hat 15, der mit 7 Knoten 21 Kanten. Da es 20 Feindschaften gibt reichen 6 Räume, um die Streithähne zu trennen.
Bei einer Feindschaft mehr wäre es 7 Räume gewesen.

https://www.dropbox.com/scl/fi/9elbh1st3...zr38u&dl=0

[Georg J. aus D.]

Ich bin mir nicht sicher, ob die obige Argumentation schon alle Feindschaftsverteilungen umfasst. Daher habe ich folgende Überlegungen angestellt:

Wenn 6 Räume nicht reichen, dann gibt es einen Wichtel, der mit 6 anderen verfeindet ist. Weiter ohne diesen einen Wichtel.
Es bleiben:
9 Wichtel, 14 Feindschaften
Wenn 5 Räume nicht reichen, dann gibt es einen Wichtel, der mit 5 anderen verfeindet ist. Weiter ohne diesen einen Wichtel.
Es bleiben:
8 Wichtel, 9 Feindschaften
Wenn 4 Räume nicht reichen, dann gibt es einen Wichtel, der mit 4 anderen verfeindet ist. Weiter ohne diesen einen Wichtel.
Es bleiben:
7 Wichtel, 5 Feindschaften
Wenn 3 Räume nicht reichen, dann gibt es einen Wichtel, der mit 3 anderen verfeindet ist. Weiter ohne diesen einen Wichtel.
Es bleiben:
6 Wichtel, 2 Feindschaften
Wenn 2 Räume nicht reichen, dann gibt es einen Wichtel, der mit 2 anderen verfeindet ist. Weiter ohne diesen einen Wichtel.
Es bleiben:
5 Wichtel, 0 Feindschaften
1 Raum reicht für diese 5 Wichtel. Plus je ein Raum für die 5 oben entfernten Wichtel -> 6 Räume reichen.

[Mathe Juergen]

Aus 6 Wichteln kann man 6 über 2 = 15 Paare bilden, d.h. man kann 6 Wichtel auswählen und jeder der sechs Wichtel ist mit jedem der anderen 5 Wichtel aus dieser Menge "verfeindet". Somit müssen alle 6 Wichtel in einen unterschiedlichen Raum ==> Man benötigt also mindestens 6 Räume. Für eine Menge von 7 Wichtel würde man schon 7 über 2 = 21 "Feindschaften" benötigen. Also kann der 7.Wichtel nicht mit allen 6 Wichtel verfeindet sein und somit kann er in einen bereits "besetzten" Raum gehen. Man benötigt also keine weiteren Räume (denn jeder Wichtel kann als 7.Wichtel angesehen werden).

[Fanbusfahrer]

Jop. Das habe ich auch so. Beide Varianten sind interessant.

PHP-Code:

Um eine maximale Anzahl von Räumen zu gewährleisten, muss es maximal viele Feindschaften von verschiedenen Personen geben. Wir starten also, dass Person 1 und 2 befeindet sind. Dann muss Person 3 auch mit 1 und 2 befeindet sein, damit diese drei Personen nicht in einem Raum sein dürfen. Person 4 ist dann mit 1-3 befindet, Person 5 mit 1-4 und Person 6 mit 1-5. Die Summe an Feindschaften ist dann 5+4+3+2+1=15. Für Person 7 ist es nicht möglich noch mit sechs Personen befeindet zu sein, sodass sie z. B. dann noch mit fünf Personen befeindet ist. Die Summe an Feindschaften ist dann 20, die kleinste Anzahl an Räumen dann 6. 
Die korrekte Antwort ist damit 6. 


[hg1]

Ich habe mir wie folgt überlegt, dass man nie mehr als 6 Räume braucht:

Betrachte eine Aufteilung in eine kleinstmögliche Zahl von Räumen. Angenommen es wären 7 Räume oder mehr, dann gibt es mindestens 7 über 2 = 21 Paare von Räumen. Da es aber nur höchstens 20 Feindschaften gibt muss es dann zwei Räume geben, zwischen denen es gar keine Feindschaften gibt --> diese Räume könnte man also gefahrlos zusammenlegen: ein Widerspruch dazu, dass die Zahl von Räumen kleinstmöglich war.