Rätsel

[Sokrates]

Haha, ich habs.

 

Lösung: b.) ist richtig: 1/3 Marzipankartoffel pro Spiel.

Die optimale Strategie: Beide spielen mit Wahrscheinlichkeit 2/3 Papier. Der Weihnachtsmann mit Wahrscheinlichkeit 1/3 Schere, der Osterhase mit Wahrscheinlichkeit 1/3 Stein.

 

Begründung folgt irgendwann. (Ist etwas mühsam. Ich brauche den "Gradienten" dazu, also Differentialrechnung mehrerer Variablen. Das scheint mir für so ein Rätsel doch etwas aufwendig).

[Sokrates]

Und hier der Beweis ohne Differentialrechnung (der trivial ist, wenn man die Lösung kennt. Ich liebe Probleme, die als Probleme extrem nichttrivial und als Lösung geradezu trivial sind - wenn man sie hat).

 

Der Weihnachtsmann kann erzwingen, dass er jedesmal im Schnitt 1/3 Kartoffel gewinnt: Indem er nämlich mit Wahrscheinlichkeit 2/3 Papier spielt und mit Wahrscheinlichkeit 1/3 Schere. Angenommen, der Osterhase würde immer Papier spielen, dann wäre es in 2/3 der Fälle unentschieden, in 1/3 der Fälle würde der Weihnachtsmann mit Schere gewinnen.

Würde der Osterhase dagegen immer Stein spielen, würde er in 1/3 der Fälle gewinnen und in 2/3 der Fälle verlieren. Für beliebige Mischstrategien des Osterhasen gilt dasselbe: Der Weihnachtsmann gewinnt immer 1/3 im Durchschnitt.

 

Wenn umgekehrt der Osterhase immer 2/3 Papier und 1/3 Stein spielt, dann kann der Weihnachtsmann machen was er will, er kommt nicht auf mehr als 1/3 Gewinn: Wenn er immer Schere spielt, verliert der Osterhase in 2/3 der Fälle und gewinnt in 1/3, wenn der Weihnachtsmann immer Papier spielt, gewinnt er in 1/3 der Fälle und macht in 2/3 der Fälle ein Unentschieden. Auch hier gilt für Mischfälle das gleiche. Wenn also jeder beim anderen erzwingen kann, dass der Erwartungswert 1/3 herauskommt, ist es optimal, wenn beide diese Strategie spielen.

 

Das Spiel zwischen Osterhase und Weihnachtsmann ist fair, wenn der Weihnachtsmann dem Osterhasen für je drei Spiele eine Teilnahmegebühr von einer Kartoffel bezahlt.

[Beutelschneider]

@Sokrates: Mit anderen Worten, Du hast das Nash-Gleichgewicht berechnet.

[Sokrates]

@Sokrates: Mit anderen Worten, Du hast das Nash-Gleichgewicht berechnet.

Danke für den Hinweis. So tief bin ich nie in die Spieltheorie eingedrungen. Nash kannte ich aus "a beautiful mind", habe mich aber nie damit beschäftigt, wofür er seinen Nobelpreis bekommen hat.

 

Jetzt habe ich kurz bei Wikipedia nachgeschaut. Das Nash-Gleichgewicht ist das, was ich wohl am Anrfang suchte, als ich das Problem noch als "extrem nichttrivial" bezeichnete. (Kein Wunder, wenn man dafür den Nobelpreis kriegen würde). Am Anfang dachte ich sogar noch, es gäbe gar keine Lösung, bei der beide Spieler an ihrer Strategie festhalten können. Da hätte ein Existenzsatz für Nash-Gleichgewichte womöglich ein Kriterium geliefert. Hast Du den Wikipedia Algorithmus mal für das Beispiel durchgerechnet?

bearbeitet 8. Dezember 2004 von Sokrates

[maxinquaye]

Und hier der Beweis ohne Differentialrechnung (der trivial ist, wenn man die Lösung kennt. Ich liebe Probleme, die als Probleme extrem nichttrivial und als Lösung geradezu trivial sind - wenn man sie hat).

 

Der Weihnachtsmann kann erzwingen, dass er jedesmal im Schnitt 1/3 Kartoffel gewinnt: Indem er nämlich mit Wahrscheinlichkeit 2/3 Papier spielt und mit Wahrscheinlichkeit 1/3 Schere. Angenommen, der Osterhase würde immer Papier spielen, dann wäre es in 2/3 der Fälle unentschieden, in 1/3 der Fälle würde der Weihnachtsmann mit Schere gewinnen.

