Frogs jump on dodecahedron vertex's

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 M ( k , 1 ) M(k,1) denote the number of random steps from vertex k k to vertex 1 1 . The frog who starts on vertex 1 1 has to move away first.

What is sum of the expected value of steps M ( k , 1 ) M(k,1) until frogs have visited vertex 1 1 of dodecahedron from all starting vertices ( 1 , 2 , 3 , , 20 1,2,3,\ldots,20 )?

And another discussion problem: frog-random-walk-on-tetrahedron .


The answer is 568.

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.

1 solution

Chris Lewis
Sep 29, 2020

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 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 1 white; vertices one edge away from vertex 1 1 are green, 2 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 R for the expected number of steps to reach vertex 1 1 from a red vertex, B B for the expected number of steps to reach vertex 1 1 from a blue vertex, and so on, this can be written as R = 1 + 1 3 ( R + B + Y ) R=1+\frac13 (R+B+Y)

Continuing this way, we find R = 1 + 1 3 ( R + B + Y ) B = 1 + 1 3 ( R + B + G ) G = 1 + 2 3 B Y = 1 + 1 3 ( 2 R + P ) P = 1 + Y W = 1 + G \begin{aligned} R &=1+\frac13 (R+B+Y) \\ B &=1+\frac13 (R+B+G) \\ G &=1+\frac23 B \\ Y &=1+\frac13 (2R+P) \\ P &=1+Y \\ W &=1+G \end{aligned}

where the last of these represents the fact that the frog starting on vertex 1 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 ) = ( 32 , 27 , 19 , 34 , 35 , 20 ) (R,B,G,Y,P,W)=(32,27,19,34,35,20)

Counting the vertices of each colour and totalling, the required answer comes to 568 \boxed{568} .

Thanks for attention. Fine solution. I solve this use Absorbing Markov chain.

Yuriy Kazakov - 8 months, 2 weeks ago

Log in to reply

Thanks! I used a Markov chain too, originally, before thinking of this method. You should post your solution too (it's a more flexible approach).

Chris Lewis - 8 months, 2 weeks ago

Log in to reply

Chris, what You think about next problem? At the beginning, 8 frogs sit in the vertices of the cube, one at each vertex - and then every second they start randomly jumping to adjacent vertices. Find the average time until the moment when they all gather at one vertex.

Yuriy Kazakov - 8 months, 2 weeks ago

Log in to reply

@Yuriy Kazakov Sounds like a great problem!

Chris Lewis - 8 months, 2 weeks ago

Log in to reply

@Chris Lewis ...even if it's a bit of a trick question (you might need to set it as multiple choice)

Chris Lewis - 8 months, 2 weeks ago

Log in to reply

@Chris Lewis Monte Carlo give answer from 10^5 to 10^7

Yuriy Kazakov - 8 months, 2 weeks ago

Log in to reply

@Yuriy Kazakov For the cube? Something's wrong there, I think.

Colour the vertices black and white so that adjacent vertices have opposite colours. Then each step, each frog jumps to a vertex of the opposite colour. So frogs on different colour vertices at the beginning are always on different colour vertices; they can never meet.

Chris Lewis - 8 months, 2 weeks ago

Log in to reply

@Chris Lewis Fine. Frogs never meet in one vertex.

Yuriy Kazakov - 8 months, 2 weeks ago

Log in to reply

@Yuriy Kazakov Not on a cube - but they can on other solids (eg a tetrahedron).

Chris Lewis - 8 months, 2 weeks ago

Log in to reply

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...