Problem 1679

Solution:

Nehme an, dies sei nicht der Fall. Dann gibt es für jedes Element $x \in X$ zwei Teilmengen $A_{i}$ und $A_{j}$, sodass $A_{i} \backslash\{x\}=A_{j} \backslash\{x\}$ (eventuell gibt es mehrere solche Paare, wir wählen ein beliebiges aus und halten es im Folgenden fest). Da $A_{i}$ und $A_{j}$ verschieden sind, folgt daraus, dass beide Mengen dieselben Elemente enthalten, ausser dass $x$ in genau einer der beiden Mengen liegt. Wir betrachten nun einen Graphen, dessen Ecken die Mengen $A_{k}$ sind. Für jedes $x \in X$ wählen wir wie oben beschrieben zwei Teilmengen, von denen die eine $x$ enthält und die andere nicht, die aber ansonsten dieselben Elemente enthalten, und verbinden sie mit einer Kante. Man überlegt sich leicht, dass keine zwei Teilmengen mit mehr als einer Kante verbunden sein können, da verschiedene Kanten zu verschiedenen Elementen $x \in X$ gehören. Da dieser Graph $n$ Ecken und $n$ Kanten hat, besitzt er einen Zyklus (dies folgt leicht mit vollständiger Induktion). OBdA sei dieser Zyklus $A_{1}, A_{2}, \ldots, A_{k}, A_{1}$ und die Kante zwischen $A_{1}$ und $A_{2}$ gehöre zu $x$. Einerseits enthält nun genau eine der Mengen $A_{1}$ und $A_{2}$ das Element $x$, da sie ja durch diese Kante verbunden sind. Andererseits sind sie aber auch durch den Kantenzug über $A_{3}, \ldots, A_{k}$ verbunden. Keine dieser Kanten gehört zu $x$, also ändert sich der Zustand von $x$ auf diesem Kantenzug nicht, und daher gehört $x$ entweder zu beiden oder zu keiner der Mengen $A_{1}, A_{2}$, Widerspruch.

Solution:

Wir verwenden Induktion nach $n$, die Behauptung ist klar für $n=2$. Sind die Mengen $A_{1} \backslash\left\{x_{n}\right\}, \ldots, A_{n} \backslash\left\{x_{n}\right\}$ alle verschieden, sind wir fertig. Wir nehmen im Folgenden an, dies sei nicht der Fall. Gilt $A_{i} \backslash\left\{x_{n}\right\}=A_{j} \backslash\left\{x_{n}\right\}$, dann unterscheiden sich $A_{i}$ und $A_{j}$ nur um das Element $x_{n}$. Daraus folgt, dass nicht drei oder mehr Mengen nach Entfernung von $x_{n}$ gleich werden können. Wir fassen nun die Teilmengen $A_{i}$ einzeln oder paarweise in Gruppen zusammen, sodass die Mengen in einer Gruppe nach dem Entfernen von $x_{n}$ gleich werden. Nummeriere die verschiedenen auftretenden Mengen $A_{i} \backslash\left\{x_{n}\right\}$ in irgend einer Reihenfolge $B_{1}, \ldots, B_{m}$ mit $m \leq n-1$. Die $B_{i}$ entsprechen genau den Gruppen der $A_{j}$. Nach Induktionsvoraussetzung gibt es ein $x_{k}$ mit $1 \leq k \leq n-1$, sodass $B_{1} \backslash\left\{x_{k}\right\}, \ldots, B_{m} \backslash\left\{x_{k}\right\}$ alle verschieden sind (ergänze die Liste $B_{1}, \ldots, B_{m}$ gegebenenfalls durch weitere Mengen $B_{m+1}, \ldots, B_{n-1}$, falls $m<n-1$, sodass die $B_{i}$ alle verschieden sind). Die Mengen $A_{1} \backslash\left\{x_{k}\right\}, \ldots, A_{n} \backslash\left\{x_{k}\right\}$ sind nun paarweise verschieden: liegen $A_{i}$ und $A_{j}$ in verschiedenen Gruppen, dann sind nach Konstruktion ja sogar die Mengen $A_{i} \backslash\left\{x_{k}, x_{n}\right\}$ und $A_{j} \backslash\left\{x_{k}, x_{n}\right\}$ verschieden, liegen sie in derselben Gruppe, dann unterscheiden sich $A_{i} \backslash\left\{x_{k}\right\}$ und $A_{j} \backslash\left\{x_{k}\right\}$ um das Element $x_{n}$, sind also auch verschieden. Dies beendet den Beweis.