Würde der Osterhase dagegen immer Stein spielen, würde er in 1/3 der Fälle gewinnen und in 2/3 der Fälle verlieren. Für beliebige Mischstrategien des Osterhasen gilt dasselbe: Der Weihnachtsmann gewinnt immer 1/3 im Durchschnitt.

 

Wenn umgekehrt der Osterhase immer 2/3 Papier und 1/3 Stein spielt, dann kann der Weihnachtsmann machen was er will, er kommt nicht auf mehr als 1/3 Gewinn: Wenn er immer Schere spielt, verliert der Osterhase in 2/3 der Fälle und gewinnt in 1/3, wenn der Weihnachtsmann immer Papier spielt, gewinnt er in 1/3 der Fälle und macht in 2/3 der Fälle ein Unentschieden. Auch hier gilt für Mischfälle das gleiche. Wenn also jeder beim anderen erzwingen kann, dass der Erwartungswert 1/3 herauskommt, ist es optimal, wenn beide diese Strategie spielen.

 

Das Spiel zwischen Osterhase und Weihnachtsmann ist fair, wenn der Weihnachtsmann dem Osterhasen für je drei Spiele eine Teilnahmegebühr von einer Kartoffel bezahlt.

Und hier der Beweis ohne Differentialrechnung (der trivial ist, wenn man die Lösung kennt. Ich liebe Probleme, die als Probleme extrem nichttrivial und als Lösung geradezu trivial sind - wenn man sie hat).

 

Ganz genau. Das ist dann ein gutes Rätsel.

 

Okay, ich möchte einmal anmerkan dass dies ein wirklich ein echter Beweis ist (was beim ersten Lesen vielleicht nicht sofort klar wird):

G der Erwartungswert des Weihnachtsmannes, kann weder unter noch über 1/3 sein, weil es dafür jeweils Gegen-Strategien gibt (das ist eine allgemeine Methode der Spieltheorie, zumindest vermute ich das mal, denn diese Methode muss auch bei anderen Rätseln dieser Art funktionieren).

 

Gut, wie kommt man auf 1/3 ?

 

Ich habe dazu mal während des Essens den Stift geschwungen. Man geht erstmal davon aus dass es globale Wahrscheinlichkeiten geben muss mit denen die Parteien Stein, Schere usw. spielen, also dass sie nicht abhängig von Ergebnis der letzten Spiele ihre Entscheidung treffen. *)

Diese Wahrscheinlichkeiten seien nun Ws,Wt,Wp und H.. (analog). (t für Stein.)

 

Dann malt man sich ein Bäimchen auf und rechnet für jeden Fall die Wahrscheinlichkeit*Gewinn auf. Dann erhält man eine Formel Gw (Gewinnerwartung vom Weihnachtsmann) (Ws,Wt,..)=... . wobei man natürlich Hs=1+Ht usw. benutzen kann. Dann rechnet den Gradienten aus. Viola. (Ohne Gewehr und Waffenschein)

 

Also : nichtrivial, auch weil es ungewohnt ist (Spieletheorie).

 

Ich verbleibe in aufrichtiger Bewunderung, Soki..

 

 

*) Dieser Punkt ist aus meiner Sicht notwendig, andernfalls sind die Wi und Hj nicht sauber definiert. Die Begründung selbst erfolgt aber wieder mit dem Argument dass Spielen nach golbalen Wahrscheinlichkeiten nicht torpedierbar sind.

bearbeitet 8. Dezember 2004 von maxinquaye

[Sokrates]

Ich versuch mal die Gleichung:

 

Wir können voraussetzen, dass der Weihnachtsmann niemals Stein spielt, weil er nie gewinnen kann, sondern höchstens unentschieden oder verlieren kann. Setzen wir ferner voraus, dass beide eine feste Strategie spielen.

 

Sei x die Wahrscheinlichkeit, dass der Weihnachtsmann Papier spielt

Sei y die Wahrscheinlichkeit, dass der Osterhase Papier spielt.

 

Dann ist 1-x die Wahrscheinlichkeit, dass der Weihnachtsmann Schere spielt

