| Autor |
Beitrag |
    
wo bla 2
| | Veröffentlicht am Dienstag, den 14. November, 2000 - 12:34: | 
|
Angenommen in einem Dorf leben 15 Männer und 10 Frauen. Jede Frau ist mit einer bestimmten Anzahl von Männern befreundet. Der könig des landes kommt in das dorf, und bestimmt 10 Männer, die heiraten sollen. Warum sind mindestens 60 Freundschaften (zwischen Frauen und Männern) nötig, damit, egal welche 10 Männer ausgewählt werden, jede Frau einen Mann heiraten kann, mit dem sie auch befreundet ist. |
Matroid (Matroid)
| | Veröffentlicht am Dienstag, den 14. November, 2000 - 20:55: |
|
Wenn es weniger als 60 Freundschaften wären, dann ist es sicher, daß mindestens eine Frau mit höchstens 5 Freundschaften existiert.
Verteile nämlich 59 Freundschaften auf 10 Schubladen (Frauen). Selbst bei gleichmäßigster Verteilung, enthält mindestens eine Schublade höchstens 5 Freundschaften. Diese (höchstens) 5 Freundschaften könnten nun gerade zu den 5 Männern bestehen, die für die Massenheirat nicht ausgewählt werden.
Beachte: "könnte", also man kann es dann nicht ausschließen.
Aber auch bei 60 Freundschaften kann man nicht sicher sein, daß jede Frau mit einen befreundeten Mann verheiratet wird.
Man könnte ja ungünstigstenfalls annehmen, daß alle 10 Frauen mit den gleichen 6 Männern befreundet sind und vom König nur 1 von diesen 6 und weitere 9 von den Männern, mit denen keine Frau befreundet ist, ausgewählt werden.
Man kann also feststellen: wenn es weniger als 60 Freundschaften gibt, dann ist es zwingend, daß mindestens eine Frau einen nicht befreundeten Mann heiraten muß.
Evtl. aber auch mehr als eine: Kann ja auch sein, daß vier von den 10 Frauen mit jedem Mann befreundet sind (macht 4*15=60) und die anderen Frauen keine Freundschaften mit Männern haben.
Wir haben es hier mit einer hinreichenden Bedingung für die nicht-Existenz einer Lösung zu tun.
Die Anzahl 60 sagt aber nichts darüber aus, ob eine Lösung existiert.
Formal geschrieben:
[n<60] => not [Für alle Auswahlen von 10 Männern existiert eine Lösung]
oder auch
[n<60] => [Es existiert eine Auswahl von 10 Männern für die keine Lösung existiert]
Die Negation davon:
[Für alle Auswahlen von 10 Männern existiert eine Lösung] => n>=60
Gruß
Matroid |
|
