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 をすべて求めよ。
ステップ 5/5: 対応する一意な値を数える
ざっくり言うと

対応する一意な値を数える

m=n(n−1)2+1m=\dfrac{n(n-1)}2+1
詳しい解説

区間は {2n+3,…,2n+1+4}\{2^n+3,\ldots,2^{n+1}+4\} である。その中で 1 が三つある数は、0≤r<s<n0\le r<s<n に対する 2n+2r+2s2^n+2^r+2^s の (n2)=n(n−1)2\binom n2=\frac{n(n-1)}2 個と、2n+1+32^{n+1}+3 である。従って一意な値は n≥2n\ge2 に対する m=n(n−1)2+1m=\frac{n(n-1)}2+1、すなわち 2,4,7,11,…2,4,7,11,\ldots である。