Größte Anzahl verschiedener Mengen

25.04.2024, 09:43	Nicht_Daniel	Auf diesen Beitrag antworten »
Größte Anzahl verschiedener Mengen Meine Frage: Was ist die größte Anzahl verschiedener Mengen, die man aus drei Mengen mit Hilfe der Mengenoperationen Vereinigung, Durchschnitt und Differenz bilden kann? Begründen Sie Ihre Antwort. Meine Ideen: Der Weg, die ganzen Kombinationen Bruteforce-mäßig aufzuschreiben scheint mir nicht der richtige, aber ich finde keinen Ansatz, wie ich das etwas allgemeiner gestalten kann...
25.04.2024, 10:18	HAL 9000	Auf diesen Beitrag antworten »
Es sind 128, z.B. erreichbar mit den Ausgangsmengen $\begin{eqnarray} A = \{0,2,4,6\} \end{eqnarray}$ , $\begin{eqnarray} B = \{0,1,4,5\} \end{eqnarray}$ und $\begin{eqnarray} C = \{0,1,2,3\} \end{eqnarray}$ . Allgemein sind bei geschickt gewählten $\begin{eqnarray} n \end{eqnarray}$ Mengen insgesamt maximal $\begin{eqnarray} 2^{2^n-1} \end{eqnarray}$ Mengen möglich.
25.04.2024, 10:34	Nicht_Daniel	Auf diesen Beitrag antworten »
Wie könnte ich das denn bei n Mengen beweisen?
25.04.2024, 10:47	HAL 9000	Auf diesen Beitrag antworten »
Mit $\begin{eqnarray} \Omega := A_1\cup \ldots \cup A_n \end{eqnarray}$ kann man zunächst alle $\begin{eqnarray} 2^n \end{eqnarray}$ Durchschnitte $\begin{eqnarray} B_1\cap \ldots \cap B_n \end{eqnarray}$ mit $\begin{eqnarray} B_k\in \left\{ A_k, A_k^c\right\} \end{eqnarray}$ für $\begin{eqnarray} k=1,\ldots,n \end{eqnarray}$ betrachten, dabei ist $\begin{eqnarray} A_k^c=\Omega\setminus A_k \end{eqnarray}$ gemeint. Diese $\begin{eqnarray} 2^n \end{eqnarray}$ Mengen sind paarweise disjunkt laut Konstruktion, und sind mit der einen Ausnahme $\begin{eqnarray} A_1^c\cap \ldots A_n^c = \emptyset \end{eqnarray}$ auch nichtleer, sofern man $\begin{eqnarray} A_1,\ldots,A_n \end{eqnarray}$ passend wählt. D.h., wir haben $\begin{eqnarray} 2^n-1 \end{eqnarray}$ nichtleere und paarweise disjunkte Elementarmengen, aus denen man wiederum per Vereinigungen insgesamt $\begin{eqnarray} 2^{2^n-1} \end{eqnarray}$ Mengen bilden kann. Eine mögliche "passende" Wahl: $\begin{eqnarray} A_k \end{eqnarray}$ enthält diejenigen Zahlen aus $\begin{eqnarray} \left\{ 0,1,\ldots,2^n-1 \right\} \end{eqnarray}$ , deren $\begin{eqnarray} k \end{eqnarray}$ -te Ziffer in der Binärdarstellung eine 0 ist. Dann sind die o.g. Durchschnitte dann jeweils die Einermengen $\begin{eqnarray} \{m\} \end{eqnarray}$ für $\begin{eqnarray} m=0,1,\ldots,2^n-2 \end{eqnarray}$ . Ok, damit ist konstruktiv nachgewiesen, dass Anzahl $\begin{eqnarray} 2^{2^n-1} \end{eqnarray}$ möglich ist. Jetzt kannst du dir noch überlegen, warum das das Maximum ist, d.h., warum nicht mehr drin ist.
25.04.2024, 11:55	Finn_	Auf diesen Beitrag antworten »
Ein wenig anschaulicher: Das Gefüge dreier hinreichend vielfältig gewählter Mengen zerfällt seinem Venn-Diagramm entsprechend in sieben disjunkte Bereiche. Gelingt es, jeden dieser Bereiche zu extrahieren, lassen sich daraufhin aus diesen via Vereinigung alle 127 Zusammensetzungen bilden. Zuzüglich der unschwer konstruierten leeren Menge sind das 128 unterschiedliche Mengen.
25.04.2024, 14:04	HAL 9000	Auf diesen Beitrag antworten »
Also für "anschaulicher" hätte ich erwartet, dass man wenigstens ein schönes Bildchen von den Venn-Diagramm sieht, als z.B. so eins zu den von mir oben genannten drei Mengen: [attach]57737[/attach]
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »