Menge - Bekannte im Hörsaal

16.06.2020, 12:11

anoynmmx

Menge - Bekannte im Hörsaal

Meine Frage:
Zeige: In der Klasse sitzen mindestens 2 Personen, die gleich viele Bekannte unter den im Klassenzimmer Anwesenden haben. Es werde vorausgesetzt, dass "bekannt" symmetrisch ist, d.h. wenn Lucas Bekannter von Thomas ist, dann ist auch Thomas Bekannter von Lucas. Lucas ist aber nicht Bekannter von sich selbst. Betrachten Sie die Menge Mk der Personen, die genau k Bekannte haben. Zeige: Höchstens eine der Mengen M0 und Mn-1 ist nicht leer.

Meine Ideen:
ich steh bei dieser Aufgabe auf dem Schlauch

16.06.2020, 12:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von anoynmmx
Zeige: Höchstens eine der Mengen $\begin{eqnarray*} M_0 \end{eqnarray*}$ und $\begin{eqnarray*} M_{n-1} \end{eqnarray*}$ ist nicht leer.

Fangen wir doch damit an: Angenommen, $\begin{eqnarray*} M_{n-1}\neq \emptyset \end{eqnarray*}$ . Dann gibt es eine Person, die mit ALLEN anderen bekannt ist. Der Symmetrie des Bekanntseins wegen gibt es dann aber keine Person, die mit keinem anderen bekannt ist, d.h., es ist $\begin{eqnarray*} M_0= \emptyset \end{eqnarray*}$ , fertig mit dieser Behauptung.

Wie hilft das bei der Gesamtaufgabe? Es ist $\begin{eqnarray*} \sum_{k=0}^{n-1} \left|M_k\right| = n \end{eqnarray*}$ (denn jede der $\begin{eqnarray*} n \end{eqnarray*}$ Personen findet in genau einer Menge $\begin{eqnarray*} M_k \end{eqnarray*}$ seinen Platz) und wir wissen, dass mindestens eine der beiden Anzahlen $\begin{eqnarray*} \left|M_0\right| \end{eqnarray*}$ sowie $\begin{eqnarray*} \left|M_{n-1}\right| \end{eqnarray*}$ gleich Null ist. Entfernen wir die aus der Summe, dann verbleibt eine Summe von $\begin{eqnarray*} n-1 \end{eqnarray*}$ nichtnegativen ganzen Zahlen mit Summenwert $\begin{eqnarray*} n \end{eqnarray*}$ , und wir müssen für

Zitat:

Original von anoynmmx
Zeige: In der Klasse sitzen mindestens 2 Personen, die gleich viele Bekannte unter den im Klassenzimmer Anwesenden haben.

nachweisen, dass mindestens einer dieser Summanden $\begin{eqnarray*} \geq 2 \end{eqnarray*}$ ist...

Neue Frage »

Antworten »

Menge - Bekannte im Hörsaal

Verwandte Themen