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"
(→‎Solution)
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>.
−
 
−
== 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 23:21, 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$.

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