Anyone with a solution

Ummm... isn't it pretty easy by recursion? Just consider the # of ways of landing on B, D, F, and H in an odd number of steps. Edit: Ermmm yes I meant recurrence , although it is a type of recursion

probability1.01 wrote: Ummm... isn't it pretty easy by recursion? Just consider the # of ways of landing on B, D, F, and H in an odd number of steps. Recurrence you mean. And yes you don't need anything else.

If wiequan and probability1.01 have better things to do, then i will post my solution First the part $a_{2n-1}=0$ It's preety obvious. Let's make a sequence $b$ of 1 and -1, setting 1 when the frog jumps left and -1 when it jumps right. If the frog would want to come to vertex E from vertex A, then $\sum b_{i}$ from $i =1$ to $i =2n-1$ should be equeal to either 4 or -4. But this sum is odd, so we have $a_{2n-1}= 0$ Now the less obvious part. Let's name $f(X,y)$ the number of ways, in which we can come to vertex X in y moves. Then $f(E,2n) = f(F,2n-1)+f(D, 2n-1) = f(C, 2n-2)+f(G, 2n-2) =$ $f(D, 2n-3)+f(B, 2n-3)+f(F, 2n-3)+f(H, 2n-3) =$ $2f(D, 2n-5)+2f(F, 2n-5)+4f(H,2n-5)+4f(B, 2n-5) =$ $4[ f(B,2n-5)+f(D, 2n-5)+f(F,2n-5)+f(H, 2n-5) ]-2 [ f(F,2n-5)+f(D,2n-5)] =$ $4f(E,2n-2)-2f(E,2n-4)$ Now we can find a solution to this reccurenc or simply prove by induction the given answer. I didn't explain to much because I'm lazy, but I hope everything's clear.

It's my first IMO combinatorics solution. There's some mystery about counting problems having being lengthy solution. Anyway let's post the solution.

$\text{Let }a_n, b_n, c_n, d_n, e_n, f_n, g_n, h_n,$ be the number of exactly $n$, distinct paths of jump ending at the points $A,B,C,D,E,F,G,H$ of the octagon respectively. By symmetry we have, $b_n=h_n, c_n=g_n, d_n=f_n.$ We also have \begin{align*} e_n=d_{n-1} +f_{n+1}=2d_{n-1}, \\ d_n=c_{n-1}, c_n=b_{n-1}+d_{n-1}, \\ a_n=2b_{n-1}, b_n=a_{n-1}+c_{n-1}. \end{align*}From the first two we get $d_{n-1}=e_n/2$ and $c_{n-1}=d_n=e_{n+1}/2.$ Subbing into the third we get $b{n-1}=1/2(e_{n+2}-e_n).$ From the fourth, $a_n=e_{n+2}-e_n.$ The fifth will be $$e_{n+3}-4e_{n+4}+2e_{n-1}=0.$$ Now from a well known result in recursion we have, $$e_n=as^n+b(-s)^n+cr^n+d(-r)^n,$$where $s=\sqrt{2+\sqrt{2}}$ and $r=\sqrt{2-\sqrt{2}}.$ It follows that $e_1=e_2=e_3=0$, and $e_4=2.$ And therefore, \begin{align*} (a-b)s+(c-d)r=0, \\ (a+b)s^2+(c+d)r^2=0, \\ (a-b)s^3+(c-d)r^3=0, \\ (a+b)s^4+(c+d)r^4=2.\end{align*}The first and third equations imply $a=b$ and $c=d$ which further imply $e_{2n-1}=0.$ Solving the second and fourth equations we get $$a=b= \frac{r^2}{4\sqrt{2}}, c=d=-\frac{s^2}{4\sqrt{2}}.$$ Finally we have, $$e_{2n}=2as^{2n}+2cr^{2n}=\frac{s^2r^2}{2\sqrt{2}} (s^{2n-2}-r^{2n-2})=\frac{(2+\sqrt{2})^{n-1} -(2-\sqrt{2})^{n-1}}{\sqrt{2}}.$$$\text{Q.E.D.}$ P.S: @above I find no implication of your post except pure nonsense, you might want to redact such spamful message.

Attachments:

ZETA_in_olympiad wrote: $\text{Let }a_n, b_n, c_n, d_n, e_n, f_n, g_n, h_n,$ be the number of exactly $n$, distinct paths of jump ending at the $8$ points of the octagon respectively. By symmetry we have, $b_n=h_n, c_n=g_n, d_n=f_n.$ We also have \begin{align*} e_n=d_{n-1} +f_{n+1}=2d_{n-1}, \\ d_n=c_{n-1}, c_n=b_{n-1}+d_{n-1}, \\ a_n=2b_{n-1}, b_n=a_{n-1}+c_{n-1}. \end{align*}From the first two we get $d_{n-1}=e_n/2$ and $c_{n-1}=d_n=e_{n+1}/2.$ Subbing into the third we get $b{n-1}=1/2(e_{n+2}-e_n).$ From the fourth, $a_n=e_{n+2}-e_n.$ The fifth will be $$e_{n+3}-4e_{n+4}+2e_{n-1}=0.$$ Now from a well known result in recursion we have, $$e_n=as^n+b(-s)^n+cr^n+d(-r)^n,$$where $s=\sqrt{2+\sqrt{2}}$ and $r=\sqrt{2-\sqrt{2}}.$ It follows that $e_1=e_2=e_3=0$, and $e_4=2.$ And therefore, \begin{align*} (a-b)s+(c-d)r=0, \\ (a+b)s^2+(c+d)r^2=0, \\ (a-b)s^3+(c-d)r^3=0, \\ (a+b)s^4+(c+d)r^4=2.\end{align*}The first and third equations imply $a=b$ and $c=d$ which further imply $e_{2n-1}=0.$ Solving the second and fourth equations we get $$a=b= \frac{r^2}{4\sqrt{2}}, c=d=-\frac{s^2}{4\sqrt{2}}.$$ Finally we have, $$e_{2n}=2as^{2n}+2cr^{2n}=\frac{s^2r^2}{2\sqrt{2}} (s^{2n-2}-r^{2n-2})=\frac{(2+\sqrt{2})^{n-1} -(2-\sqrt{2})^{n-1}}{\sqrt{2}}.$$$\text{Q.E.D.}$ P.S: @above I find no implication of your post except pure nonsense, you might want to redact such spamful message. Wow nice solution! Seems right to me. How did you motivate the definitions of \(a_n\), \(b_n\), \(c_n\), etc though?

rama1728 wrote: Wow nice solution! Seems right to me. How did you motivate the definitions of \(a_n\), \(b_n\), \(c_n\), etc though? Do you want the picture of the octagon? I added the motivation picture. P.S. Please try to keep quotations short.