2013 USAMO Problems/Problem 2

For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle. Label one of them $A$ , and place a marker at $A$ . One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of $2n$ distinct moves available; two from each point. Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$ , without repeating a move. Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$ .

Solution

we will use indution and dividing the question to consecutive odds and evens. we iterate the equality $a_{n-1}+a_n=2^n$ to $n+1$ to get $a_n+a_{n+1}=2^{n+1}$ subtracting the two we get $a_n+a_{n+1}-(a_{n-1}+a_n)=2^{n+1}-2^{n}$ $a_{n+1}-a_{n-1}=2^n(2-1)=2^n$ which is equivalent to $a_{n+1}a_{n-1}=2^n+a_{n-1}$ note that for the initial case $(n=4)$ we have that $a_{n-1}=a_{3}$ has the following moving options:

$2,2,2$
$1,2,2,1$
$1,1,2,2$
$2,2,1,1$
$2,1,1,2$

(one can easily show that there are no other options)

$[asy] /* from geogebra: see azjps, userscripts.org/scripts/show/72997 */ import graph; defaultpen(linewidth(0.7)+fontsize(10)); size(100); /* segments and figures */ draw(circle((5,0),5)); /* points and labels */ dot((5,5)); dot((9.33,-2.5)); dot((0.66,-2.5)); clip((-3.72991,-6.47862)--(-3.72991,17.44518)--(32.23039,17.44518)--(32.23039,-6.47862)--cycle); [/asy]$

next we show that for $n=4$ $a_{n+1}=a_5=2^4+a_3=21$

Page

Toolbox

Search

2013 USAMO Problems/Problem 2

Solution