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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_USAMO_Problems/Problem_5&oldid=54798"