Autor |
Beitrag |
Sandra
| Veröffentlicht am Sonntag, den 16. April, 2000 - 21:06: |
|
Rafft ihr´s? Zeige: Sei n größergleich 1 eine nat. Zahl. Dann besitzt die Menge {1,...,n} hat genau so viele Teilmengen mit einer ungeraden Anzahl von Elementen wie Teilmengen mit einer geraden Anzahl von Elementen. |
Armin Heise (Armin)
| Veröffentlicht am Sonntag, den 16. April, 2000 - 21:52: |
|
Hallo Sandra, Lösung mit vollständiger Induktion über n n= 1: Teilmengen sind : die leere Menge und {1}, d.h. eine Menge mit einem Element und eine Menge mit 0 Elementen, d.h. genausoviele Teilmengen mit einer geraden Anzahl von Elementen wie mit einer ungeraden Zahl von Elementen Sei Mn={1,...,n} Induktionsschritt : Zeige aus der Gültigkeit der Aussage für n folgt die Gültigkeit für n+1 Sei Mn+1={1,...,n+1} Zeige also: Mn+1 hat genausoviele Teilmengen mit einer geraden Anzahl wie mit einer ungeraden Anzahl von Elementen. Nach Induktionsvoraussetzung ist die Anzahl aller Mengen, die n+1 nicht enthalten und eine gerade Anzahl von Elementen haben = Anzahl aller Mengen, die n+1 nicht enthalten und eine ungerade Anzahl von Elementen besitzen, denn dies sind Teilmengen von Mn Jede Teilmenge von Mn+1, die n+1 enthält und eine gerade Anzahl von Elementen enthält, entsteht aus einer Teilmenge von Mn, die eine ungerade Anzahl von Elementen enthält, indem man n+1 hinzufügt. Genauso entsteht jede Teilmenge von Mn+1, die n+1 enthält und eine ungerade Anzahl von Elementen enthält aus einer Teilmenge von Mn, die eine gerade Anzahl von Elementen enthält, indem man n+1 hinzufügt.(*) Da es aber genausoviele Teilmengen von Mn mit einer geraden Zahl von Elementen wie mit einer ungeraden Zahl von Elementen gibt ( Induktionsvoraussetzung ) gibt es also auch genausoviele Teilmengen von Mn+1 mit gerader Anzahl von Elementen wie mit ungerader Anzahl von Elementen, die n+1 enthalten ( wegen (*)) Sowohl von Teillmengen von Mn+1, die n+1 enthalten, als auch von solchen, die n+1 nicht enthalten, gibt es genausoviele mit gerader und ungerader Zahl von Elementen, d.h. Mn+1 hat auch insgesamt genauso viele Teilmengen mit gerader Zahl wie mit ungerader Zahl von Elementen und dies mußte gezeigt werden. Es gibt also genausoviele Teilmengen von Mn+1 mit gerader und ungerader |
|