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):
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ą?
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.
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.
pokażcie kod brutala, pliz
W Excelu na IF-ach się da.
Mnie wychodzi po obliczeniach dla 2 kaczek 4.905405405405405 = 363 / 74 ?
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 🙂
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…
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.