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

Ragnarok23 (talk | contribs) |
|||

Line 1: | Line 1: | ||

== Problem == | == Problem == | ||

− | A mathematical frog jumps along the number line. The frog starts at | + | |

+ | 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>. | ||

+ | |||

== Solution == | == Solution == | ||

+ | |||

+ | {{solution}} | ||

+ | |||

== See Also == | == See Also == | ||

− | *[[2006 USAMO Problems]] | + | |

+ | * [[2006 USAMO Problems]] | ||

+ | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=490682#p490682 Discussion on AoPS/MathLinks] | ||

+ | |||

+ | |||

+ | [[Category:Olympiad Number Theory Problems]] |

## Revision as of 19:48, 1 September 2006

## 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 , then it can jump either to or to where is the largest power of 2 that is a factor of . Show that if is a positive integer and is a nonnegative integer, then the minimum number of jumps needed to reach is greater than the minimum number of jumps needed to reach .

## Solution

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