There are 20 frogs in the vertex's of a dodecahedron (one frog in one vertex) for the first time. At every step, the frog jump to one of its three neighboring vertices with equal probability.
Let denote the number of random steps from vertex to vertex . The frog who starts on vertex has to move away first.
What is sum of the expected value of steps until frogs have visited vertex of dodecahedron from all starting vertices ( )?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
We can make use of the dodecahedron's symmetries to help with this problem. All that matters is how far away the frog's starting vertex is from vertex 1 . In the diagram below (a dodecahedral graph; vertices and edges on the graph correspond to vertices and edges on the dodecahedron), I've coloured vertex 1 white; vertices one edge away from vertex 1 are green, 2 edges away blue, and so on:
If a frog starts on a red vertex, and makes one hop, then (with equal probability) it will end up on either a new red vertex, a blue one, or a yellow one.
Using R for the expected number of steps to reach vertex 1 from a red vertex, B for the expected number of steps to reach vertex 1 from a blue vertex, and so on, this can be written as R = 1 + 3 1 ( R + B + Y )
Continuing this way, we find R B G Y P W = 1 + 3 1 ( R + B + Y ) = 1 + 3 1 ( R + B + G ) = 1 + 3 2 B = 1 + 3 1 ( 2 R + P ) = 1 + Y = 1 + G
where the last of these represents the fact that the frog starting on vertex 1 has to hop away first.
This is a system of six linear equations in six unknowns; solving, we find ( R , B , G , Y , P , W ) = ( 3 2 , 2 7 , 1 9 , 3 4 , 3 5 , 2 0 )
Counting the vertices of each colour and totalling, the required answer comes to 5 6 8 .