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

Ragnarok23 (talk | contribs) |
Ragnarok23 (talk | contribs) |
||

Line 1: | Line 1: | ||

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

+ | A mathematical frog jumps along the number line. The frog starts at <math>1</math>, 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 <math>2</math> 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^ik</math> is greater than the minimum number of jumps needed to reach <math> 2^i.</math> | ||

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

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

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

## Revision as of 11:08, 12 July 2006

## Problem

A mathematical frog jumps along the number line. The frog starts at , 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 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