MathLabs

第3問

正整数 kk に対し、f(k)f(k) を {k+1,…,2k}\{k+1,\ldots,2k\} の中で二進表示に 11 がちょうど三つある整数の個数とする。任意の正整数 mm が f(k)f(k) の値として現れることを示し、f(k)=mf(k)=m となる kk がちょうど一つであるような mm をすべて求めよ。
ステップ 3/5: 一意な kk を特徴付ける
ざっくり言うと

ある値に対応する kk が一つだけとなる条件を調べる。

2k−1 and 2k+1 have three 1s  ⟺  k−1 and k have two 1s2k-1\text{ and }2k+1\text{ have three }1\text{s}\iff k-1\text{ and }k\text{ have two }1\text{s}
詳しい解説

増分は 00 または 11 なので、f(k)=mf(k)=m が一意となるのは前後の二つの増分がともに 11 のとき、すなわち 2k−12k-1 と 2k+12k+1 がともに 11 を三つ持つときである。二進表示の末尾に 1 を付ける関係から、これは k−1k-1 と kk がともに 11 を二つ持つことと同値である。