Question

ABCDEFGH is a regular octagon. A and E are opposite vertices. A frog starts at A, may jump to adjacent vertices except E. When it reaches E, it stops. Let $a_n$ = number of distinct paths of exactly $n$ jumps ending at E. Find $a_{2n-1}$.

• A. Zero
• B. Four
• C. $2n - 1$
• D. Can't be determined

Hint:

On a bipartite graph, vertices in same part can only be connected by even-length paths.

Answer 1

The Correct Option is A

In an even cycle graph, vertices A and E are at even distance (4 edges in octagon). Thus any path from A to E must have even number of jumps. An odd number $2n-1$ is impossible. \[ \boxed{0} \]