Wędrówki gąsienicy

[mol_ksiazkowy]

Gąsienica idzie po krawędziach sześcianu a zaczyna z punktu (wierzchołka )\(\displaystyle{ A}\) ; oraz \(\displaystyle{ B}\) i \(\displaystyle{ C}\) są posmarowane klejem, gdzie \(\displaystyle{ AB}\) jest przekątną ściany, \(\displaystyle{ AC}\) jest przekątną główną. Będąc w dowolnym wierzchołku z jednakowym prawdopodobieństwem idzie po jednej z krawędzi (może się też cofnąć), Jakie jest prawdopodobieństwo tego, że
i) przyklei się w \(\displaystyle{ B}\)
ii) przyklei się w \(\displaystyle{ C}\)
i) wróci do \(\displaystyle{ A}\)

[kerajs]

Prócz startu z A, gdzie gąsienica ma do wyboru trzy krawędzie, w każdym nienazwanym wierzchołu gąsienica wybiera jedną z dwóch dróg. Ponadto, układy z pierwszym wyborem drogi do wierzchołka ściany z A i B są symetryczne.
i)
\(\displaystyle{ P= \frac{2}{3} \left[ \left( \frac{1}{2} \right) +\left( \frac{1}{2} \right)^5\right] +
\frac{1}{3} \left[ \left( \frac{1}{2} \right)^3 +\left( \frac{1}{2} \right)^3\right]= \frac{7}{16} }\)
ii)
\(\displaystyle{ P= \frac{2}{3} \left[ \left( \frac{1}{2} \right)^2 +\left( \frac{1}{2} \right)^4\right] +
\frac{1}{3} \left[ \left( \frac{1}{2} \right)^2 +\left( \frac{1}{2} \right)^2\right]= \frac{6}{16} }\)
iii)
\(\displaystyle{ P= \frac{2}{3} \left[ \left( \frac{1}{2} \right)^3 +\left( \frac{1}{2} \right)^5\right] +
\frac{1}{3} \left[ \left( \frac{1}{2} \right)^3 +\left( \frac{1}{2} \right)^3\right]= \frac{3}{16} }\)

[a4karo]

@kerajs
W każdym wierzchołku do wyboru sa TRZY drogi, bo gąsienica może się cofać

Może sobie też w nieskończoność łazić po ścianach, które nie zawiera wierzchołków B i C

[kerajs]

@kerajs
W każdym wierzchołku do wyboru sa TRZY drogi, bo gąsienica może się cofać

A dałbym sobie włosy obciąć, że tam było napisane, iż nie może się cofać.
Dziękuję za zauważenie tak fundamentalnego błędu.

[kerajs]

Nie mam pomysłu na szybkie rozwiązanie, więc poniżej część kiepskiego:

Zakładam, że gąsienica cały czas porusza się z taką samą prędkością i żyje wiecznie.

I)
Nienazwane w treści zadania wierzchołki etykietuję cyframi 0,1,2,3,4 jak na poniższej grafice:

Jest dokładnie sześć istotnie różnych tras którymi gąsienica dociera do wierzchołka B. Literą \(\displaystyle{ e}\) nazwę liczbę etapów (krawędzi) które przebywa gąsienica, a przez literą \(\displaystyle{ s}\) ilość wariantów przejścia trasy e-etapowej. Przykładowo, trasę B1 można pokonać w:
\(\displaystyle{ e=2}\) etapach tylko jednym sposobem: A0B
\(\displaystyle{ e=4}\) etapach tylko jednym sposobem: A010B
\(\displaystyle{ e=6}\) etapach na dwa sposoby: A01010B, A01010B , itd

Trasa B1:
\(\displaystyle{ \begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
e & 2 & 4 & 6 & 8 & 10 & 12 & 14 & ... & ... \\ \hline
s & 1 & 1 & 2 & 5 & 14 & 41 & 122 & ... & ... \\ \hline
s & 1 & \frac{3^0+1}{2} & \frac{3^1+1}{2} & \frac{3^2+1}{2} & \frac{3^3+1}{2} & \frac{3^4+1}{2} & \frac{3^5+1}{2}& ... & ... \\ \hline
\end{array}
\\
P(B1)= \left( \frac{1}{3} \right) ^2+\left( \frac{1}{3} \right) ^4\frac{3^0+1}{2} +\left( \frac{1}{3} \right) ^6 \frac{3^1+1}{2} +\left( \frac{1}{3} \right) ^8 \frac{3^2+1}{2} +\left( \frac{1}{3} \right) ^{10} \frac{3^3+1}{2}+...= \frac{55}{432}
}\)


