Ich habe die Aufgabe so verstanden, dass ich eine Wurfkombination suche, wie z.B. Strategie S: 1.) werfe X_1 auf X_2, 2.) werfe X_3 auf X_4. Und dann ganz unabhängig von der Ausgangssituation sagen kann: (z.B.) Jetzt haben X_5 und X_6 den gleichen Typ. [....]
Ja, das sieht ganz vernünftig aus.
Ich grüble nun seit einigen Tagen über diese Aufgabe und muss sagen, dass ich immer noch nicht genau weiß, was zu tun ist. In der Aufgabenstellung heißt es:
ZitatWie viele Würfe mit Xmasium-Atomen muss Knecht Ruprecht im schlimmsten Fall mindestens ausführen, damit er dem Weihnachtsmann garantiert zwei Xmasium-Atome vom selben Typ schenken kann?
Welche "Fälle" sind hier gemeint? Ich habe die Aufgabe bislang so verstanden, dass Ruprecht weiß, welche Ausgangssituationen möglich sind (= "mögliche Fälle"), aber eine Strategie (= "Wurffolge") entwickeln muss, die ihm für jede beliebige Ausgangssituation garantiert, zwei gleiche Xmasium-Atome auswählen zu können. In diesem Sinne wäre eine Strategie eine Wurffolge und man könnte eigentlich "im schlimmsten Fall" aus der Aufgabenstellung herausstreichen. Diese Auffassung passt auch zur folgenden Erläuterung hier im Forum:
Ruprecht kennt den Ausgangszustand nicht, aber seine Strategie muß für jeden Augangszustand funktionieren.
Allerdings passt das nicht zur folgenden Aussage:
Erläuterung der Aufgabe:
- Am Anfang liegen sechs Atome im Kochtopf. Jedes dieser Atome besitzt entweder ein Higgs-Boson oder auch nicht. Das liefert uns 64 mögliche Ausgangssituationen A_1,A_2,...,A_64.
- Knecht Ruprecht hat eine Strategie S, mit der er zwei Atome gleichen Typs in den Geschenkkarton packen will.
- Für jede Ausgangssituation A_k wird die Strategie S eine gewisse Anzahl W_k an Würfen erfordern. Der Maximalaufwand dieser Strategie S ist das Maximum der 64 Zahlen W_1,...,W_64.
- Gesucht ist nun eine Strategie S, die den Maximalaufwand minimiert.
Hieraus entnehme ich, dass eine Strategie nicht eine Wurffolge ist, sondern eine Menge von Wurffolgen, aus denen man die für die jeweilige Ausgangssituation passende Wurffolge auswählt. Das macht aber keinen Sinn. Wenn ich in diesem Sinne eine Strategie entwickle, die für jede einzelne Ausgangssituation A_k eine Anzahl an Würfen W_k erfordert (also bei vollem Wissen über A_k), so ist die Strategie trivial zu finden. Wenn ich eine Strategie entwickle, die für alle A_k's gilt, so kann es nur eine Wurffolge in der Strategie geben und man landet im ersten Fall, wie oben. Sinnvoll fände ich diese Auffassung von "Strategie", wenn man für bestimmte Mengen von Ausgangssituationen eine geeignete Wurffolge finden will, z.B. die Menge aller Ausgangssituationen, in denen es vier Atome mit Higgs-Boson gibt und zwei ohne. Dann hätte man unvollständiges Wissen über die Ausgangssituation und verschiedene Wurffolgen würden durchaus Sinn machen. Dies ist aber offenbar laut Aufgabenstellung nicht gemeint. Was genau ist also hier eine "Strategie"?
Ich grüble nun seit einigen Tagen über diese Aufgabe und muss sagen, dass ich immer noch nicht genau weiß, was zu tun ist.
[...]
Was genau ist also hier eine "Strategie"?
Zu überlegen, was die Strategie ist, ist ja genau eure Aufgabe. Wir können dir da leider nicht weiterhelfen.
Hieraus entnehme ich, dass eine Strategie nicht eine Wurffolge ist, sondern eine Menge von Wurffolgen, aus denen man die für die jeweilige Ausgangssituation passende Wurffolge auswählt. Das macht aber keinen Sinn.
Wie du aber schon richtig bemerkst, macht das keinen Sinn, da weder Ruprecht noch wir die Ausgangsituation kennen.
Die folgenden Aussagen von WoegingerG stehen daher in keinem Widerspruch:
Ruprecht kennt den Ausgangszustand nicht, aber seine Strategie muß für jeden Augangszustand funktionieren.
Erläuterung der Aufgabe:
- Am Anfang liegen sechs Atome im Kochtopf. Jedes dieser Atome besitzt entweder ein Higgs-Boson oder auch nicht. Das liefert uns 64 mögliche Ausgangssituationen A_1,A_2,...,A_64.
- Knecht Ruprecht hat eine Strategie S, mit der er zwei Atome gleichen Typs in den Geschenkkarton packen will.
- Für jede Ausgangssituation A_k wird die Strategie S eine gewisse Anzahl W_k an Würfen erfordern. Der Maximalaufwand dieser Strategie S ist das Maximum der 64 Zahlen W_1,...,W_64.
- Gesucht ist nun eine Strategie S, die den Maximalaufwand minimiert.
Da die Bearbeitungsphase ja jetzt vorbei ist. Wie ist die folgende Erläuterung denn zu verstehen?
Erläuterung der Aufgabe: [...]
- Für jede Ausgangssituation A_k wird die Strategie S eine gewisse Anzahl W_k an Würfen erfordern. Der Maximalaufwand dieser Strategie S ist das Maximum der 64 Zahlen W_1,...,W_64.
Wie ist die folgende Erläuterung denn zu verstehen?
Es gibt 2^6 = 64 Startkonstellationen A_1, ..., A_64 für die Atome. Die Strategie, wenn es sie denn gäbe, müsste für jede Startkonstellationen einen Maximalwurfaufwand W_k für Konstellation A_k erzwingen können. Der größte dieser 64 Maximalwurfaufwände war in der Aufgabe gesucht. Aber leider ist ja nicht möglich . . .
Es gibt 2^6 = 64 Startkonstellationen A_1, ..., A_64 für die Atome. Die Strategie, wenn es sie denn gäbe, müsste für jede Startkonstellationen einen Maximalwurfaufwand W_k für Konstellation A_k erzwingen können. Der größte dieser 64 Maximalwurfaufwände war in der Aufgabe gesucht. Aber leider ist ja nicht möglich . . .
Ich bin nicht der Meinung, dass das so funktionieren würde, wenn es denn eine Strategie gäbe. Man kann die Startkonstellationen A_k nicht unabhängig betrachten und für jede einen Wurfaufwand W_k berechnen, von denen man das Maximum bildet. Selbst wenn es für jede Startkonstellation A_k eine Strategie mit Wurfaufwand W_k gibt, heißt das noch lange nicht, dass es eine Strategie gibt, die für eine unbekannte Startkonstellation funktioniert. Das zeigt ja diese Aufgabe gerade (siehe Lösungsdiskussionsthread). Und selbst wenn es eine "globale" Strategie für unbekannte Startkonstellationen gäbe, hieße das nicht, dass sie irgendetwas mit den "Teilstrategien" für irgendwelche konkreten echten Teilmengen von {A_1, ..., A_64} zu tun haben müsste (oder könnte).
Es ist ja nur eine Formalisierung der Aufgabenstellung. Man kann z.B. beliebige Startkonstellationen sortieren etc. Gemeint ist hier nur, dass der schlechtmöglichste Fall einer Startkonstellation betrachtet wird. Aber vermutlich war das gar nicht Deine Frage.
Hm, das ist der Punkt. Eine schlechtmöglichste Startkonstellation gibt es nicht bzw. ist völlig irrelevant für eine Strategie, die mit allen Startkonstellationen zurecht kommen muss, da eine Strategie für eine Startkonstellation nichts zu tun haben muss mit einer Strategie für alle. Insbesondere hat man mit dem Maximum aller W_ks nicht unbedingt den Aufwand der Strategie für unbekannte Startkonstellationen bestimmt.