第3問

正整数

k

に対し、

f(k)

を

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

の中で二進表示に

1

がちょうど三つある整数の個数とする。任意の正整数

m

が

f(k)

の値として現れることを示し、

f(k)=m

となる

k

がちょうど一つであるような

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)$ である。