2009 Putnam B6

Prove that for every positive integer $n$, there is a sequence of integers

$a_0, a_1, \dots, a_{2009}$ with $a_0 = 0$ and $a_{2009} = n$ such that each term

after $a_0$ is either an earlier term plus $2^k$ for some nonnegative integer $k$,

or of the form $b\,\mathrm{mod}\,c$ for some earlier positive terms $b$ and $c$.

[Here $b\,\mathrm{mod}\,c$ denotes the remainder when $b$ is divided by $c$,

so $0 \leq (b\,\mathrm{mod}\,c) < c$.]

证明对于每个正整数 $n$，都存在一个整数序列

$a_0, a_1, \dots, a_{2009}$ 其中 $a_0 = 0$ 且 $a_{2009} = n$ 使得每一项

$a_0$ 之后是一个较早的术语加上 $2^k$(对于某些非负整数 $k$)，

或者对于一些早期的正项 $b$ 和 $c$，采用 $b\,\mathrm{mod}\,c$ 的形式。

[这里$b\,\mathrm{mod}\,c$表示$b$除以$c$的余数，

所以 $0 \leq (b\,\mathrm{mod}\,c) < c$.]