Problem mit Äquavalenzrelationen! SOS!

Question

Aufgabe:

Auf einem Fest treffen sichnPersonen. Zeigen Sie, dass zwei von diesen mit derselbenAnzahl von Anwesenden bekannt sind.Hinweis: Bekannt sein soll reflexiv sein, d.h. wenn eine Person eine andere kennt, dannauch umkehrt

Problem/Ansatz: ich muss diese Aufgabe lösen, hab aber leider keine Ahnung wie!

habt ihr vielleicht Tipps für mich?

Mansi

Comments

Bekannt sein soll reflexiv sein, d.h. wenn eine Person eine andere kennt, dannauch umkehrt

Nein, das heißt es nicht.

Reflexiv heißt, dass jeder mit sich selbst bekannt ist.

"wenn eine Person eine andere kennt, dann auch umkehrt" ist symmetrisch.

Ich weiß das, weil ich die beiden Dinger immer verwechsel und deshalb gerade noch mal zur Sicherheit nachgeschaut habe.

---

ja du hast recht. hast du eine Ahnung wie ich sie lösen könnte?

---

Irgendwas mit Schubfachprinzip. Details kenne ich im Moment nicht.

---

Vom Duplikat:

Titel: Auf einem Fest treffen sich n Personen

Stichworte: aussagen,stammfunktion

Aufgabe:

Auf einem Fest treffen sich n Personen. Zeigen Sie, dass zwei von diesen mit derselben
Anzahl von Anwesenden bekannt sind.
Hinweis: Bekannt sein soll symmetrisch sein, d.h. wenn eine Person eine andere kennt,
dann auch umkehrt

Answer 1

Du kannst das Ganze als Graphenproblem modellieren: Jede Person ist ein Knoten und zwei Personen sind durch eine Kante verbunden, wenn sie mit einander befreundet sind. Wir wollen nun zeigen, dass es zwei Knoten gibt, welche die selbe Anzahl an Kanten haben. Dazu bemerken wir, dass es nicht sein kann, dass eine Person mit allen befreundet ist und gleichzeitig eine Person mit keinem befreundet ist. Das heisst, der Grad jedes Knoten ist entweder in der Menge \( \{1,2, \ldots, n-1\} \) oder in der Menge \( \{0,1,2, \ldots, n-2\} . \) Jetzt wird dir sicherlich auffallen, dass beide Mengen nur \( n-1 \) Elemente haben, es muss also mindestens zwei Knoten geben, die den selben Grad (Kanten die zu dem Knoten führen) haben. Daraus folgt die Behauptung.