Kombinatorische Problemstellung |
| 11.10.2008, 13:16 | Soz.Päd. | Auf diesen Beitrag antworten » | ||
| Kombinatorische Problemstellung ein Rätsel möchte ich vorstellen, auf das ich in dem Buch "Mathematisch denken" gestoßen bin, ohne dass darin eine Lösung enthalten war. Einen Lösungsvorschlag habe ich dazu erarbeitet, aber ich bin mir nicht sicher, ob er stimmt ... . Hier das Problem: In einem Wirtshaus treffen sich n - Personen zum wöchentlichen Stammtisch, von denen jede mindestens eine Neuigkeit weiß, welche die anderen nicht kennen. Nun kommen zwei Personen immer miteinander ins Gespräch nach folgenden Regeln: Jede Person erzählt der Person, mit der sie gerade spricht, ihre eigene Neuigkeit und all das, was sie vorher von den anderen Personen erfahren hat. Wieviele 2-er-Gespräche sind in Abhängigkeit von n mindestens nötig, damit alle Personen alle Neuigkeiten erfahren haben? Anmerkung: Vielleicht kann sich ja noch jemand dazu erbarmen, etwas zu meinem vorherigen Problem "Altes Rätsel im neuen Gewand" zu schreiben? Gruß Soz.Päd. |
||||
| 11.10.2008, 13:26 | Klappergrasmuecke | Auf diesen Beitrag antworten » | ||
Hmm... Als Erstes fällt mir folgende Lösung ein: Ich wähle eine Person A aus. A führt mit jedem der anderen (n-1) Personen ein Gespräch. Somit wissen A und diejenige Person mit der A als letztes gesprochen hat alle Neuigkeiten und es haben bisher (n-1) Gespräche stattgefunden. Die übrigen (n-2) Personen, die noch nicht alles wissen, reden nun alle noch mal mit A. Dann weiß jeder alle Neuigkeiten und zu den bisherigen (n-1) Gesprächen sind (n-2) dazu gekommen. (n-1)+(n-2)=2n-3 Mit dieser Anzahl an Gesprächen klappt es auf jeden Fall. Ne Möglichkeit mit wenigeren fällt mir jetzt nicht ein... |
||||
| 11.10.2008, 13:30 | kiste | Auf diesen Beitrag antworten » | ||
Eine durchaus bessere Möglichkeit als die von Klappergrasmuecke funktioniert durch aufbauen eines Baumes. Das ist aber sicherlich nicht optimal da ich nur den Informationsfluss in eine Richtung ausnutze. Ein guter Ansatz besteht sicherlich auf Gruppenbildung, Stichwort dynamische Algorithmen, Divide&Conquer. Ich werde noch weiter darüber nachdenken 
Wie sieht den deine Lösung aus Soz.Päd? |
||||
| 11.10.2008, 13:34 | Soz.Päd. | Auf diesen Beitrag antworten » | ||
Zum Lösungsvorschlag von Klappergrasmücke: Dieser Vorschlag stimmt nach meiner Meinung nicht, denn bei 4 Personen wären dann 2*4 - 3 = 5 Gespräche nötig, aber es geht mit 4 Gesprächen: 1. Person spricht mit 2. Person. (1. Gespräch) 3. Person spricht mit 4. Person. (2. Gespräch) 1. Person spricht mit 3. Person (3. Gespräch) 2. Person spricht mit 4. Person (4. Gespräch). Zudem war bei der Aufgabenstellung ein mathematischer Beweis erwünscht, dass die angegebene Lösung wirklich die minimale Anzahl ist ... . Gruß Soz.Päd. |
||||
| 11.10.2008, 13:42 | Klappergrasmuecke | Auf diesen Beitrag antworten » | ||
Jo, da hast du wohl Recht. Es war ja auch nur ein Denkansatz, der sich blöderweise als suboptimal herausgestellt hat
|
||||
| 11.10.2008, 19:50 | AD | Auf diesen Beitrag antworten » | ||
Und, wo ist er? Karten auf den Tisch!
|
||||
| Anzeige | ||||
|
|
||||
| 12.10.2008, 13:28 | Soz.Päd. | Auf diesen Beitrag antworten » | ||
Na, ja .. schon beim Pokern gilt ... man soll die Karten nicht zu früh auf den Tisch legen ... . Gruß Soz.Päd. |
||||
| 12.10.2008, 13:31 | tigerbine | Auf diesen Beitrag antworten » | ||
Tja, und nicht jeder fällt auf einen Bluff rein.
|
||||
| 12.10.2008, 13:37 | Soz.Päd. | Auf diesen Beitrag antworten » | ||
An Tigerbiene, ja, ich glaube, so eine Antwort hatte ich förmlich provoziert . Daher: Ich präsentiere noch nicht meinen Lösungsvorschlag, aber immerhin mal mein Ergebnis ... . Ab vier Personen erhöht sich die minmale Anzahl an Gesprächen bei jeder Person, die hinzukommt um zwei, d.h. bei 4 Personen sind 4 Gespräche nötig. bei 5 Personen sind 6 Gespräche nötig. bei 6 Personen sind 8 Gespräche nötig. (usw.). Gruß Soz.Päd. |
||||
| 12.10.2008, 15:28 | AD | Auf diesen Beitrag antworten » | ||
Dass möglich ist, erledigt sich ja durch Angabe einer entsprechendne Gespächsreihenfolge. Die Frage ist, mit welchem schlüssigen Argument man die Optimalität dieser Anzahl beweist. (Ich bin mir nicht mal sicher, dass für alle wirklich optimal ist...) |
||||
| 15.10.2008, 20:41 | Soz.Päd. | Auf diesen Beitrag antworten » | ||
Hallo, O.K, um den Verdacht eines Bluffs beiseite zu räumen, nun mein Lösungsvorschlag: Behauptung: Ab 4 Personen nimmt mit jeder Person, die hinzukommt, die minimale Anzahl der nötigen Gespräche um genau 2 zu. (Bei n = 4 sind dabei 4 Gespräche nötig, was wir uns unter der Einzelfallbetrachtung erschließen müssen). Wir wissen zum einen, dass bei jeder Person, die hinzukommt, die minimale Anzahl an Gesprächen höchstens um zwei zunimmt. Denn seien bei n Personen (4<n) 2*(4 - n) + 4 Gesprächen notwendig, dann gilt für n+1,: Die "neue" Person spircht zuerst mit irgendeiner Person, und am Ende mit einer weiteren Person, die über alle Informationen verfügt, und die Bedingung ist mit 2 Gesprächen mehr erfüllt. Nehmen wir also in einem Widerspruchsbeweis an, die Anzahl an minimaler Gespräche würde sich bei n + 1 Personen um nur "1" erhöhen. a) n + 1 muss eine gerade Zahl sein, denn: Bei einer ungeraden Anzahl gäbe es mindestens eine Person, die, um alle Informationen zu erhalten, mit einer Person ein Gespräch führen müsste, die bereits alle Informationen hat (Ansonsten würden ja immer in einem Gespräch gleichzzeitig 2 Personen in deren "Abschlussgespräch" alle Informationen erhalten, was aber bei einer ungeraden Zahl nicht ginge). Also muss diese Person mindestens 2 Gesprächen (bei 4<n) führen, um zu allen Informatonen zu gelangen. Ohne sie wären dann zwei Gespräche unnötig (ihr erstes und ihr letztes, dessen anerer Teilnehmer ja schon alle Informationen hat), was aber der Voraussetzung widerspricht. b) Wir wissen also, dass n + 1 eine gerade Zahl sein müsste, wenn sich die Anzahl der notwendigen Gespräch nur um "1" erhöht. Desweiteren müssen wir davon ausgehen, dass in einem Gespräch, in dem eine Person ihre restlichen Informationen erhählt, die andere Person vorher auch noch nicht über alle Informationen verfügte, denn dies würde zu einem Widerspruch wie in a) führen. Nun betrachten wir aus den n + 1 Personen vier Personen, nennen sie 1, 2, 3, 4 mit folgenden Vorraussetzungen: Ihr vorletztes Gespräch führen die Personen 1 und 2 miteinander. Die Person 1 führt ihr letztes Gespräch mit Person 3, 2 ihr letztes mit 4. Dann kann es zwischen der Person 1 und 3 vorher zu keiner Wechselwirkung (dies bedeutet eine Verbindung, die auch über andere Personen verlaufen kann) gekommen sein, denn ansonsten müsste für die Person 1 bzw. 3 nach dem Gespräch, das zu dieser Wechselwirkung führte, noch ein weiteres vor ihrem letzten Gespräch stattfinden, in dem ansonsten nicht beide zu neuen Informationen gelangen würden. Dies führt dann dazu, dass wir ohne jene Person 1 bzw. 3, die nun mindestens drei Gespräche führen müsste, zu mindestens zwei Gesprächen - zwei Gespräche könnten wir sozusagen zu einem zusammenfassen -weniger kommen, was ein Widerspruch wäre. Dasselbe gilt für die Personen 2 und 4. Also muss es eine Wechselwirkung zwischen den Personen 3 und 4 geben. Nun fassen wir zusammen: Die Personen 1 und 2 führen ihr vorletztes Gespräch miteinander, müssen aber beide Wechselwirkungen zu weiteren Personen haben.Dadruch ergeben sich mindestens 3 notwendige Gespräche. Die Personen 3 und 4 haben ebenfalls eine Wechselwirkung miteinander. Wenn es unter den beiden nun eine Person gäbe, die aber vor ihrem letzten Gespräch keine weitere Wechselwikrung mit anderen Personen hätte - im Gegensatz zu vorher müssen wir diesen Fall betrachten, da wir ja nicht davon ausgehen können, dass die Personen 3 und 4 ihr vorletztes Gespräch überhaupt miteinander führen - , dann hätte die Person - nennen wir sie zum Verständnis Person 1 -, die als letztes mit ihr spricht, bereits alle notwenigen Informationen, wenn es die Personen 3 und 4 nicht gäbe. Dasselbe gilt für Person 2, denn schließlich spricht Person 1 mit ihr als vorletztes. Ohne die Personen 3 und vier wären dann also vier Gespräche weniger notwenig, was ein Widerspruch wäre. Also: 3 und 4 haben mindestens eine Wechselwirkung miteinander, aber auch noch vor ihrem letzten Gesprächen mit weiteren Personen: Daraus ergibt sich die Notwendigkeit von mindestens 3 Gesprächen. Die beiden letzten Gespräche ergeben 2 notwenige Gespräche. Ohne diese 4 betrachteten Personen wären also 3 + 3 + 2 = 8 Gespräche weniger nötig: Widerspruch zur Voraussetzung, dass sich aber erst bei n + 1 die Anzahl der notwendigen Gespräche um "1" erhöht. Dabei beachte man aber nochmals gesondert die Fälle n = 6 und n = 8 nachrechnen (einsetzen in die hergeleitete Formel und vergleichen mit den Erkennnissen; beispielsweise erhöht sich die Anzahl der notwendigen Gespräche von 3 auf 4 wirklich nur um eines.) Gruß Soz.Päd. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|