23. AUFGABE DER WOCHE

Jeder der n Mitarbeiter einer Fakultät für Mathematik habe sich eine Menge potentieller ’Aufgaben der Woche’ ausgedacht. Immer dann, wenn ein Mitarbeiter einen anderen anruft, werden alle ausgedachten Aufgaben der beiden Gesprächspartner ausgetauscht, d.h. am Ende eines Gesprächs kennt jeder der beiden Gesprächspartner zusätzlich zu den Aufgaben, die er bereits kennt auch alle Aufgaben, die sein Gesprächspartner kennt. Was ist im schlimmsten Fall (d.h. wenn anfangs die Aufgabenmengen je zweier Mitarbeiter disjunkt sind) die kleinste Anzahl von Anrufen, die gemacht werden müssen, damit alle Mitarbeiter alle ausgedachten Aufgaben kennen?

(Was passiert, wenn man für ein k ≥ 2 anstatt 2-er auch k-er Konferenzen zulässt?)

Die ’Aufgabe der Woche’ ist eine inoffizielle Belustigung. Für den Urheber der ersten Lösung liegt in V4-206 ein namhafter Schokoriegel bereit. Vorschläge für schöne neue Aufgaben werden dankend aber schokoriegelfrei in V4-206 angenommen. Den Lösungsstatus einer Aufgabe, sowie die normalerweise montags neu erscheinende Aufgabe findet man unter http://www.math.unibielefeld.de/∼florian/adw/ .