Ich war heute in meiner Lieblingspizzeria bei Alfredo und ich werde jetzt mal versuchen dir zu erklären, wieso mich seine Speisekarte an deine Aufgabe erinnert.
Alle seine Pizzen werden zunächst mit Tomaten und Käse belegt, das ist nichts besonderes. Dann hat Alfredo in seiner Küche eine Zutatenliste, aus der er gewisse Extrabeläge auswählen kann, um sie auf seine Pizzen zu legen. Je nach Auswahl erfindet er klangvolle Namen für seine Kreationen und schreibt die in seine Speisekarte für die Gäste.
Hier ist ein Ausschnitt aus seiner Speisekarte :
Pizza Margerita : mit Tomaten und Käse und sonst nichts
Pizza Funghi : mit Tomaten, Käse und Pilzen
Pizza Salami : mit Tomaten, Käse und Salami
Pizza PrimaDonna : mit Tomaten, Käse und Pilzen und Schinken
Pizza DonAlfredo : mit Tomaten, Käse und Salami und Schinken und Gurke
...
(das und sonst nichts habe ich eingefügt)
Der Zusammenhang mit deiner Aufgabe ist nun folgender :
Die Zutatenliste entspricht der Menge M, die komplette Speisekarte entspricht der Potenzmenge P(M) (was "komplett" bedeuten soll erkläre ich gleich). Jede Pizza auf der Speisekarte entspricht einer bestimmten Auswahl an Extrabelägen, d.h. einer Teilmenge von M. Wenn man alle möglichen Teilmengen von M betrachtet, erhält man die "Menge aller Teilmengen", das ist die Potenzmenge von M. Dem entsprechen alle möglichen Kombinationen von Extrabelägen, also alle möglichen Pizzen, eben die in diesem Sinne komplette Speisekarte.
Die Anzahl möglicher Extrabeläge (also wie viele Zutaten Alfredo zur Verfügung stehen) ist die Anzahl der Elemente von M (man nennt das auch die "Mächtigkeit" von M) und dafür wird |M| geschrieben.
Die Aufgabe besteht nun darin, zu untersuchen, wie viele Pizzen auf einer kompletten Speisekarte stehen, wenn Alfredo 5 (oder 7 oder 0 oder allgemein |M|) Zutaten zur Auswahl hat, d.h. gesucht ist die Mächtigkeit der Potenzmenge, also |P(M)|.
Machen wir ein paar Beispiele :
Wenn Alfredo gar keinen Extrabelag mehr hat (d.h. M = ∅ , |M| = 0), so kann er doch immerhin noch Pizza Margerita anbieten (allerdings auch keine andere), die komplette Speisekarte hat einen Eintrag, |P(M)| = 1. Mathematiker schreiben dafür P(∅) = {∅ }
Wenn Alfredo Artischocken hat (M = {a}), stehen auf seiner Speisekarte zwei Pizzen, nämlich Pizza Margerita und Pizza Pompeji (die mit Artischocken) : P(M) = {Margerita, Pompeji} = { ∅ , {a} }
Wenn Alfredo zwei Zutaten hat, Artischocken und Bananen ( M = {a , b} ), dann kann er jetzt schon vier Pizzen anbieten, nämlich Margerita, Pompeji, Vesuvo (die mit Banane) und Cäsar (die mit Artischocken und Banane) P(M) = {Margerita, Pompeji, Vesuvo, Cäsar} = { ∅ , {a} , {b} , {a,b} }
So hatte also Alfredo seine Zutatenliste, seine Gäste hatten die Speisekarte, alle waren glücklich und zufrieden. Da tauchte eines Tages ein Fremder auf, der eine exotische Zutat mitbrachte, von der keiner je zuvor etwas gehört hatte : Eisbein. Er verlangete, dass Eisbein auf die Zutatenliste gesetzt wird. Dadurch wurde |Malt| → |Mneu| = |Malt| + 1 . Wie veränderte sich der Umfang der Speisekarte also |P(M)| ? Die alten Pizzen konnten natürlich bleiben, aber zusätzlich konnten diese außerdem auch noch mit Eisbein belegt werden, es gab also jetzt doppelt so viele Pizzen wie vorher : |P(Malt)| → |P(Mneu)| = 2*|P(Malt)| . Jede neue Zutat verdoppelt den Umfang der Speisekarte, wenn M ein Element mehr erhält, verdoppelt sich die Mächtigkeit seiner Potenzmenge.
Mächtigkeit von M
| 0
| 1
| 2
| 3
| 4
| 5
| ...
| n
|
Mächtigkeit von P(M)
| 1
| 2
| 4
| 8
| 16
| 32
| ...
| 2^n
|
Das ist im Prizip der Induktionsbeweis dafür, dass |P(M)| = 2|M| ist.
Zusatz für Zweitsemester : Eines Tages kam der Teufel in die Pizzeria und verlangte, dass auch Pizzen als Belag auf Pizzen zugelassen sein sollten.
Pizza Diavolo sollte die Pizza Diavolo als Belag enthalten ...
Da wandte sich Alfredo an seinen Freund Bertrand um Rat. Bertrand schlug ihm vor, doch zunächst mal nur solche Pizzen anzubieten, die sich selbst nicht als Belag enthalten, solche Pizzen seien doch harmlos . Als Belohnung für seinen Ratschlag sagte Bertrand : "Dafür machst du mir jetzt bitte eine "Pizza Ultima", das ist die Pizza, die alle harmlosen Pizzen als Belag enthält." Alfredo hat Bertrand nie wieder seinen Freund genannt.