Zuerst einmal muss ich mich entschuldigen: Die Lösung des Dezemberrätsels, die ich für Ende 2015 angekündigt hatte, ließ lange auf sich warten. Mir kamen irgendwie die Weihnachtsferien dazwischen, und eine Menge Arbeit, und die übliche Prokrastination… Und dann hatte ich auch das Gefühl, dass es eigentlich nichts mehr aufzulösen gäbe, da eine hartnäckige Bande von Rätslern am Ende gemeinsam ohnehin schon alles gesagt hatte, was zu sagen war.

Trotzdem, hier also jetzt die “offizielle” Auflösung:

Anna kann gegen einen klugen Bernd ihre Gewinnwahrscheinlichkeit tatsächlich über 50% heben, allerdings nur geringfügig darüber. Dazu müssen wir zunächst klären, was ein “kluger Bernd” eigentlich sein soll. Hinter dieser Formulierung steht die Annahme, Bernd sei gewissermaßen hyperrational – er antizipiert die von Anna gewählte Strategie und reagiert optimal (für ihn gewinnmaximierend) darauf. Annas Ziel ist es also, ihre Gewinnchance durch geschickte Strategiewahl zu erhöhen, gegeben dass Bernd optimal darauf reagiert. Hier sind wir übrigens schon mitten in der Spieltheorie, es handelt sich nämlich technisch ausgedrückt um ein endliches 2-Personen-Konstantsummenspiel, das mit John von Neumanns (1928) Minimax-Theorem lösbar ist.

Bevor wir uns geeignete Strategien für Anna – und für Bernd – überlegen, müssen wir definieren, was überhaupt eine Strategie ist. Als “reine Strategie” bezeichnen wir einen “Verhaltensplan”, also einen vorab festgelegten und deterministischen Plan, der beschreibt, welches Zahlenpaar man wählt (für Bernd) bzw. ob man tauscht oder nicht, wenn man eine bestimmte Zahl sieht (für Anna). Für Bernd ist eine reine Strategie also einfach ein Paar (X,Y) mit X < Y von Zahlen zwischen 1 und 1000, er hat demnach 1000 x 999 / 2 = 499500 reine Strategien. Das klingt zwar nach einer ganzen Menge, ist aber nichts im Vergleich zur Anzahl von Annas möglichen reinen Strategien. Im Grunde kann Anna nämlich eine von 1000 Zahlen sehen, und für jeden dieser 1000 Fälle muss sie sich überlegen, ob sie den entsprechenden Zettel behält oder tauscht. Das sind insgesamt 2^1000 mögliche Strategien, also

1071508607186267320948425049060001810561404811705533607443750388370351051 12493612249319837881569585812759467291755314682518714528569231404359845775 7469857480393456777482423098542107460506237114187795418215304647498358194 1267398767559165543946077062914571196477686542167660429831652624386837205 668069376, was doch deutlich mehr ist.

Allerdings kann keine einzige dieser Strategien Annas Gewinnchance gegen den klugen Bernd erhöhen. Denn für jede dieser reinen Strategien kann Bernd seine beiden Zahlen so wählen, dass Annas Strategie ihr lediglich eine 50%ige Gewinnwahrscheinlichkeit beschert. Wenn Annas Strategie z.B. lautet: “Tausche bei 12, 134 und allen Zahlen größer als 788, ansonsten behalte”, dann kann Bernd z.B. mit der Strategie (401, 645) kontern (oder mit unzähligen anderen). Anna wird dann jedenfalls behalten, und es bleibt bei ihrer 50% Gewinnchance. Ähnliches gilt für jede andere von Annas reinen Strategien.

Glücklicherweise hat Anna aber noch die Möglichkeit, ihre reinen Strategien zu “mischen”. Unter einer “gemischten Strategie” versteht man eine Wahrscheinlichkeitsverteilung auf den reinen Strategien. Anna hat also nicht nur ihre reinen Strategien zur Auswahl, sondern auch unendlich viele gemischte Strategien. Eine solche gemischte Strategie könnte z.B. lauten “Mit Wahrscheinlichkeit 1/3 tausche ich bei 3, 4 und 5, mit Wahrscheinlichkeit 2/3 tausche ich bei 498, 532 und allem von 933 bis 951.” Der Clou dabei ist: Wenn Anna eine gemischte Strategie spielt, dann wird ihr tatsächliches Verhalten zufällig und kann dadurch von Bernd nicht antizipiert werden. (Auch hyperrationale Spieler sind keine Hellseher.)

