Are You Ready For BRIMO?

(The upper problem is similar to this problem )

Suppose there is a pentagon with all its diagonals drawn. A bug stands at any vertices. We'll calculate how many ways there are for the bug to walk on the edges 9 times such that, it doesn't come back when finished.

Denote $P_n$ be the probability that the bug stands at the starting position after $n$ times walking.

The bug will be at the starting position after $n+1$ times walking only if these conditions follow:

• It wasn't at the starting position after $n$ times walking (with probability of $1-P_n$ ).

• It chooses to go back to the starting position (with probability of $\dfrac 14$ ).

Hence, we have this recursive formula $P_{n+1} = \dfrac 14(1-P_n)$ .

With $P_0=1, P_1=0$ , we can calculate to have $P_9 = \dfrac{13107}{65536}$ .

But $P_n$ is the probability that the bug stands at the starting position, so the probability that it doesn't stand at this vertice after 9 times is: $1-P_9=\dfrac{52429}{65536}$

There are 5 ways for the bug to choose the starting vertice, for each time it walks, there are 4 ways to choose the next destination, so the answer would be: $5 \times 4^9 \times (1-P_9) = \boxed{1048580}$