| 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 |
|
