 |
 |
 |
 |
 |
 |
Startseite » Forum » Extremalprinzip
Extremalprinzip
Universität / Fachhochschule
Sonstiges
Tags: Extremal, Extremalaufgabe, Extremalprinzip, extremalproblem
 
|
  |
|---|
|
Hallo ihr Lieben! Ich brauche einmal Hilfe zu einem Extremalprinzip…. Die Aufgabe: In einer Gruppe von 10 Personen kenne jede Person mindestens 5 andere. Zeigen Sie, dass es möglich ist, die 10 Personen so um einen runden Tisch anzuordnen, dass jeder zwischen zwei Bekannten sitzt. Der Hinweis ist dabei Zeigen Sie zunächst Folgendes: 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 und b und d kennen. Betrachten Sie dann die Sitzordnung mit den wenigsten Fehlern. Der Tutorentipp war dabei dass das Schubfachprinzip hilfreich wäre. Ich wäre euch dabei über jeden Tipp sehr dankbar! Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
> 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 und b und d kennen. (*) Wenn du das nachweisen kannst, bist du praktisch fertig, vor allem wenn man dies befolgt > Betrachten Sie dann die Sitzordnung mit den wenigsten Fehlern. D.h., wir ordnen jeder Sitzordnung die Anzahl der Nachbarpaare zu, die sich NICHT kennen. Nun betrachten wir eine Konfiguration mit minimaler solcher Fehlerzahl. Angenommen, die ist größer Null, dann findet man Nachbarn a,b, die sich nicht kennen, auf die wendet man (*) an. Ausgehend von Tischordnung ab(1)cd(2) betrachten wir jetzt die Tischordnung ac(1')bd(2), wobei (1') dieselben Leute wie (1) sind, nur in umgekehrter Reihenfolge. Die so konstruierte Tischordnung hat nun mindestens einen Fehler weniger als die Ausgangsordnung, was im Widerspruch steht zur geforderten Minimalität der Fehlerzahl in der Ausgangsordnung. P.S.: Schubfachprinzip? Naja, vielleicht zum Nachweis von (*), obwohl man das zur Begründung nicht unbedingt benötigt. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1456216
1456084