Trasa B2:
\(\displaystyle{ \begin{array}{|c|c|c|c|c|c|c|c|}
\hline
e & 6 & 8 & 10 & 12 & 14 & ... & ... \\ \hline
s & 1 & 4 & 13 & 40 & 121 & ... & ... \\ \hline
s & \frac{3^1-1}{2} & \frac{3^2-1}{2} & \frac{3^3-1}{2} & \frac{3^4-1}{2} & \frac{3^5-1}{2}& ... & ... \\ \hline
\end{array}
\\
P(B2)= \left( \frac{1}{3} \right) ^6 \frac{3^1+1}{2} +\left( \frac{1}{3} \right) ^8 \frac{3^2+1}{2} +\left( \frac{1}{3} \right) ^{10} \frac{3^3+1}{2}+...= \frac{1}{432}
}\)

Trasa B3:
\(\displaystyle{ \begin{array}{|c|c|c|c|c|c|c|c|}
\hline
e & 4 & 6 & 8 & 10 & 12 & ... & ... \\ \hline
s & 1 & 3 & 9 & 27 & 81 & ... & ... \\ \hline
s & 1 & 3^1 & 3^2 & 3^3 &3^4& ... & ... \\ \hline
\end{array}
\\
P(B3)= \left( \frac{1}{3} \right) ^4+\left( \frac{1}{3} \right) ^6 3^1 +\left( \frac{1}{3} \right) ^8 3^2+\left( \frac{1}{3} \right) ^{10} 3^3+...= \frac{1}{54}
}\)

Trasa B4 jest równoważna trasie B1, trasa B5 odpowiada trasie B2, a B6 trasie B3.

\(\displaystyle{ P(B)=2(P(B1)+P(B2)+P(B3))= \frac{37}{108} }\)
(o ile nie pomyliłem się w rachunkach)

PS
Jak znajdę czas to dopiszę kolejne podpunkty, chyba że ktoś wpisze prostsze rozwiązanie.

[Dasio11]

(i) Niech \(\displaystyle{ (V, E)}\) będzie grafem odpowiadającym szkieletowi sześcianu i dla każdego \(\displaystyle{ u \in V}\) niech \(\displaystyle{ N(u)}\) oznacza (trzyelementowy) zbiór jego sąsiadów. Oznaczmy też przez \(\displaystyle{ p_u}\) prawdopodobieństwo, że gdyby gąsienica zaczęła spacer w wierzchołku \(\displaystyle{ u}\), to przykleiłaby się w \(\displaystyle{ B}\). Mamy wtedy \(\displaystyle{ p_B = 1}\) i \(\displaystyle{ p_C = 0}\), a ponadto

\(\displaystyle{ p_u = \frac{1}{3} \sum \limits_{v \in N(u)} p_v}\) dla \(\displaystyle{ u \notin \{ B, C \} \qquad (*)}\)

Ponieważ graf jest dwudzielny, podstawiając do prawej strony każdego równania \(\displaystyle{ (*)}\) wartości \(\displaystyle{ p_v}\) wynikające z pozostałych równań, otrzymamy dwa rozłączne układy czterech zmiennych. W zasadzie interesuje nas tylko ten z nich w którym występuje \(\displaystyle{ p_A}\). W każdym z tych układów jedna niewiadoma jest znana (\(\displaystyle{ p_B}\) i \(\displaystyle{ p_C}\)) a dwie inne są równe ze względu na odpowiednią symetrię sześcianu (zachowującą krawędź \(\displaystyle{ BC}\)). Te obserwacje na tyle upraszczają rachunki, że dają się wykonać w skończonym czasie. Jeśli się nie rąbnałem: \(\displaystyle{ p_A = \frac{4}{7}}\).

(ii) Ponieważ gąsienica musi przykleić się w \(\displaystyle{ B}\) lub w \(\displaystyle{ C}\) (bo prawdopodobieństwo nieskończonego spaceru, który omija oba wierzchołki, jest zerowe), zatem odpowiedź to \(\displaystyle{ 1-p_A = \frac{3}{7}}\).