Und 1-y die Wahrwscheinlichkeit, dass der Osterhase Stein spielt.

 

Betrachten wir den Gewinn aus Sicht des Weihnachtsmannes (=W; Osterhase = O):

 

+1 wenn (W: Papier) und (O: Stein),  Wahrscheinlichkeit:     x * (1-y)
+1 wenn (W: Schere) und (O: Papier), Wahrscheinlichkeit: (1-x) * y
-1 wenn (W: Schere) und (O: Stein),  Wahrscheinlichkeit: (1-x) * (1-y)

In allen anderen Fällen ist unentschieden.

 

Dann gilt für den Erwartungswert:

 

E(x,y) = x*(1-y) + ((1-x)*y + (-1)*(1-x)*(1-y) = x - xy + y - xy - 1 + x + y -xy
       = 2x + 2y - 3xy -1

 

Hinweis für Nichtmathematiker: Wenn man E(x,y) aufzeichnet, erhält man eine Art gewellte Landschaft über einer Ebene. Man kann jetzt den "Gradienten" ausrechnen, das ist ein Vektor, der die partiellen Ableitungen von E(x,y) nach x und nach y als Komponenten enthält. Dieser Gradient ist ein Vektor in Richtung des steilsten Abfalls unserer aufgezeichneten Gebirgslandschaft, also die Richtung, in die der Skifahrer fahren würde, wenn er besonders waghalsig ist.

                (2-3y)
grad(E(x,y)) = (    )     
               (2-3x)

 

(Zur Erläuterung: der obere Wert ist nach x abgeleitet, und y als Konstane aufgefasst, "partielle Ableitung nach x", der untere Wert ist nach y abgeleitet, und x als Konstante aufgefasst)

 

Nun ist ja der Gradient die Richtung der steilsten Steigung. Wenn es so etwas nicht gibt, sind wir wohl auf einem Gipfel, dem Tal oder einem Sattelpunkt. Also suchen wir in unserem Beispiel die Stelle, wo sich der Gewinn für Weihnachtsman und Osterhase nicht mehr stark ändert, so ein Sattelpunkt. Den erhalten wir dort, wo der Gradient der Nullvektor ist.

 

Also: grad (E(x,y)) = (0;0)

oder:

(1) 2 - 3x = 0
(2) 2 - 3y = 0

 

Daraus folgt: x = 2/3 und y = 2/3, und das sind die gesuchten Wahrscheinlichkeiten, um Papier zu spielen.

 

Eingesetzt in der Erwartungswert gibt das:

 

E(x,y)=2*2/3+2*2/3+3*4/9-1 = 4/3-1 = 1/3

bearbeitet 8. Dezember 2004 von Sokrates

[Beutelschneider]

Hi Sokrates,

ich habe noch gar nicht bei Wikipedia nachgeschaut, sondern dass sind noch die Wissenreste aus der Zeit nach meinem Studium, als ich mal versucht habe über sowas eine Diss zu schreiben. Ist aber nichts geworden, also bitte nichts ernst nehmen was ich von mir gebe!

[maxinquaye]

Die Funktion E(x,y).

 

 

An dieser Stelle danke ich pmm herzlich für den Link !

bearbeitet 8. Dezember 2004 von maxinquaye

[Sokrates]

Hi Maxi,

 

sieht E(x,y) so aus? Der Sattelpunkt ist gut zu erkennen. Allerdings kann die Skala nicht stimmen, bzw. muss umnormiert werden. x und y muss zwischen 0 und 1 liegen.

[Stefan]

Ich mag Rätsel die eine Pointe haben.

Ich auch. Gibt es noch welche?

[Einsteinchen]

Welches einzige englische Wort hat vorne und hinten ein "und" ?

[Stefan]

Welches einzige englische Wort hat vorne und hinten ein "und" ?

Underground

[Einsteinchen]

Richtig. Das ging aber schnell.

[maxinquaye]

Ich habe die Funktion oben einfach in ein Prog eingegeben (daher sollte es eigentlich richtig sein). Die Werte für x,y müssen natürlich aus [0,1] sein, ich habe die Achsen nicht formatiert.

[maxinquaye]

Ich mag Rätsel die eine Pointe haben.

Ich auch. Gibt es noch welche?

Ja, sicher. Es ist ein wenig schade dass die Rätsel etwas mathematischer wurden, die waren auch sehr pointiert, man brauchte aber etwas math. Handwerkszeug. Haben Dir die letzten Rätsel gefallen ?

 

Ich habe ein einfaches :

 

Stell Dir einen Würfel vor. Nun möchte eine Ameise von einer Ecke in die andere die zwei Kanten weiter ist. Welches ist der kürzeste Weg ?

[Sokrates]

Ich habe auch ein nettes, eine VErallgemeinerung von einem Rätsel, das wir hier schon hatten:

 

Kürzlich war ich in den Bergen in einer Albhütte. Auf die Frage, wie ich am besten ins Tal käme, sagte mir der Wirt:

 

Gehe geradeaus. Du kommst an eine Weggabelung. Einer der Wege führt in eine tödliche Schlucht, der andere sicher ins Tal. Der Wegweiser ist nicht zu lesen, und ich weiss nicht mehr, ob Du den rechten oder den linken Weg gehen musst.

 

Aber bei der Gabelung sitzen immer drei Hirten, die wissen alle drei Bescheid. Aber Vorsicht: Einer von ihnen sagt immer die Wahrheit, einer lügt immer, und der dritte lügt manchmal und manchmal sagt er die Wahrheit. Und nochmal Vorsicht: Stelle möglichst wenige Fragen, und nie eine Frage an mehrere Hirten gleichzeitig, denn wenn die Burschen sauer werden, könnten sie Dich verprügeln.

 

Ich ging also zur Weggabelung und traf die Drei: Den Lügner, den Wahrheitssager, und den Unzuverlässigen.

 

Wieviele Fragen brauchte ich, und welche waren das?

bearbeitet 8. Dezember 2004 von Sokrates

[maxinquaye]

Das gleiche Bild aus einer anderen Perspektive.

bearbeitet 8. Dezember 2004 von maxinquaye

[Sokrates]

Das gleiche Bild aus einer anderen Perspektive.

Du musst mal schauen, wo Du bei Deiner Software die Skalenbeschriftung einstellen kannst. Ganz links muss Null stehen und ganz rechts 1 (Sonst kommen einige durcheinander.

[Wally]

@maxinquaye:

Meinst Du mit deiner Ameise einfach die Diagonale einer Würfelseite?

[maxinquaye]

Nein, der Weg läuft nicht über die Diagonale der Würfelseite, falls Du das meinst. Das wäre ja zuu einfach.

[maxinquaye]

Du hast eine Geraderobe mit 3 Schubladen. Eine Schublade enthält nur Socken, eine zweite enthält nur Unterhosen, und die dritte enthält eine Mischung von Socken und Unterhosen. Jede der Schubladen ist eindeutig beschriftet, aber jede der Beschriftungen ist falsch. Du darfst nun deine Augen schließen, eine Schublade öffnen und ein einziges Kleidungsstück entnehmen und dir dieses anschauen. Wie kannst du den Inhalt jeder der drei Schubladen ermitteln ?

[Rinf]

Nein, der Weg läuft nicht über die Diagonale der Würfelseite, falls Du das meinst. Das wäre ja zuu einfach.

Und Du bist Dir da ganz sicher mit den 2 Kanten?

Vielleicht doch eher 3?

[Rinf]

Du darfst nun deine Augen schließen, eine Schublade öffnen und ein einziges Kleidungsstück entnehmen und dir dieses anschauen. Wie kannst du den Inhalt jeder der drei Schubladen ermitteln ?

Ich ziehe ein Kleidungstück aus der Schublade "Socken und Unterhosen".

Ziehe ich eine Socke, muß es die reine Socken-Schublade sein.

Dann kann in der mit "Unterhosen" beschriftete Schublade nur noch beides sein, und für die mit "Socken" beschriftetete bleiben nur die Unterhosen.

 

Umgekehrt ist es natürlich umgekehrt ;-)

[maxinquaye]

Nein, der Weg läuft nicht über die Diagonale der Würfelseite, falls Du das meinst. Das wäre ja zuu einfach.

Und Du bist Dir da ganz sicher mit den 2 Kanten?

Vielleicht doch eher 3?

3, ja. Es ist drei Kanten weiter.

 

Die Sockenaufgabe ist rischtisch.

[Rinf]

3, ja. Es ist drei Kanten weiter.

OK - handelt es sich um einen Zuckerwürfel? ;-)