Problem vom 22.6.98: Zu einem skandalträchtigen Thema wissen n Personen jeweils unterschiedliche Teile des gängigen Tratsches. Wenn sie nun untereinander telephonieren und zwei Teilnehmer dabei die ihnen zum jeweiligen Zeitpunkt vorliegenden Informationen vollständig austauschen: Was ist die kleinste Zahl von Telefonaten, die nötig ist, um zu erreichen, daß jeder von jedem alles weiß?
Gossip: Cogito 1/1999 [Heinrich Hemme] Ich hatte in den letzten Wochen etliche Überstunden gemacht und mir nun deshalb einen Nachmittag von der Arbeit frei genommen. Das Wetter war schön, und ich vertrödelte die Zeit im Liegestuhl. Plötzlich fiel mir ein, dass ich meinem Chef versprochen hatte, ihm den Monatsbericht heute zu geben. Ich hatte ihn gestern früh geschreiben, aber vergessen, ihn abzugeben. "Ich rufe rasch meinen Kollegen an, er soll den Bericht dem Chef bringen", dachte ich und ging ins Haus um zu telefonieren. Doch meine Tochter saß am Telefon und unterhielt sich mit jemandem über irgendwelche Mathematikaufgaben. "Quasselliese", brummte ich, und ging wieder nach draußen. Als ich nach weiteren 10, 20 und 40 Minuten wieder versuchte zu telefonieren, hatte ich genausowenig Erfolg. Schließlich riß mir der Geduldsfaden, und ich schimpfte: "Hör endlich auf zu quasseln. Ich muß dringend in der Firma anrufen." "Bin schon fertig, Papi", sagte Christina fröhlich und legte den Hörer auf. Als ich mein Telefonat beendet hatte und wieder nach draußen kam, saß Christina auch auf der Terrasse. "Mit wem hast du eigentlich stundenlang telefoniert?" fragte ich sie. "Ach, nur mit einigen Mädchen aus meiner Klasse," sagte sie. "Wir haben die Matheaufgaben ausgetauscht." "Wie bitte?" Ich verstand nicht recht, was sie meinte. "Das ist doch ganz einfach, Papi. Wir hatten Matheaufgaben auf, und wir sind sieben Mädchen in der Klasse. Also hat jede von uns eine gerechnet. Und dann haben wir miteinander telefoniert, so dass nun jede von uns die Lösungen aller sieben Aufgaben hat." "Aha", meinte ich, "wenn ich dich richtig verstehe, hat jede von euch sieben einmal mit jeder der anderen sechs telefoniert. Das sind also insgesamt 21 Telefonate." Christina sah mich vorwurfsvoll an. "Papi, du hast mir selbst erzählt, dass uneffektives Arbeiten Verschwendung ist! Wir haben uns natürlich eine Methode überlegt, mit der man mit einem Minimum an Telefonaten die Ergebnisse aller sieben Aufgaben an alle sieben Mädchen durchgeben kann." Mit wie vielen Telefonaten kamen die sieben Mädchen aus? Gossip: Matherätsel 14 Sechs neue Fummel für die Doggemenda. Jetzt wird's vornehm beim Matherätsel. Denn schliesslich steht die Doggemenda elf vor der Düre. Und da geht es um die angemessene Erscheinung der Damen vom Dokumenta-Team. Zwei Fragen ranken sich um das wichtige Thema. Grosse Aufregung unter den Damen vom Team. 's Heike und 's Lowise, 's Karin und 's Barbara, ja sogar 's Gertie und 's Zoffie schnattern aufgeregt durcheinander: Jetzt wird es aber wirklich allerhöchste Zeit, denn der achte Juni rückt näher und näher. Und eines eines ist doch wohl klar: Zur feierlichen Eröffnung der Doggemenda muss selbstverständlich ein neuer Fummel her! Das ist ja wohl das Mindeste! Und dazu gehören natürlich auch neue Schuhe, denn keines der Mädels will die ahlen Patschen von der Doggemenda X dieses Jahr nochmal wieder anziehen. "Mäh hon zwor fill ze duhn", spricht's Lowise, "awer wam'mäh missen, dam wum'mäh moh usschwärmen!" Und mit diesen Worten machen sich die sechs Mädels auf in die Stadt, um nach dem geeigneten "kleinen Schwarzen" mit den dazugehörigen Pumps und weiteren künstlerischen Accessoires zu suchen. Da sie alle getrennt einkaufen wollen, vereinbaren sie vorher miteinander, sich abends über ihre erfolgreichen Einkäufe am Telefon auszutauschen. Hierzu nun zwei Fragen: Erste Frage: Wie viele Anrufe (Nur zwischen zwei Personen wird telefoniert! Keine Konferenzschaltungen oder ähnliche Tricks!) sind erforderlich, damit alle sechs Mädels über die Einkäufe aller Freundinnen informiert sind? Dabei werden bei jedem Telefonat alle bereits erhaltenen Informationen beider Gesprächsteilnehmerinnen ausgetauscht. Hieran schliesst sich noch eine, etwas schwierigere, zweite Frage an: Wie gross ist die kleinstmögliche Anzahl der für den obigen Informationsaustausch erforderlichen Telefonate? Bitte die Behauptung begründen.
Die Minimalzahl von Telefonaten ist:
1, für n=2; 3, für n=3; und 2n-4 für n>3.
Daß für n>3 diese Zahl von
Telefonaten ausreicht, zeigt die folgende Überlegung:
Man wähle vier
Personen A, B, C, D als "Kerngruppe" G. Jede Person außerhalb von G, ruft
(irgend)ein Mitglied von G an (n-4 Telefonate). Dann telefonieren A-B, C-D, A-C,
B-D. Jetzt weiß jeder in G über alles bescheid. Nun muß nur noch jede Person
außerhalb von G nochmals (irgend)ein Mitglied von G anrufen. Insgesamt werden
bei diesem Vorgehen also (n-4) + 4 + (n-4) = 2n - 4 Gespräche geführt.
Zur Minimalität und für weiterführende Überlegungen siehe: