Existenzbeweis, Runder Tisch Bekanntschaften |
| 24.01.2022, 02:30 | MatheLover069 | Auf diesen Beitrag antworten » | ||||
| Existenzbeweis, Runder Tisch Bekanntschaften Wir behandeln gerade das Extremalprinzip und dazu habe ich folgende Aufgabe: In einer Gruppe von 10 Personen kenne jede Person mindestens 5 andere. Zeige, dass es m¨oglich ist, die 10 Personen so um einen runden Tisch anzuordnen, dass jeder zwischen zwei Bekannten sitzt Meine Ideen: Ich bin ehrlich gesagt nicht sicher, ob ich das Problem richtige verstehe. Wenn jeder seinen Nachbarn kennen soll, dann müsste doch jeder am Tisch sich gegenseitig kennen, was offensichtlich nicht der Fall ist. Stehe ein wenig auf dem Schlauch. |
||||||
| 24.01.2022, 10:27 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Da gab es doch ein Déjà-vu bei mir (ist 3 Jahre her): https://www.onlinemathe.de/forum/Extremalprinzip-3 Der Nachweis der Hilfsaussage "Sitzt Person a links neben Person b, die a nicht kennt, so gibt es Person c und d, sodass c links neben d sitzt und sodass sich a und c sowie b und d kennen" ist im verlinkten Thread nicht geschehen - falls es da noch Probleme gibt, bitte melden. Der Beweis funktioniert auch für folgende hinsichtlich der Personenzahl verallgemeinerte Behauptung:
|
||||||
| 24.01.2022, 10:39 | IfindU | Auf diesen Beitrag antworten » | ||||
Alternativ kann man auch mit diskreter Mathematik argumentieren: Hamiltonkreis. |
||||||
| 24.01.2022, 11:09 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Hatte ich noch vergessen:
Da liegt wohl ein grundlegendes Missverständnis des Begriffes "Nachbarschaft am Runden Tisch" vor: Das ist so gemeint, dass nur die beiden links und rechts von einem sitzenden Personen als Nachbarn angesehen werden, nicht die anderen sieben Personen am Tisch! Und gefordert wird nur, dass man die Nachbarn kennt (was natürlich nicht ausschließt, dass man ggfs. noch ein paar weitere der Leute kennt). |
||||||
| 24.01.2022, 12:25 | MatheLover069 | Auf diesen Beitrag antworten » | ||||
| RE: Existenzbeweis, Runder Tisch Bekanntschaften Hallo, Den Hinweis hatte ich im Buch von Grieser auch gefunden gehabt. Aber die verstehe ich nicht richtig, da wenn Person a links neben Person B sitzt, ist ja A ein Nachbar von B. Aber wenn B A nicht kennt, dann stimmt die Aussage doch nicht? Vor 3Jahren MPB an der UOL gehabt? Haha |
||||||
| 24.01.2022, 13:31 | MatheLover069 | Auf diesen Beitrag antworten » | ||||
| RE: Existenzbeweis, Runder Tisch Bekanntschaften Ich habe mich damit jetzt noch weiter beschäftigt und habe glaube dies bemerkt: Wir konstruieren uns den Tisch so wie im Hinweis, und sagen, dass das die Reihenfolge mit der minimalsten Fehleranzahl ist. Da aber offensichtlich durch das Wechseln zweier Plätze von Nachbarn, eine Tischreihenfolge mit weniger Fehlern konstruiert wurde, erhalten wir einen Widerspruch. Aber wie begründet man den Hinweis und wieso ist das die Reihenfolge mit minimalsten Fehler, wieso können wir das so voraussetzen? |
||||||
| Anzeige | ||||||
|
|
||||||
| 24.01.2022, 14:31 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
RE: Existenzbeweis, Runder Tisch Bekanntschaften
Willst du, dass man dir alles auf dem Silbertablett serviert oder besitzt du noch soviel Ehre, es wenigstens doch mal selbst zu probieren?
Für jede Sitzordnung können wir zählen, wie viele der 10 Nachbarpaare NICHT bekannt sind, das bezeichnen wir als Fehleranzahl dieser Sitzordnung. Nun kann man ja das Minimum dieser Fehleranzahl über alle 10! möglichen Sitzordnungen bestimmen, dies sei die Anzahl . Die Behauptung sagt nun . Ein indirekter Beweis dieser Behauptung startet nun mit der Annahme, dass diese Behauptung falsch ist, d.h., dass es 10 Leute mit einer Bekanntschaftsstruktur gemäß Voraussetzungen gibt, so dass gilt. Und diese Annahme wird zum Widerspruch geführt in der Weise, dass wir aus einer Sitzordnung mit Fehleranzahl (die es ja laut Definition von geben muss!) eine Sitzordnung konstruiert wird mit Fehleranzahl , was einen Widerspruch zur Minimalität von darstellt. |
||||||
| 24.01.2022, 16:11 | MatheLover069 | Auf diesen Beitrag antworten » | ||||
| RE: Existenzbeweis, Runder Tisch Bekanntschaften Hey, sorry so war das nicht gemeint. Ich verstehe wie ich vom Hinweis zum Widerspruch komme und damit die Behauptung beweise. Bei der Begründung des Hinweises mache ich mir Schwierigkeiten. Da Person a Person b nicht kennt, gibt es nach Vor. andere Personen die er kennen muss am Tisch. Also kann es auch Person c geben die dann links neben d sitzt. Dabei kann Person a Person c kennen und Person b Person d kennen. Ich sehe nicht wirklich das Problem, bzw. wieso das gelten muss. Vielleicht kannst du mich da ja in die richtige Richtung lenken, danke! |
||||||
| 24.01.2022, 16:18 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Die Voraussetzung, dass jede Person mit mindestens 5 anderen Personen bekannt ist, darfst/musst du auch einsetzen. Und zwar 5, nicht bloß 4 oder gar nur 3... Wenn es beispielsweise nur drei sind, dann gibt es Konfigurationen, wo keine solche Sitzordnung möglich ist: https://de.wikipedia.org/wiki/Petersen-Graph |
||||||
| 24.01.2022, 17:43 | MatheLover069 | Auf diesen Beitrag antworten » | ||||
Also bei den Personen a,b,...,j kennt a mindst. 5 von c,...,j und b ebenfalls. Muss ich irgendwie mit betrachen, dass a links neben b und c links neben d sitzt? Falls ja, wie würde ich das am Besten machen? Irgendwie finde ich da keinen guten Weg |
||||||
| 24.01.2022, 21:15 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Einfach streng logisch durchdenken: a ist mit b nicht bekannt, mit seinem linken Nachbarn aber eventuell - das bedeutet, dass unter den restlichen 7 Personen mindestens 4 Bekannte von a sind, die bezeichne ich mal als vorerst mögliche Kandidaten für c. Schauen wir uns die rechten Nachbarn dieser c-Kandidaten an: Die Annahme, dass keiner dieser Nachbarn mit b verbunden ist würde bedeuten, dass b maximal 8-4 = 4 Bekannte hat, Widerspruch zu den vorausgesetzten mindestens 5 Bekannten. Daher gibt es einen solchen mit b bekannten Nachbarn, und der ist dann unser gesuchtes d, während seiner linker Nachbar und c-Kandidat dann das passende c ist. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
