2006 USAMO 第 5 题

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

一只数学青蛙沿着数轴跳跃。青蛙从 1 开始，并根据以下规则跳跃：如果青蛙位于整数 $n$，则它可以跳到 $n+1$ 或 $n+2^{m_n+1}$，其中 $2^{m_n}$ 是 2 的最大幂，即 $n$ 的因数。证明如果 $k\ge 2$ 是正整数且 $i$ 是非负整数，则到达 $2^i k$ 所需的最小跳转次数大于到达 $2^i$ 所需的最小跳转次数。