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.
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).
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.
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.