Anzahl aller ungeraden teilmengen von x gleich 2n 1

Zitat:Original von Arthur Dent
"Kenn ich nicht, weiß ich nicht, hatt ich nicht, will ich nicht ... aber gebt mir einen vernünftigen (!) Ansatz."

Was du verlangst, ist was für Zauberkünstler. Ich sehe hier jede Menge vernünftige Ansätze, aber du lässt keinen an dich heran.

Hm, also einen vernünftigen Ansatz kenn ich noch, der zwar die Idee des induktiven Beweises verwendet, aber kein induktiver Beweis ist...

Um sie zu verdeutlichen, nehmen wir an, der Geschäftsführer einer Diskothek möchte bei einem Event, das er veranstaltet hat, feststellen, ob mehr Männer oder Frauen anwesend sind... Er bittet dazu den DJ eine Platte aufzulegen, bei der sich erfahrungsgemäß garantiert alle potenziellen Paare auf die Tanzfläche begeben... Zu seiner Verwunderung stellt er fest, dass keine Besucher übriggeblieben sind, die nicht auf der Tanzfläche sind, woraus er den messerscharfen Schluss zieht, dass es gleich viele männliche wie weibliche Besucher geben muss...

Als er nach Hause kommt, sieht er seinen Sohn über eben der Aufgabe brüten, die in diesem Thread gestellt wurde... Blitzschnell schießt es ihm durch den Kopf, dass dieses Prinzip der Paarbildung vielleicht auch hier anwendbar ist, wobei in jedem Paar jeweils eine Menge eine gerade und die andere Menge eine ungerade Anzahl von Elementen hat... Nun gibt es auf Mengen aber bereits eine ganz natürliche (ungeordnete) Paarbildung nämlich, wobeidie Komplementärmenge zu A bezeichnet,...

Er probiert das einmal mit den Teilmengen der Menge M={1,2,3} aus und präsentiert dann seinem Sohn stolz die Lösung mit den Paaren

mit der Bemerkung, dass das im allgemeinen Fall ganz genauso geht... Aber der holt ihn schnell wieder in die Realität zurück, indem er darauf hinweist, dass dies nur in 50% der Fälle so funktioniert, nämlich genau dann wenn die Menge M eine ungerade Anzahl von Elementen hatte, wie eben in diesem Beispiel ...

Ok, das stimmt offensichtlich, aber kann man diese Beweisidee nicht vielleicht doch auch für Mengen M mit einer geraden Anzahl von Elementen in irgendeiner Form "retten"? Der Geschäftsführer und sein Sohn setzen sich jedenfalls hin und überlegen angestrengt, ob man dies nicht z.B. irgendwie auf den schon bekannten Fall, wo M eine ungerade Anzahl von Elementen hat, zurückspielen kann...

Tja, und vielleicht ist diese Frage ja auch dem TE zugänglich, sozusagen als allerletzter Versuch?

Ich hab dir doch oben hingeschrieben, wie für eine 3-elementige Mengedie Teilmengen aussehen und wie man da die "Paare" bildet:

Insbesondere ist da die leere Menge auch dabei, warum in aller Welt willst du die ausschließen??! Die hat doch 0 Elemente und 0 ist eine gerade Zahl, da durch 2 teilbar, d.h., die leere Menge ist genauer eine Teilmenge mit einer geraden Anzahl von Elementen... (edit: wie Arthur oben schon gesagt hat)

Wie schaut das jetzt bei den Teilmengen vonaus? Hier funktioniert zwar die obige Paarbildung nicht mehr, denn in jedem Paarhaben nun beide Mengen entweder eine gerade oder eine ungerade Anzahl von Elementen, aber es funktioniert eine andere Paarbildung, wo die "Partner" verschiedene "Paritäten" haben, nämlich

...

Du solltest dir mal alle diese Paare wirklich hinschreiben und dir dann überlegen, inwieweit dir das hilft, dass die Behauptung für Teilmengen vonja schon bewiesen wurde...
Zitat:Original von TheBoss
Wenn man das Ganze für k=5 macht, steht in jeder Zeile auch wieder eine gerade und eine ungerade Zahl, nur, dass es eben wieder die doppelte Menge an Teilmengen ist, im Vergleich zu k=4!

Und das ist dortlaufend so, dass sich die Teilmengen immer verdoppeln... Aber inwieweit kann ich die erkannte Schlussfolgerung "sauber" führen? Bzw. was genau meinst du damit?

Das Problem ist, du weichst meinen Fragen immer wieder aus, hier z.B. auf den anderen Fall k=5, obwohl ich dich ja ausdrücklich gebeten hatte, den Beweis für k=4 zu führen... Ich werde dir das noch schnell vorführen, wie ich das gemeint hatte und dann die Diskussion hier damit abschließen, da wir irgendwie nicht vom Fleck kommen...

Schauen wir uns dazu nochmals untenstehende Liste aller Teilmengen von {1,2,3,4} an, von der wir zeigen, dass sie insgesamt gleich viele gerade wie ungerade Teilmengen enthält....

1. ({ },{4})
2. ({1},{1,4})
3. ({2},{2,4})
4. ({3},{3,4})
5. ({1,2},{1,2,4})
6. ({1,3},{1,3,4})
7. ({2,3},{2,3,4})
8. ({1,2,3},{1,2,3,4})

Wir wissen nun bereits, dass dies für die 1.Spalte (bestehend aus den ersten Komponenten aller Paare) zutrifft, da dies ja nur Teilmengen von {1,2,3}, für welche wir das ja schon gezeigt haben... Angenommen, dies wäre in der 2.Spalte (bestehend aus den zweiten Komponenten aller Paare) nicht so und es gäbe z.B. mehr ungerade Teilmangen als gerade... Für diese Paare wäre aber dann die erste Komponente gerade, d.h., es gäbe dann in der ersten Spalte mehr gerade als ungerade Teilmengen, Widerspruch... Es gibt somit auch in der 2.Spalte gleich viele gerade wie ungerade Teilmengen von {1,2,3,4}, somit gilt dies auch insgesamt für alle Teilmengen von {1,2,3,4}, die ja alle in diesen zwei Spalten aufgelistet sind...
Ja, Arthur hat es wunderbar auf den Punkt gebracht, genauer auf den Punkt b), wo auch ich die allergrößten Zweifel habe, dass du ihn wirklich verstanden hast...

Du sagst z.B., du würdest den Beweis gerne "allgemein" anschreiben und übersiehst dabei völlig, dass ich das oben zwar für M={1,2,3,4} alles aufgeschrieben habe, damit du dir das bessser vorstellen kannst, aber dass meine Argumentation tatächlich ganz allgemein war... Abgesehen von winzigen Änderungen, indem man M={1,2,3,4} allgemeiner durch die Menge M={1,2,...,n} für ein n>1 ersetzt und die Paarbildung

betrachtet, sowie auch wieder die Liste derPaare

läßt sich nämlich meine Argumentation oben fast Wort für Wort übernehmen... Ich habe eben oben in dem Sinne "sauber" argumentiert, als mein Argument mutatis mutandis auch für den allgemeinen Fall gilt...

Übrigens: "Formeln" im üblichen Sinne gibt es bei diesem Beweis keine, wenn du sowas suchst, so wärst du mit der allerersten Beweisidee, welche von tmo vorgeschlagen wurde, nämlich dem Beweis der Formel

wobei hiergerade die Anzahl der k-elementigen Teilmengen von M={1,2,...,n} ist, besser beraten...
Man könnte allenfalls noch erwähnen, dass man für einen induktiven Beweis nach obigem Muster einen Induktionsanfang braucht, das ist hier der Fall n=1, den man direkt nachrechnen muss...Ich bin aber oben davon ausgegangen, dass die Behauptung für ungerades n auf dem von mir skizzierten Wege schon allgemein bewiesen war...

Ja, viele Wege führen nach Rom, wie es so schön heißt... Als kleine Ergänzung noch eine Beweisvariante, dir mir persönlich fast am besten gefällt, da sie leicht zu merken ist...

Sei M={1,2,...,n} für ein n>0 und a ein beliebiges, aber im folgenden festes Element von M. Es ist dann die Abbildung

eine selbstinverse Permutation von... Anschaulich gesprochen wird durch Anwendung von f auf X der Menge X das Element a hinzugefügt, wenn es vorher nicht in X enthalten war, sonst wird es aus X entfernt... Inbesondere sieht man sofort, dass X und f(X) auf jeden Fall eine verschiedene Parität haben, was ihre Mächtigkeiten betrifft... Ist dann U die Menge der "ungeraden" Teilmengen und G die Menge der "geraden" Teilmengen von M, so müssen wir also dann zeigen, dass |G|=|U| ist...

Betrachten wir dazu die beiden Einschränkungen f|U: U -> G und f|G: G ->U von f, so sind diese als Folge der Bijektivität von f immer noch injektiv, d.h., es giltund, woraus tatsächlichfolgt...
Vielleicht sollte ich hier die Geschichte vom dem Geschäftsführer der Disco und seinem Sohn noch zu Ende erzählen...Es war inzwischen spät nachts geworden und die beiden brüteten noch immer über der Aufgabe...Insbesondere wurmte es dem Vater, dass seine Idee mit der Paarbildung, welche bei Mengen mit einer ungeraden Anzahl von Elementen so wunderbar funktioniert hatte, auf Mengen mit einer geraden Anzahl von Elementen nicht anwendbar sein sollte...

Er betrachtete nochmals das Beispiel M={1,2,3,4}, wie schon so oft vorher, und hatte plötzlich die Idee, es genau mit der Paarbildung

({ },{4})
({1},{1,4})
({2},{2,4})
({3},{3,4})
({1,2},{1,2,4})
({1,3},{1,3,4})
({2,3},{2,3,4})
({1,2,3},{1,2,3,4})

zu versuchen, auf welche auch wir oben gekommen waren, nämlich jede Teilmenge von {1,2,3} wird gepaart mit der der um 4 vergrößerten Teilmenge, was also dann insgesamt 8 Paare ergibt...

Nun hatte der gute Mann noch nie in seinem Leben von vollständiger Induktion gehört, daher kam er gar nicht erst auf die Idee, es damit zu versuchen... Zum Glück brauchte er sie aber gar nicht: Da jedes Paar genau eine gerade und eine ungerade Teilmenge enthielt, genau wie im Beispiel M={1,2,3} mit der Paarung (Teilmenge,Komplementärmenge), und andererseits auch alle Teilmengen von {1,2,3,4} in obiger Auflistung genau einmal vorkommen, war auch so der Beweis erbracht, dass es genausoviele gerade wie ungerade Teilmengen von {1,2,3,4} geben musste...

Stolz zeigte er diese Lösung seinem Sohn mit der Bemerkung, dass der allgemeine Fall einer n-elementigen Menge M nun wirklich genauso gehen sollte...Dieser schaute sich das nur kurz an, um dann freudig zuzustimmen, das war offensichtlich die Lösung...

Am nächsten Tag wurde in der Übungsstunde jemand zu diesem Beispiel aufgerufen, der offenbar keine Ahnung von einem allgemeinen Beweis hatte und glaubte, die Aufgabe so lösen zu können, indem er die Richtigkeit der Behauptung für einige kleine Werte von n nachwies... Da die Zeit schon fortgeschritten war, sprang der Professor dann irgendwann ein und führte den Beweis mit vollständiger Induktion korrekt zu Ende...Da zeigte unser Sohn auf, und führte im Detail aus, dass diesselbe Idee auch ohne vollständige Induktion funktioniert, genau so wie sein Vater dies in der Nacht zuvor gemacht hatte...Er hatte seinen Professor noch nie so perplex gesehen...