© Friederike Hofmann, MATH+
Autoren: Olaf Parczyk, Silas Rathke (FU Berlin)
Projekt: Learning Extremal Structures in Combinatorics (EF 1-12)
Aufgabe
In der technischen Abteilung arbeiten zehn Wichtel in zehn Büros an allen möglichen technischen Problemen, die bei der größten Geschenkeproduktion der Welt auftreten können. Wegen des Klimawandels und dem damit verbundenen Anstieg des Meeresspiegels erleiden jedoch drei Büros einen Wasserschaden und sind von nun an unbenutzbar. Jetzt haben wir also zehn Wichtel, aber nur noch sieben Büros. Was soll man nun tun?
Die Lösung ist schnell gefunden: Jeden Tag kommen nur sieben Wichtel in die technische Abteilung, und die anderen drei arbeiten von Zuhause aus. Sicherheitswichtel Willi hat die wichtige Aufgabe, zehn Wichtel mit Schlüsseln für die Büros auszurüsten. Jeder Schlüssel passt nur in ein spezifisches Büroschloss und wird an einen Wichtel verteilt. Ein Wichtel kann sogar mehrere Schlüssel erhalten. Insbesondere können Büros auch von mehreren Schlüsseln geöffnet werden.
Willi hat eine klare Regel bei der Schlüsselverteilung: Nachdem die Schlüssel verteilt sind, darf es keine Rolle spielen, welche sieben Wichtel in die technische Abteilung kommen. Es muss immer möglich sein, die sieben Wichtel den sieben funktionierenden Büros zuzuordnen, sodass jeder Wichtel Zugang zu einem Büro hat, mit dem passenden Schlüssel. Das Tauschen oder Ausleihen von Schlüsseln ist strengst verboten.
Natürlich könnte Willi jedem Wichtel einen Schlüssel für jedes Büro geben, was bedeuten würde, dass er insgesamt siebzig Schlüssel herstellen müsste. Doch Willi überlegt, ob es auch mit weniger Schlüsseln möglich ist. Er sucht nach der kleinsten Anzahl, k , von Schlüsseln, die er insgesamt verteilen muss, um die vorherige Regel zu erfüllen. Welche Aussage über k ist korrekt?
Antwortmöglichkeiten:
- k < 20
- 20 \le k < 25
- 25 \le k < 30
- 30 \le k < 35
- 35 \le k < 40
- 40 \le k < 45
- 45 \le k < 50
- 50 \le k < 55
- 55 \le k < 60
- 60 \le k
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.