Bundeswettbewerb 2007, Teil 1, Beispiel 3: Lösung
Aus ÖMO Wiki
Angabe
Sei 
. Für jede nicht leere Teilmenge bilden wir das
Produkt ihrer Elemente. Wie groß ist die Summe über alle diese Produkte?
Erste Lösung
Wir paaren jede Teilmenge A von 
mit der Menge
.
Falls A nicht-leer ist, hebt sich in der gewünschten Summe das Produkt
für A mit dem Produkt für X(A) auf. Falls A leer ist, trägt X(A) genau
− 1 zur Summe bei. Die Summe ist daher -1.
Zweite Lösung
Wir beweisen mit Induktion über n, dass die gewünschte Summe gleich -1 ist.
Für n = 1 ist das trivial.
Im Induktionsschritt teilen wir die Teilmengen von Mn + 1 in drei Teile auf: Der erste Teil enthält alle Teilmengen von M(n). Der zweite Teil enthält die Menge {n + 1}. Der dritte Teil enthält alle restlichen Mengen (die von der Form {n + 1} vereinigt mit einer nicht-leerer Teilmenge von M(n) sind).
Zur gewünschten Summe trägt der erste Teil -1 bei (laut Induktionsannahme),
der zweite Teil n + 1, und der dritte Teil 
(wieder laut
Induktionsannahme). Das addiert sich zu -1 auf.
