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 をすべて求めよ。
ステップ 2/5: 全ての正の値が現れることを示す
前のステップ次のステップ
ざっくり言うと

全ての正の値が現れることを示す

2r+2s+1(r>s>0)2^r+2^s+1\quad(r>s>0)
詳しい解説

r>s>0r>s>0 なら 2r+2s+12^r+2^s+1 は 11 をちょうど三つ持つので、k=(2r+2s)/2k=(2^r+2^s)/2 で 2k+12k+1 がこの性質を持つ例は無限にある。従って f(k)f(k) は上に有界でない。00 から始まり増分は 00 または 11 なので、全ての正整数を取る。