MathLabs

第3题

对于正整数 kk，令 f(k)f(k) 为 {k+1,…,2k}\{k+1,\ldots,2k\} 中二进制表示恰有三个 11 的整数个数。证明每个正整数 mm 都能取为某个 f(k)f(k)，并求出恰有一个 kk 满足 f(k)=mf(k)=m 的所有 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\}。其中有三个一的数包括 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。