Das Problem lässt sich mit dem Schubfachprinzip (Pigeonhole Principle) lösen. Wir möchten zeigen, dass es auf einer Party mit mindestens zwei Personen $|V| \geq 2$ immer zwei verschiedene Gäste gibt, die gleich viele Freunde auf der Party haben.

Modellierung der Freundschaften

• $V$: Die Menge der Partygäste, wobei $|V| = n$.
• $E \subseteq V^2$: Die Menge der Freundschaftsbeziehungen. Jede Beziehung ist symmetrisch, also wenn $\{v, w\} \in E$, dann gilt $\{w, v\} \in E$.

Für jeden Gast $v \in V$ definieren wir den Grad $\deg(v)$, der die Anzahl der Freunde von $v$ angibt. Dieser Wert ist eine ganze Zahl zwischen 0 (wenn $v$ mit niemandem befreundet ist) und $n-1$ (wenn $v$ mit allen anderen Gästen befreundet ist).

Behauptung

Es gibt mindestens zwei Gäste $u, v \in V$, sodass $\deg(u) = \deg(v)$.

Beweis

1. Maximale Werte für den Grad:

   • Jeder Gast kann zwischen $0$ und $n-1$ Freunde haben. Das bedeutet, dass es $n$ mögliche Werte für $\deg(v)$ gibt, wenn keine Einschränkungen bestehen.

2. Einschränkung durch symmetrische Freundschaften:

   • Wenn ein Gast $v$ $0$ Freunde hat (isoliert ist), kann kein anderer Gast $n-1$ Freunde haben, da $v$ nicht mit diesem Gast befreundet ist. Das bedeutet, die möglichen Werte für $\deg(v)$ sind eingeschränkt auf $0, 1, 2, \ldots, n-2$ oder $1, 2, \ldots, n-1$.

3. Anwendung des Schubfachprinzips:

   • Es gibt $n$ Gäste, aber nur $n-1$ mögliche Werte für den Grad $\deg(v)$ (siehe Schritt 2). Das Schubfachprinzip besagt, dass mindestens zwei Gäste denselben Grad haben müssen, da $n > n-1$.

Schlussfolgerung

Es existieren stets zwei verschiedene Gäste $u, v \in V$, die gleich viele Freunde auf der Party haben. Damit ist Pias Erfolg, zwei Menschen mit derselben Anzahl an Freunden zu finden, garantiert.

---

Zusammenfassung: Das Problem wird durch das Schubfachprinzip gelöst. Da es $n$ Gäste, aber nur $n-1$ mögliche Freundschaftsgrade gibt, müssen mindestens zwei Gäste denselben Grad haben.

---

Haben Sie dazu noch Fragen oder möchten Sie eine detaillierte Erklärung zu einem bestimmten Teil? Hier sind fünf vertiefende Fragen:

1. Was genau besagt das Schubfachprinzip, und wie kann es auf andere Probleme angewendet werden?
2. Was passiert, wenn die Anzahl der Gäste stark ansteigt – wie könnte man das Problem effizienter modellieren?
3. Wie könnte man dieses Problem mit Graphen und deren Eigenschaften (z. B. vollständiger Graph) weiter analysieren?
4. Was würde sich ändern, wenn asymmetrische Freundschaften erlaubt wären?
5. Wie könnte man diese Lösung praktisch umsetzen, etwa durch einen Algorithmus?

Tipp: Das Schubfachprinzip ist ein universelles Werkzeug und kann in vielen Beweisführungen nützlich sein, wenn es um begrenzte Ressourcen oder Ver