Difference between revisions of "2006 USAMO Problems/Problem 5"

Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
A mathematical frog jumps along the number line. The frog starts at 1, and jumps according to the following rule: if the frog is at integer <math> \displaystyle n </math>, then it can jump either to <math> \displaystyle n+1 </math> or to <math>n+2^{m_n+1}</math> where <math>2^{m_n}</math> is the largest power of 2 that is a factor of <math> \displaystyle n </math>. Show that if <math>k\ge 2</math> is a positive integer and <math> \displaystyle i </math> is a nonnegative integer, then the minimum number of jumps needed to reach <math> \displaystyle 2^i k </math> is greater than the minimum number of jumps needed to reach <math> \displaystyle 2^i </math>.
+
A mathematical frog jumps along the number line. The frog starts at 1, and jumps according to the following rule: if the frog is at integer <math>n </math>, then it can jump either to <math>n+1 </math> or to <math>n+2^{m_n+1}</math> where <math>2^{m_n}</math> is the largest power of 2 that is a factor of <math>n </math>. Show that if <math>k\ge 2</math> is a positive integer and <math>i </math> is a nonnegative integer, then the minimum number of jumps needed to reach <math>2^i k </math> is greater than the minimum number of jumps needed to reach <math>2^i </math>.
  
 
== Solution ==
 
== Solution ==
Line 14: Line 14:
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 13:41, 4 July 2013

Problem

A mathematical frog jumps along the number line. The frog starts at 1, and jumps according to the following rule: if the frog is at integer $n$, then it can jump either to $n+1$ or to $n+2^{m_n+1}$ where $2^{m_n}$ is the largest power of 2 that is a factor of $n$. Show that if $k\ge 2$ is a positive integer and $i$ is a nonnegative integer, then the minimum number of jumps needed to reach $2^i k$ is greater than the minimum number of jumps needed to reach $2^i$.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

See Also

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS