第3题

对于正整数

k

，令

f(k)

为

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

中二进制表示恰有三个

1

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

m

都能取为某个

f(k)

，并求出恰有一个

k

满足

f(k)=m

的所有

m

。

第 3/5 步：刻画唯一的

k

通俗地说

考察某个取值只有一个 $k$ 的条件。

2k-1\text{ and }2k+1\text{ have three }1\text{s}\iff k-1\text{ and }k\text{ have two }1\text{s}

详细分析

由于增量只能是 $0$ 或 $1$ ， $f(k)=m$ 唯一当且仅当它前后的两个增量都为 $1$ ，即 $2k-1$ 与 $2k+1$ 都有三个 $1$ 。添上或去掉二进制末位可知，这等价于 $k-1$ 与 $k$ 都有两个 $1$ 。