https://artofproblemsolving.com/wiki/index.php?title=1979_IMO_Problems/Problem_6&feed=atom&action=history 1979 IMO Problems/Problem 6 - Revision history 2021-06-16T12:27:36Z Revision history for this page on the wiki MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=1979_IMO_Problems/Problem_6&diff=143996&oldid=prev Hamstpan38825: Created page with "==Problem== Let $A$ and $E$ be opposite vertices of an octagon. A frog starts at vertex $A.$ From any vertex except $E$ it jumps to..." 2021-01-30T03:06:50Z <p>Created page with &quot;==Problem== Let &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;E&lt;/math&gt; be opposite vertices of an octagon. A frog starts at vertex &lt;math&gt;A.&lt;/math&gt; From any vertex except &lt;math&gt;E&lt;/math&gt; it jumps to...&quot;</p> <p><b>New page</b></p><div>==Problem==<br /> Let &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;E&lt;/math&gt; be opposite vertices of an octagon. A frog starts at vertex &lt;math&gt;A.&lt;/math&gt; From any vertex except &lt;math&gt;E&lt;/math&gt; it jumps to one of the two adjacent vertices. When it reaches &lt;math&gt;E&lt;/math&gt; it stops. Let &lt;math&gt;a_n&lt;/math&gt; be the number of distinct paths of exactly &lt;math&gt;n&lt;/math&gt; jumps ending at &lt;math&gt;E&lt;/math&gt;. Prove that:&lt;cmath&gt; a_{2n-1}=0, \quad a_{2n}={(2+\sqrt2)^{n-1} - (2-\sqrt2)^{n-1} \over\sqrt2}. &lt;/cmath&gt;<br /> <br /> ==Solution==<br /> First the part &lt;math&gt;a_{2n-1}=0&lt;/math&gt; It's pretty obvious. Let's make a sequence &lt;math&gt;b&lt;/math&gt; 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 &lt;math&gt;\sum b_{i}&lt;/math&gt; from &lt;math&gt;i =1&lt;/math&gt; to &lt;math&gt;i =2n-1&lt;/math&gt; should be equal to either 4 or -4. But this sum is odd, so we have &lt;math&gt;a_{2n-1}= 0&lt;/math&gt;<br /> <br /> Now the less obvious part.<br /> Let's name &lt;math&gt;f(X,y)&lt;/math&gt; the number of ways, in which we can come to vertex X in y moves.<br /> <br /> Then<br /> &lt;math&gt;f(E,2n) = f(F,2n-1)+f(D, 2n-1) = f(C, 2n-2)+f(G, 2n-2) =&lt;/math&gt;<br /> &lt;math&gt;f(D, 2n-3)+f(B, 2n-3)+f(F, 2n-3)+f(H, 2n-3) =&lt;/math&gt;<br /> &lt;math&gt;2f(D, 2n-5)+2f(F, 2n-5)+4f(H,2n-5)+4f(B, 2n-5) =&lt;/math&gt;<br /> &lt;math&gt;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)] =&lt;/math&gt;<br /> &lt;math&gt;4f(E,2n-2)-2f(E,2n-4)&lt;/math&gt;<br /> <br /> Now we can find a solution to this recurrence or simply prove by induction the given answer.<br /> <br /> This solution was posted and copyrighted by Myszon11. The original thread for this problem can be found here: [https://aops.com/community/p712390]<br /> <br /> {{alternate solutions}}<br /> <br /> == See Also == {{IMO box|year=1979|num-b=5|after=Last Question}}</div> Hamstpan38825