Anna kann jetzt durch die Wahl einer gemischten Strategie ihre Gewinnchance tatsächlich über 50% heben. Das geht z.B. durch jene Strategie, die wir die Z-Strategie nennen wollen. Sie lautet: “Ich wähle zufällig (gleichverteilt) eine Zahl Z zwischen 1 und 999. Wenn die Zahl auf meinem Zettel kleiner oder gleich Z ist, dann tausche ich, ansonsten behalte ich.” Egal welches Zahlenpaar (X,Y) Bernd nun wählt, gibt es immer eine strikt positive Wahrscheinlichkeit, dass Annas Z in den Bereich X <= Z < Y fällt. Wenn das passiert, dann tauscht Anna, falls sie X zieht, behält aber, falls sie Y zieht, d.h. sie gewinnt dann auf jeden Fall. Wenn Annas Z nicht in diesen Bereich fällt, dann tauscht sie entweder auf jeden Fall oder behält auf jeden Fall, und wahrt damit ihre 50% Chance. Insgesamt hat sie also eine Gewinnwahrscheinlichkeit von mehr als 50%.

1 / 2 / Auf einer Seite lesen

Kommentare (16)

  1. #1 Lercherl
    13. Januar 2016

    Jauchzet, frohlocket! Der Gewinn freut mich wirklich sehr!

    Ich habe mich nach meinen beiden Kommentaren ganz am Anfang nicht mehr blicken lassen, das ist richtig. Ich hatte relativ bald den Eindruck, dass kaum mehr signifikant neue Erkenntnisse dazukamen, und habe dann aus Zeitgründen die Diskussion nicht mehr im Detail verfolgt. Ich hatte zu meiner Lösung auch nicht mehr viel dazuzusagen.

    Wie bin ich zu meiner Lösung gekommen? Mir war relativ bald klar, dass die Randfälle Bernd einen Nachteil bescheren. Für ein analoges Problem mit kleineren Intervallen statt 1 bis 1000 kann man das durch Abzählen relativ leicht ausrechnen:

    Intervall (1,2): Anna gewinnt immer.
    Intervall (1,2,3): Anna gewinnt in 75% der Fälle
    usw.

    und am anderen Ende:

    Intervall (-unendlich, unendlich): hier ist leicht zu sehen, dass Anna und Bernd exakt gleiche Chancen haben, egal wie sie spielen.

    Daraus ergibt sich, dass Bernd danach trachten muss, den Anteil der Randfälle möglichst gering zu halten, was sich durch die zufällige Wahl von Paaren mit Differenz 1 und das leicht konterintuitive Beharren auf Akzeptieren von Zufallspaaren (1,2) und (999,1000) realisieren lässt.

  2. #2 Karl-Heinz
    13. Januar 2016

    @Ulrich Berger
    Danke für die Auflösung und ausführliche Erläuterung
    Lg Karl-Heinz

  3. #3 Lercherl
    13. Januar 2016

    Nachtrag:

    Statt dem beidseitig unendlichen Intervall ist ein Problem mit zyklischen Randbedingungen (also z.B über den Restklassen modulo 1000: per definitionem 999 < 1000 und 1000 < 1) vielleicht zur Illustration besser geeignet (gleichverteilte Zufallszahlen auf einem unendlichen Intervall sind nicht wirklich definiert). Hier fallen die Randpaare weg und damit Bernds Nachteil.

    • #4 Ulrich Berger
      14. Januar 2016

      Das wäre aber schwierig zu spielen, weil dann 1 < 1000 < 1 wäre... Außerdem stimmt dieser "Grenzübergang" nicht. Auch bei unendlich vielen Zahlen zur Auswahl gilt: Solange Anna eine Verteilung spielt, die nirgendwo verschwindet, ist ihre Gewinnchance größer als 50%.

  4. #5 Dr. Webbaer
    14. Januar 2016

    Liest sich gut, schön zusammengefasst, danke.
    Ein sehr nettes Problem!

    @ Lercherl :
    Das hier war sehr “orthogonal” vorgetragen und der sofort gekommene Einwand konnte nicht durch den Hinweis entkräftet werden, dass dann ‘neue Randpaare’ sozusagen zwingend entstehen würden.
    Zudem mangelt es an Erklärung, warum Bernd gleichverteilt alle Konnektoren spielen sollte, und an Überlegung zu Annas Strategie.

    Ansonsten ist Ihr Kommentatorenfreund ebenfalls Intervalle der Größe 2 betrachtend und iterierend auf die Lösung gekommen, N kann nicht geschlagen werden, korrekt,
    MFG
    Dr. W (der natürlich nichts gegen die offizielle Lösung hat, abär immer noch ein wenig daran nagt, ob Bernd nicht (aus praktischen Gründen) die Konnektoren (501,502) bis (998,999) spielen sollte, auch um anderen Gewinnstrategien Annas (“bei 501 und größer stehen bleiben, ansonsten wechseln”) vorzubeugen)

  5. #6 Karl-Heinz
    14. Januar 2016

    @Lercherl

    Danke für deine Erklärung.
    Habe schon ein bisschen gerätselt, wie Du die richtige Lösung so einfach aus den Ärmel geschüttelt hast 😉

    Lg Karl-Heinz

  6. #7 Dr. Webbaer
    14. Januar 2016

    Sr, Karl-Heinz, was Kommentatorenfreund ‘Lercherl’ zu ergänzen wusste, war unzureichend.
    Vielleicht meldet sich der Laureat ja noch,
    MFG
    Dr. W

  7. #8 Dr. Webbaer
    14. Januar 2016

    @ Herr Berger :

    Auch bei unendlich vielen Zahlen zur Auswahl gilt: Solange Anna eine Verteilung spielt, die nirgendwo verschwindet, ist ihre Gewinnchance größer als 50%.

    Die Erwartung Annas ginge dann gegen 0,5 – wäre nicht anders als per Grenzwert mit 0,5 festzustellen.

    BTW, was bedeutet ‘verschwindet’?`

    MFG
    Dr. W

    • #9 Ulrich Berger
      14. Januar 2016

      “Ginge dann gegen 0,5” deutet den Grenzwert einer unendlichen Folge an. Aber was sollte diese sein? Bernd kann schließlich im gestellten Problem nur eine Verteilung wählen, nicht eine unendliche Folge von Verteilungen.

      “Verschwindet” bedeutet in diesem Kontext “ist null”.

  8. #10 Lercherl
    14. Januar 2016

    @Ulrich Berger

    OK, das mit den zyklischen Randbedingungen muss ich mir noch durch einmal den Kopf gehen lassen. Den angesprochenen “Grenzwert” können wir exakt folgendermaßen definieren:

    Sei b(n) die maximale Gewinnwahrscheinlichkeit von Bernd bei einem Spiel mit Auswahl von 1 bis n. Dann ist lim b(n) = 0,5 für n -> unendlich.

    @Webbaer

    Was ich noch nicht explizit dazugesagt habe: Jede deterministische Strategie Bernds kann von Anna geschlagen werden, deshalb auch die möglichst “zufällige” Strategie von Bernd.

    • #11 Ulrich Berger
      15. Januar 2016

      “lim b(n) = 0,5 für n -> unendlich” ist zwar richtig, aber nicht wirklich hilfreich, wenn man sich konkret für b(unendlich) interessiert, wie es im originalen Zwei-Zettel-Spiel der Fall ist. (Dort sind außerdem beliebige reelle statt nur ganze Zahlen zugelassen.)

  9. #12 Dr. Webbaer
    15. Januar 2016

    @ Lercherl :

    Das ist unzureichend, dieser Einwand valid und diese Ergänzung wiederum unzureichend.

    Diese Ergänzung – ‘Jede deterministische Strategie Bernds kann von Anna geschlagen werden, deshalb auch die möglichst “zufällige” Strategie von Bernd.’ – blieb hier unverstanden, also, was sie genau ergänzen soll. – Warum gilt es deterministische Strategien Bernds zu betrachten?

    Sans ehrlich, mir ham da ma was geschrieben, was dem (korrekten) EV der Beteiligten entspricht, aber i.p. Erklärung und Lösungsweg spekulativ blieb.

    MFG
    Dr. W

  10. #13 Ulrich Berger
    15. Januar 2016

    @ Lercherl, @ Webbaer:

    Das Problem an Lercherls ursprünglicher Erklärung ist, dass Annas Strategie nicht explizit angegeben wurde. Die Formulierung “wenn weder das erste noch das letzte Paar dabei sind, kann Anna durch Wechseln ihre Chancen nicht erhöhen” ist zwar mit der Z-Strategie kompatibel, aber z.B. auch mit “Bei 1 wechseln, bei 1000 behalten und bei allen anderen Zahlen zufällig entscheiden”.

    Auf diese letztere Strategie könnte Bernd aber tatsächlich erfolgreich kontern, indem er die Paare (1,2) und (999,1000) einfach weglässt. (Deshalb mein Einwand.)

    Die Entgegnung, dass dann (2,3) und (998,999) als neue Randpaare entstehen würden, ist wiederum recht unpräzise. Ich habe sie aber wohlwollend so interpretiert, dass die eigentlich gemeinte Strategie Annas tatsächlich die Z-Strategie war. Man könnte das aber auch weniger wohlwollend interpretieren, wie es der Webbaer offenbar tut…

  11. #14 Dr. Webbaer
    18. Januar 2016

    Webbaer sowieso nicht der wohlwollende Typ sein, jedenfalls nicht kommentarisch.
    Vielen Dank für Ihre Reaktion, Herr Berger, war wirklich ein sehr hübsches Rätsel,
    MFG + weiterhin viel Erfolg!
    Dr. W

  12. #15 Joker
    19. Januar 2016

    Danke.

    Frei nach Whitehead: All unser abendliches Rätseln ist als ‘Fußnote zu Lercherl’ zu verstehen.

  13. #16 Karl-Heinz
    20. Januar 2016

    Kommentar von Joker gefällt Karl-Heinz 🙂 🙂

    Frei nach Whitehead: All unser abendliches Rätseln ist als ‘Fußnote zu Lercherl’ zu verstehen.