06 Krach im Wichtelamt

© Vira Raichenko, MATH+

Autoren: Olaf Parczyk, Silas Rathke

Projekt: EF 1-12

Aufgabe

Politik ist nicht leicht! Auch am Nordpol nicht. Dort entscheiden zehn gewählte Bürokratie-Wichtel über die Gesetze im ewigen Eis. Doch nun ist ein riesiger Streit darüber entstanden, wofür im nächsten Jahr Geld ausgegeben werden soll. Manche wollen das Geld einsetzen, um den Kindern bessere Geschenke zu machen. Andere wollen es lieber in einen leichteren Schlitten investieren, um die Rentiere zu entlasten, und wieder andere wollen das Wichteldorf mit moderneren Heizungen ausstatten. Der Streit wurde so erbittert geführt, dass insgesamt 20 Feindschaften entstanden sind. Eine Feindschaft besteht dabei immer aus genau zwei Bürokratie-Wichteln, die sich so in die Haare gekriegt haben, dass sie nicht mehr miteinander sprechen. Um die Wogen zu glätten, lädt Oberwichtel Olav die zehn Bürokratie-Wichtel zu einem Arbeitstreffen ins Wichtelamt ein. Dort sollen in unterschiedlichen Räumen an Lösungen gearbeitet werden. Ein einziger Raum reicht dafür leider nicht aus, da verfeindete Bürokratie-Wichtel nicht im selben Raum arbeiten können. Unglücklicherweise hat Olav den Überblick darüber verloren, wer mit wem verfeindet ist – er weiß nur, dass es genau 20 Feindschaften sind. Deswegen möchte Olav die Räume so buchen, sodass diese für alle möglichen Arten von Feindschaften ausreichen würden.

Was ist die kleinste Anzahl k an Räumen, die Olav braucht, sodass man die zehn Bürokratie-Wichtel bei 20 Feindschaften in jedem Fall auf k Räume aufteilen kann, ohne dass verfeindete Wichtel im selben Raum landen?

Antwortmöglichkeiten:

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10

Projektbezug:

Im Projekt “Learning Extremal Structures in Combinatorics” verwenden wir Ansätze aus dem Bereich der künstlichen Intelligenz und des maschinellen Lernens, um neue Konstruktionen für Graphen mit bestimmten Eigenschaften zu finden. Die vorliegende Aufgabe lässt sich gut als extremales Problem in der Graphentheorie formulieren,  ähnlich wie die Probleme, die wir in diesem Projekt studieren.