Zagadka: pogubione kaczuszki

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 3×3.

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ą?

Zapisz się
Powiadom o
guest
8 komentarzy
Inline Feedbacks
View all comments
Cichy
2020/02/11 17:18

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.

Butter
Butter
Reply to  xpil
2020/02/12 20:26

pokażcie kod brutala, pliz

Krzysiek
Krzysiek
2020/02/12 10:11

Mnie wychodzi po obliczeniach dla 2 kaczek 4.905405405405405 = 363 / 74 ?

Krzysiek
Krzysiek
Reply to  xpil
2020/02/12 13:18

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…

8
0
Would love your thoughts, please comment.x
()
x