Schubfachprinzip < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:47 So 17.06.2007 | | Autor: | LeMaSto |
| Aufgabe | Zeigen Sie mit dem Schubfachprinzip
a) In jeder Gruppe von 6 Personen, in der je zwei Personen entweder befreundet oder verfeindet sind, gibt es 3 Personen, die paarweise befreundet oder paarweise verfeindet sind.
b) Seien n [mm] \ge [/mm] 2 Personen in einem Raum. Dann gibt es zwei Personen, welche mit der gleichen Anzahl von Personen im Raum bekannt sind. |
hey...
wär lieb, wenn ihr mir helfen könntet. ich hab das schubfachprinzip leider noch nicht verstanden......
auf jeden fall schon einmal danke!
lg lema
|
|
| |
|
Das Schubfachprinzip eine Methode, um Aussagen über eine endliche Menge zu machen.
Das Schubfachprinzip besagt:
Falls man n Objekte auf m Mengen (n,m > 0) verteilt, und n größer als m ist, dann gibt es mindestens eine Menge, in der mehr als ein Objekt landet.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:54 So 17.06.2007 | | Autor: | LeMaSto |
ok, das hört sich plausibel an. aber ich was bedeutet das jetzt für diese beiden aufgaben!?
|
|
|
| |
|
Auch wenn es schon überfällig ist - Ich würde es so beweisen:
Vor: Sei A eine Gruppe von 6 Personen, die jeweils paarweise befreundet oder verfeindet sind.
Beh: Es gibt 3 Personen, die paarweise befreundet oder verfeindet sind.
Bew: In dieser Gruppe gibt es [mm] \pmat{6\\2}=15 [/mm] Möglichkeiten für Kombinationen.
Diese 15 Paarkombinationen werden auf die Mengen V:= Menge der verfeindeten Paare und B:=Menge der befreundeten Paare verteilt.
Damit gibt es immer eine Menge, deren Mächtigkeit [mm] \ge [/mm] 8 ist
Nehmen wir nun oBdA an Mächtigkeit von B [mm] \ge [/mm] 8. Es sind also mindestens 8 Freundschatfspaare in dieser Gruppe von 6 Personen.
Davon müssen dann mindestens 3 paarweise untereinander befreundet sein, denn in diesem Fallvon 8 befreundeten Paarkombinationen sind mindestens 2 Personen mit 2 anderen befreundet, womit eine Dreiergruppierung gegeben ist. Je mehr Freundschaftsverbindungen dazukommen. desto mehr solcher Gruppen lassen sich dazu zählen. Also gilt die Behauptung.
MfG
Knuddelbunti
|
|
|
| |
|
> Zeigen Sie mit dem Schubfachprinzip
> b) Seien n [mm]\ge[/mm] 2 Personen in einem Raum. Dann gibt es zwei
> Personen, welche mit der gleichen Anzahl von Personen im
> Raum bekannt sind.
Eine Person kann demnach mit zwischen $0$ und $n-1$ Personen im Raum bekannt sein. Es ist aber nicht möglich, dass zugleich eine Person mit $0$ und eine Person mit $n-1$ Bekannten im Raum vorhanden sind. Also bleiben nur $n-1$ Möglichkeiten für die Anzahl von Bekannten im Raum bei $n$ Personen insgesamt. Gemäss Schubfachprinzip muss es demnach mindestens zwei Personen mit derselben Anzahl Bekannten im Raum geben.
|
|
|
|
