Größte Anzahl verschiedener Mengen

Neue Frage »

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...
HAL 9000 Auf diesen Beitrag antworten »

Es sind 128, z.B. erreichbar mit den Ausgangsmengen , und .

Allgemein sind bei geschickt gewählten Mengen insgesamt maximal Mengen möglich.
Nicht_Daniel Auf diesen Beitrag antworten »

Wie könnte ich das denn bei n Mengen beweisen?
HAL 9000 Auf diesen Beitrag antworten »

Mit kann man zunächst alle Durchschnitte

mit für

betrachten, dabei ist gemeint. Diese Mengen sind paarweise disjunkt laut Konstruktion, und sind mit der einen Ausnahme auch nichtleer, sofern man passend wählt.

D.h., wir haben nichtleere und paarweise disjunkte Elementarmengen, aus denen man wiederum per Vereinigungen insgesamt Mengen bilden kann.


Eine mögliche "passende" Wahl: enthält diejenigen Zahlen aus , deren -te Ziffer in der Binärdarstellung eine 0 ist. Dann sind die o.g. Durchschnitte dann jeweils die Einermengen für .


Ok, damit ist konstruktiv nachgewiesen, dass Anzahl möglich ist. Jetzt kannst du dir noch überlegen, warum das das Maximum ist, d.h., warum nicht mehr drin ist.
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.
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]
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »