| |
| Autor |
 Mengen |
|
Anonymous
Unregistrierter Benutzer
|  Themenstart: 2002-10-10
|
wie kann ich folgende aufgabe lösen:
sei M eine nichtleere endliche Menge. Zeige, daß M 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.
|
|
Fabi
Senior 
Dabei seit: 03.03.2002
Mitteilungen: 4586
 | Beitrag No.1, eingetragen 2002-10-10
|
Hi!
Sei M eine n-elementige Menge. Es gibt (n über k) Mengen mit k Elementen und ebensoviele mit n-k Elementen.
1. Fall: n ist ungerade
Dann betrachte alle Teilmengen mit k Elementen. Das sind genausoviele wie alle Teilmengen mit n-k Elementen. Wenn n ungerade ist, ist genau eine dieser beiden Zahlen ungerade, die andere gerade.
Sei A eine Menge der Mächtigkeit k.
DIe Menge B := {b ÎM | b Ï A} hat dann n-k Elemente und hat (wenn A eine ungerade Elementenzahl hatte) eine gerade Elementenzahl, andernfalls eine ungerade Elementenzahl.
Also kann man allen Mengen der Mächtigkeit k genau eine Menge der Mächtigkeit n-k zuordnen, und man hat einer ungeraden Menge eine gerade Menge zugeordnet.
Abbildungsvorschrift:
A -> B:= {b ÎM | b Ï A}
2. n gerade
Ich betrachte alle Teilmengen, die ein beliebiges Element p nicht enthalten. Das sind die Teilmengen der Menge M/{p}, und diese Menge hat die Mächtigkeit n-1, also eine ungerade Mächtigkeit. In dieser Menge gibt es genausoviele gerade wie ungerade Teilmengen.
Nun betrachte ich die restlichen Mengen: die, die p enthalten.
Das sind genau die Mengen, die man erhält, wenn man p zu allen Teilmengen, die p nicht enthalten, dazutut. Diese Mengen werden dadurch von ungeraden zu geraden bzw. von geraden zu ungeraden Mengen. Da es genausoviele ungerade wie gerade Mengen vor dem Hinzufügen von p gab, ändert sich dieser Sachverhalt jetzt nicht und auch für die Mengen, die p enthalten, gilt: Es gibt genausoviele gerade wie ungerade Mengen.
Jetzt braucht man noch eine Abbildungsvorschrift. Die ist hier schwieriger als im ersten Fall.
1. Fall: p Ï T
T -> C{c Î M/{p} | c Ï T}
2. Fall: p Î T
T -> T/{p} -> C{c Î M | c Ï T/{p}} -> C+p
Gruß
Fabi
|
 Profil
|
| Anonymous wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
