Difference between revisions of "2013 USAMO Problems/Problem 2"
(Blanked the page) |
|||
Line 1: | Line 1: | ||
+ | For a positive integer <math>n\geq 3</math> plot <math>n</math> equally spaced points around a circle. Label one of them <math>A</math>, and place a marker at <math>A</math>. 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 <math>2n</math> distinct moves available; two from each point. Let <math>a_n</math> count the number of ways to advance around the circle exactly twice, beginning and ending at <math>A</math>, without repeating a move. Prove that <math>a_{n-1}+a_n=2^n</math> for all <math>n\geq 4</math>. | ||
+ | == Solution == | ||
+ | we will use indution and dividing the question to consecutive odds and evens. | ||
+ | we iterate the equality <math>a_{n-1}+a_n=2^n</math> | ||
+ | to <math>n+1</math> to get <cmath>a_n+a_{n+1}=2^{n+1}</cmath> | ||
+ | subtracting the two we get <math>a_n+a_{n+1}-(a_{n-1}+a_n)=2^{n+1}-2^{n}</math> | ||
+ | <cmath>a_{n+1}-a_{n-1}=2^n(2-1)=2^n</cmath> | ||
+ | which is equivalent to <cmath>a_{n+1}a_{n-1}=2^n+a_{n-1}</cmath> | ||
+ | note that for the initial case <math>(n=4)</math> | ||
+ | we have that <math>a_{n-1}=a_{3}</math> has the following moving options: | ||
+ | *<math>2,2,2</math> | ||
+ | *<math>1,2,2,1</math> | ||
+ | *<math>1,1,2,2</math> | ||
+ | *<math>2,2,1,1</math> | ||
+ | *<math>2,1,1,2</math> | ||
+ | (one can easily show that there are no other options) | ||
+ | <center><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></center> | ||
+ | |||
+ | next we show that for <math>n=4</math> <math>a_{n+1}=a_5=2^4+a_3=21</math> |
Revision as of 21:55, 9 April 2014
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