第3题

对于正整数

k

，令

f(k)

为

\{k+1,\ldots,2k\}

中二进制表示恰有三个

1

的整数个数。证明每个正整数

m

都能取为某个

f(k)

，并求出恰有一个

k

满足

f(k)=m

的所有

m

。

第 1/5 步：追踪函数的一步变化

通俗地说

追踪函数的一步变化

f(k+1)-f(k)\in\{0,1\}

详细分析

从 $k$ 变到 $k+1$ 时移去 $k+1$ ，加入 $2k+1$ 和 $2k+2$ 。 $2k+2$ 的二进制表示是在 $k+1$ 的表示末尾添一个 0，因此这两项贡献抵消。于是当且仅当 $2k+1$ 有三个 $1$ 时 $f(k+1)=f(k)+1$ ，否则 $f(k+1)=f(k)$ 。