2008 APMO 第 4 题

Consider the function $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$, where $\mathbb{N}_{0}$ is the set of all non-negative integers, defined by the following conditions:

(i) $f(0)=0$,

(ii) $f(2 n)=2 f(n)$ and

(iii) $f(2 n+1)=n+2 f(n)$ for all $n \geq 0$.

(a) Determine the three sets $L:=\{n \mid f(n)<f(n+1)\}, E:=\{n \mid f(n)=f(n+1)\}$, and $G:=\{n \mid f(n)>f(n+1)\}$.

(b) For each $k \geq 0$, find a formula for $a_{k}:=\max \left\{f(n): 0 \leq n \leq 2^{k}\right\}$ in terms of $k$.

考虑函数 $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$，其中 $\mathbb{N}_{0}$ 是所有非负整数的集合，由以下条件定义：

(i)$f(0)=0$，

(ii) $f(2 n)=2 f(n)$ 并且

(iii) 对于所有$n \geq 0$，$f(2 n+1)=n+2 f(n)$。

(a) 确定三个集合 $L:=\{n \mid f(n)<f(n+1)\}、E:=\{n \mid f(n)=f(n+1)\}$ 和 $G:=\{n \mid f(n)>f(n+1)\}$。

(b) 对于每个 $k \geq 0$，找到 $a_{k}:=\max \left\{f(n): 0 \leq n \leq 2^{k}\right\}$ 以 $k$ 表示的公式。