Difference between revisions of "2013 USAMO Problems/Problem 2"

Revision as of 21:55, 9 April 2014

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$

@@ 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>

Page

Toolbox

Search

Difference between revisions of "2013 USAMO Problems/Problem 2"

Revision as of 21:55, 9 April 2014

Solution