Eine Katze, einen Fisch, einen Hund und Ihr Mittagessen über einen Fluss bringen

Du versuchst, eine Katze, einen Fisch, einen Hund und dein Mittagessen über einen Fluss zu bringen, aber da ist ein Troll im Weg. Der Troll sagt: „Ich werde dir erlauben, den Fluss zu überqueren, aber nur, wenn du dieses Spiel mit mir spielst. Ich habe hier einen Würfel, der eine Katze, einen Fisch, einen Hund und dein Mittagessen zeigt. Ich werde diesen Würfel werfen , und dann musst du diesen Gegenstand über den Fluss bringen, egal auf welcher Seite. Sobald du das getan hast, würfele ich erneut. Wenn du alles auf die andere Seite bringen kannst, lasse ich dich gehen.“

Du merkst schnell, dass das keine gute Idee ist: Wenn du die Katze und den Fisch alleine auf einer Seite lässt, frisst die Katze den Fisch, und wenn du den Hund und das Mittagessen alleine auf einer Seite lässt, frisst der Hund dein Mittagessen. (Wenn die Katze, der Fisch und etwas anderes allein auf einer Seite liegen, wird nichts gegessen. Ebenso wird nichts gegessen, wenn der Hund, Ihr Mittagessen und etwas anderes allein auf einer Seite liegen.) Sie sagen dies zu der Troll, der sagt: „Gut. Wenn es unbedingt sein muss, würfele ich neu, um sicherzustellen, dass keine Ihrer wertvollen Frachten zu Schaden kommt.“

Angenommen, Sie machen eine Bewegung, wenn Sie etwas von einer Seite des Flusses auf die andere bringen. (Wenn der Troll seinen Würfel erneut würfelt, zählt dies nicht als Zug.) Finden Sie die erwartete Anzahl an Zügen, die Sie machen müssen, bevor alles auf der anderen Seite des Flusses ist.

Ich weiß ehrlich gesagt nicht, wo ich mit diesem Problem anfangen soll, und eine Lösung wäre sehr dankbar.

Ich verstehe es nicht ... warum würdest du jemals den Troll bitten, zu würfeln? Und warum nicht gleich alles rüberbringen?
Hier fällt mir ein Markov Chain-Ansatz auf. Erinnern Sie sich an die Übergangsmatrix T und Erwartungswertvektor E wir haben
( ICH − T ) E = 1
Wo ICH ist die Identitätsmatrix und 1 ein Spaltenvektor von ist 1 S. Weitere Informationen finden Sie hier

Antworten (1)

Wir können dies auf eine Markov-Kette abbilden { 0 , 1 , 2 , 3 , 4 } , wobei die Staaten die Anzahl der Gegenstände darstellen, die über den Fluss gebracht wurden. Die Übergangswahrscheinlichkeiten sind: 0 Und 4 immer Übergang zu 1 Und 3 , bzw; 1 Und 3 Übergang zu 0 Und 4 bzw. mit Wahrscheinlichkeit 1 3 und zu 2 mit Wahrscheinlichkeit 2 3 (da die vierte Option einen Wiederholungswurf verursacht) und 2 Übergänge zu 1 oder 3 mit gleicher Wahrscheinlichkeit 1 2 .

Es braucht E 0 = 1 bewegen, um von zu bekommen 0 Zu 1 .

Dann dauert es E 1 bewegt sich von 1 Zu 2 , mit

E 1 = 1 + 1 3 ( E 0 + E 1 ) ,

mit Lösung E 1 = 2 .

Dann dauert es E 2 bewegt sich von 2 Zu 3 , mit

E 2 = 1 + 1 2 ( E 1 + E 2 ) ,

mit Lösung E 2 = 4 .

Und dann dauert es E 3 bewegt sich von 3 Zu 4 , mit

E 3 = 1 + 2 3 ( E 2 + E 3 ) ,

mit Lösung E 3 = 11 .

Insgesamt wird die Operation also voraussichtlich dauern 1 + 2 + 4 + 11 = 18 bewegt.

Eine Katze, einen Fisch, einen Hund und Ihr Mittagessen über einen Fluss bringen
AntwortenHierDatenschutz-Bestimmungen1y, 0v