schubfachprinzip

Neue Frage »

9-er Komplement Auf diesen Beitrag antworten »
schubfachprinzip
nabend zusammen,

kann mir vielleicht einer von euh folgende aufgabe ERKLÄREN????


Beweisen Sie:
In jeder Gruppe P von Personen gibt es zwei Personen, die die gleiche Anzahl von Personen kennen. ”Kennen“ ist dabei als symmetrische Relation gemeint, d.h A kennt B folgt B kennt A.


weiss gar nicht wie ich anfange soll ????


danke i. voraus Tanzen
carsten Auf diesen Beitrag antworten »

Nehmen wir mal an Deine Gruppe besteht aus n Leuten.

Betrachten wir jetzt eine Person aus der Gruppe, wieviele verschiedene Leute kann er denn kennen?

Vergleicht man jetzt die Anzahl Moeglichkeiten wieviele Personen eine Person kennen kann und die Gesamtanzahl Personen, kann man schon fast die Behauptung schlussfolgern. Es ist nur eine Kleinigkeit extra zu beachten.

Gruesse
Carsten
Tobias Auf diesen Beitrag antworten »

Man benutzt hierfür das Schubfachprinzip und einen Beweis durch Widerspruch.

Deine Schubfächer sind die Personen .

Nun behauptest du: Es gibt KEINE zwei Personen, die gleichviele andere kennen.

Jetzt verteilst du mal fröhlich und stößt hoffentlich auf einen Widerspruch. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »