Diskrete Mathematik < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:17 Fr 09.06.2006 | | Autor: | Sunny85 |
| Aufgabe | | Der Club der Ehemaligen einer Schule hat 90 Mitglieder. Jeder von ihnen hat 10 Freunde im Club. Man zeige, dass jedes Clubmitglied 3 Leute zum Essen so einladen kann, dass jede der vier Personen am Tisch mit mindestens zwei der drei anderen befreundet ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Die Mitglieder kann man durch Knoten repräsentieren und zwischen zwei Knoten existiert jeweils eine Kante, wenn die beiden Mitglieder miteinander befreundet sind. Soweit ist es mir klar, auch was gefragt ist, aber ich weiß nicht wie ich es zeigen soll. Ich glaube man könnte sich erstmal einen beliebigen Knoten x nehmen und sich alle Nachbarn von x (das sind 10) angucken. aber weiter komme ich nicht
|
|
| |
|
Hallo und guten Morgen,
nehmen wir an, für einen Ehemaligen v ginge das nicht.
Dann kann es innerhalb seiner Nachbarschaft [mm] u_1,\ldots u_{10} [/mm]
keinen Pfad der Länge 2 geben.
Jeder der Knoten [mm] u_i,1\leq i\leq [/mm] 10 hat somit mindestens 8 Nachbarn unter den restlichen 90-11 Knoten.
Wir sind fertig, wenn wir zeigen, dass mindestens zwei Knoten der [mm] u_i [/mm] einen gemeinsamen Nachbarn unter diesen 79
restlichen Knoten haben. Das muss aber so sein, denn wären die Nachbarschaften paarweise disjunkt, so bräuchten wir dazu insgesamt noch 80
Knoten - haben aber nur 79.
Gruss,
Mathias
|
|
|
|
