TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 101
Jump to navigation
Jump to search
Sei
eine nichtleere endliche Menge. Zeigen Sie, dass gleich viele Teilmengen mit gerader Elementanzahl wie solche mit ungerader Elementanzahl besitzt, indem Sie ein Verfahren angeben, das aus den Teilmengen der einen Art umkehrbar eindeutig die der anderen Art erzeugt.
Lösung gibts im Informatik Forum SS07!
Nur ohne Angabe des Links nicht auffindbar!
Lösungsvorschlag von M4rS[edit]
Die Lösungen im Informatik-forum schaun ja auf den ersten Blick relativ kompliziert aus, und nachdem im Buch das nächste Bsp (88) mehr od weniger "einfach" bewiesen ist, würde ichs mal so versuchen
Jede Menge hat
Elemente. Wir können uns eine Teilmenge als Kombination von Binärzahlen vorstellen.Z. B.
Teilmengen sind
Die Anzahl können wir immer mit darstellen, je nachdem, ob wir das Element in die Teilmenge aufnehmen. Da man bei jedem Element auf diese Weise wählen kann ob man es in die Gruppe aufnimmt od nicht haben wir mMn bewiesen das es gleich viele gerade wie ungerade Teilmengen gibt und auch ein Verfahren gezeigt, mit dem man umkehrbar eindeutig Teilmengen erzeugen kann.Lösungsvorschlag von Ryus[edit]
Kurz gefasst: Man wählt irgendein Element x aus der Menge aus und wendet folgende Funktion auf die Teilmenge an:
Wobei
die symmetrische Differenz bezeichnet. Ist , wird es der Teilmenge A hinzugefügt. Ist hingegen , wird es aus A entfernt. So kann man von jeder ungeraden Menge auf eine gerade schließen und umgekehrt. Somit ist eine Bijektion gefunden und gezeigt, dass die Anzahl an ungeraden Mengen gleich der Anzahl an geraden Mengen ist.--Ryus (Diskussion) 19:52, 25. Mär. 2015 (CET)