Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 USAMO Problems/Problem 2"
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>.
 
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>.
−
{{MAA Notice}}
+
 
 +
== 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:38, 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$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_USAMO_Problems/Problem_2&oldid=61406"