Zagadka: pogubione kaczuszki

https://xpil.eu/gsf

Dziś zagadka drobiowa.

Mamy staw. Ale nie kolanowy tylko taki z wodą.

W stawie mamy dziewięć całkiem sporych kamieni, ułożonych dziwnym zbiegiem okoliczności w kwadrat 3x3.

Na środkowym kamieniu siedzą sobie dwie kaczuszki.

Siedzą sobie, siedzą...

Minęła minuta. Kaczuszkom znudziło się tak siedzieć, każda z nich wybrała więc losowy kierunek (góra / dół / lewo / prawo) i przepłynęła na sąsiedni kamień znajdujący się w wylosowanym kierunku. Robią to niezależnie jedna od drugiej.

Jeżeli obydwie trafiły na ten sam kamień, pozostają tam do końca świata i jeden dzień dłużej. Jeżeli trafiły na różne kamienie, po minucie znów losują sąsiedni kamień (każda swój) i nań przepływają.

I tak dalej.

Za każdym razem po upływie minuty każda z kaczuszek, niezależnie jedna od drugiej, wybiera sobie losowo sąsiedni kamień (wyłącznie wzdłuż albo w poprzek, nie na ukos!) i na niego przepływa. Prawdopodobieństwo wybrania każdego z sąsiednich kamieni wynosi 1/4 dla kamienia środkowego, 1/3 dla czterech bocznych i 1/2 dla każdego z czterech narożnych (bo ze środka są cztery kierunki, z boków - po trzy, a z narożników tylko po dwa):

Rysunek poglądowy. Kaczki w tej skali są wielkości niedużego drzewa. Coś jakby kaczkozaury na menhirach. Przypuszczam, że co minutę w stawie pojawia się niewielkie tsunami.

No i teraz pytanie: po ilu średnio minutach kaczuszki spotkają się? Zakładamy, że czas przepłynięcia z kamienia na kamień można pominąć.

Pytanie bonusowe: a co, jeżeli ze środkowego kamienia wystartują trzy kaczuszki zamiast dwóch? Po ilu wówczas minutach spodziewamy się, że wszystkie trzy się znów spotkają?

https://xpil.eu/gsf

8 komentarzy

  1. Brute force pokazał, że około pięciu, a dla trzech kaczek około osiemnastu – ale rozpisywać kombinacje odechciało mi się już przy trzecim kroku, więc jeśli nie znajdę jakiejś drogi na skróty, to lepszej odpowiedzi nie dam.

    1. Mi brute force pokazał 5 dla dwóch i 19 dla trzech, i to są w miarę precyzyjne wyniki. A jak to rozwiązać analitycznie pokażę w następnym wpisie.

    1. I to jest poprawna odpowiedź! Jeżeli jeszcze objaśnisz krok po kroku jak do tego doszedłeś, zdradzisz dobrze ponad połowę treści mojego kolejnego wpisu 🙂

      1. OK,
        ja doszedłem do wyniku tak:

        pierwsza rzecz zauważyć można, że mamy ograniczoną liczbę stanów w których nasze kaczki mogą się znajdować w danym momencie, niektóre układy są niemożliwe do osiągnięcia np (k – kaczka, x – pusty kamień):
        xkk
        xxx
        xxx

        Druga rzecz to taka, że niektóre układy są z naszego punku widzenia równoważne np:
        kxx
        xkx
        xxx

        oraz

        xxk
        xkx
        xxx
        Układy, które powstają przez obrót lub odbicie lustrzane są równoważne. Po wzięciu pod uwagę tych warunków mamy 5 możliwych układów kaczek:
        Układ 1:
        xkx
        kxx
        xxx

        Układ 2:
        xkx
        xxx
        xkx

        Układ 3:
        kxk
        xxx
        xxx

        Układ 4:
        kxx
        xkx
        xxx

        Układ 5:
        kxx
        xxx
        xxk

        Teraz tylko musimy wyznaczyć przejścia pomiędzy stanami (K – oznacza stan końcowy, w którym kaczki są na jednym kamieniu):
        1 -> K, K, 3, 3, 4, 4, 4, 4, 5
        2 -> K, 3, 3, 4, 4, 4, 4, 5, 5
        3 -> K, 1, 1, 2
        4 -> K, K, 1, 1, 1, 1, 2, 2
        5 -> 1, 1, 2, 2
        czyli np z układu 4 możemy przejść na 2 sposoby do stanu końcowego, na cztery sposoby do stanu nr 1 i na 2 sposoby do stanu nr 2.
        Zbierając to do kupy możemy sobie wypisać kilka równań
        E1 = 2/9 + 2/9*(1+E3) + 4/9*(1+E4) + 1/9*(1+E5)
        E2 = 1/9 + 2/9*(1+E3) + 4/9*(1+E4) + 2/9*(1+E5)
        E3 = 1/4 + 2/4*(1+E1) + 1/4*(1+E2)
        E4 = 2/8 + 4/8*(1+E1) + 2/4*(1+E2)
        E5 = 1/4*(1+E1) + 2/4*(1+E2)
        Można sobie uprościć te równania coby  nie mieć ułamków i sobie rozwiązać układ 5 równań z 5 niewiadomymi. Ja użyłem https://matrixcalc.org/pl/slu.html
        E1 = 184 / 37
        E2 = 210 / 37
        E3 = 363 / 74
        E4 = 363 / 74
        E5 = 234 / 37
        to są wartości oczekiwane w poszczególnych stanach. Teraz tylko musimy sobie policzyć jaka jest wartość oczekiwana w stanie początkowym. Z niego można dojść na 4 sposoby do stanu końcowego, na 8 sposobów do stanu nr 1 i na 4 sposoby do stanu nr 2:
        E = 4/16 + 8/16*(1+E1) + 4/16*(1+E2)
        Po podstawieniu E1 i E2 dostajemy wynik 363 / 74

        Pewnie jest jakiś prostszy sposób, ale ten też działa…

        1. Doskonale, solidna robota! Ja lada dzień pokażę jak się takie klamoty rozwiązuje uniwersalnie, ale początek rozważań mamy identyczny, czyli redukcja do pięciu możliwych układów oraz policzenie prawdopodobieństw przejść między nimi. Jestem pod wrażeniem.

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.