2013 USAMO Problems/Problem 2
For a positive integer plot
equally spaced points around a circle. Label one of them
, and place a marker at
. 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
distinct moves available; two from each point. Let
count the number of ways to advance around the circle exactly twice, beginning and ending at
, without repeating a move. Prove that
for all
.
Solution
we will use indution and dividing the question to consecutive odds and evens.
we iterate the equality
to
to get
subtracting the two we get
which is equivalent to
note that for the initial case
we have that
has the following moving options:
(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]](http://latex.artofproblemsolving.com/c/8/1/c81d87b2b56886abf3c2a051e06edbee8022bc91.png)
next we show that for