在不大于2003的正整数中，二进制表示下1比0多的数有 $m$ 个，求 $m$ 的后三位．
【难度】
【出处】
2003年第21届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
155
【解析】
由于 $2003<2047={{2}^{11}}-1$，所求的整数用二进制表示之后最多只有11位数字．我们先计算从1到2047中有多少个数二进制表示下1比0多．假设一个数额二进制表示有 $d$ 为，那么当其中至少有 $\left[ \frac{d}{2}\right]+1$ 个1时，1的个数才多于0的个数．由于首位必须为1，故其他的 $d-1$ 个位数上至少要有 $\left[ \frac{d}{2} \right]$ 个1．故二进制表示下有 $d$ 位US胡子，且其中1比0多的数有 $C_{d-1}^{\left[ \frac{d}{2}\right]}+C_{d-1}^{\left[ \frac{d}{2} \right]+1}+\cdots +C_{d-1}^{d-1}$ 个．当 $d$ 是偶数时，它等于 $\frac{1}{2}\cdot{{2}^{d-1}}={{2}^{d-2}}$（这里利用了组合数的对称性），当 $d$ 是奇数时，它等于 $\frac{1}{2}\cdot \left({{2}^{d-1}}+C_{d-1}^{\left[ \frac{d}{2} \right]}\right)={{2}^{d-2}}+\frac{1}{2}\cdot C_{d-1}^{\frac{d-1}{2}}$．因此1到2047中有
$\displaystyle \sum\limits_{d=1}^{11}{{{2}^{d-2}}}+\sum\limits_{1\leqslant d\leqslant 11,2\left| d \right.}{\frac{1}{2}\cdot C_{d-1}^{\frac{d-1}{2}}}$
$=\left({{2}^{10}}-\frac{1}{2} \right)+\frac{1}{2}\cdot \left( 1+2+6+20+70+252\right)=1199$
个数在二进制表示下1比0多．注意到 $2003>1984={{\left(11111000000 \right)}_{2}}$，故从2004到2047的所有数的二进制表示中都至少有六个1，故它们都是二进制表示下1比0多的数，故所求的数目是 $1199-\left( 2047-2003\right)=1155$，这个数除以1000的余数为155．
$\displaystyle \sum\limits_{d=1}^{11}{{{2}^{d-2}}}+\sum\limits_{1\leqslant d\leqslant 11,2\left| d \right.}{\frac{1}{2}\cdot C_{d-1}^{\frac{d-1}{2}}}$
$=\left({{2}^{10}}-\frac{1}{2} \right)+\frac{1}{2}\cdot \left( 1+2+6+20+70+252\right)=1199$
个数在二进制表示下1比0多．注意到 $2003>1984={{\left(11111000000 \right)}_{2}}$，故从2004到2047的所有数的二进制表示中都至少有六个1，故它们都是二进制表示下1比0多的数，故所求的数目是 $1199-\left( 2047-2003\right)=1155$，这个数除以1000的余数为155．
答案
解析
备注
