[组合] 旧论坛的一道组合数奇偶题转过来

kuing

原贴链接：http://kkkkuingggg.haotui.com/thread-1677-1-1.html
原标题：2008安徽初赛第6题
发贴人：guanmo
题目：

6. 设多项式 $(1+x)^{2008}=a_0+a_1x+\cdots+a_{2008}x^{2008}$，则 $a_0$, $a_1$, $\ldots$, $a_{2008}$ 中，共有（  ）个是偶数。

问题显然等价于问 $C_{2008}^0$, $C_{2008}^1$, $\ldots$, $C_{2008}^{2008}$ 有多少个偶数。

kuing

组合数奇偶性问题，在2007年高考湖南理数15就出现过，以前在人教就有过讨论（比如 http://bbs.pep.com.cn/forum.php?mod=viewthread&tid=299907 等等）
而在2006年有一篇《二项式系数奇偶性的判定准则》的文章（见 http://wenku.baidu.com/view/14b8c385b9d528ea81c779f1）
文章里证明的是：

判定准则  $C_n^m$（$m\leqslant n$）的奇偶性取决于 $m$ 和 $n-m$ 的二进制表达式中是否存在位于同一数位上的两个数码都是 1，如果存在，$C_n^m$ 是偶数，否则 $C_n^m$ 就是奇数。

有了这个，怎么用于本题？……待续……

kuing

$n=2008=11111011000_2$
当 $m=0$ 时 $C_n^m=1$ 为奇数；
当 $m=1000_2$ 时 $n-m=11111010000_2$，$C_n^m$ 为奇数；
当 $m=10000_2$ 时 $n-m=11111001000_2$，$C_n^m$ 为奇数；
当 $m=11000_2$ 时 $n-m=11111000000_2$，$C_n^m$ 为奇数；
……
也就是将那些1拿过去，总共有7个1，所以这样数下去可以数出有 $2^7=128$ 个奇数（$m=0$ 也计算在内了）。
但是除此之外的是不是都是偶数呢？看上去好像是，如果是，那答案就是 $2009-128=1881$ 个偶数（这的确是原题选项之一！）。
还有待证明……继续待续……

kuing

大概想到了，但是有点难表达……

$n=2008=11111011000_2$，以下用 $\text{*}$ 表示任取 $0$ 或 $1$。

如果 $m=\text{*****0**000}_2$，那么 $n-m=\text{*****0**000}_2$，并且这两个数对应位置上的 $\text{*}$ 之和为 $1$。
例如 $m=11010010000_2$，那么 $n-m=00101001000_2$。  
所以 $m=\text{*****0**000}_2$ 这种情况下不可能出现同一数位上都为 $1$，由判定准则知 $C_n^m$ 是奇数。
可见这类情况共包含了 $2^7=128$ 个奇数。

如果 $m=\text{**********1}_2$，因为 $n_2$ 最后的一位为 $0$，则 $n-m=\text{**********1}_2$，由判定准则知 $C_n^m$ 是偶数；
如果 $m=\text{*********10}_2$，因为 $n_2$ 倒数第二位为 $0$，则 $n-m=\text{*********10}_2$，由判定准则知 $C_n^m$ 是偶数；
如果 $m=\text{********100}_2$，因为 $n_2$ 倒数第三位为 $0$，则 $n-m=\text{********100}_2$，由判定准则知 $C_n^m$ 是偶数；
如果 $m=\text{*****100000}_2$，因为 $n_2$ 倒数第六位为 $0$，则 $n-m=\text{*****111000}_2$，由判定准则知 $C_n^m$ 是偶数；
如果 $m=\text{*****101000}_2$，因为 $n_2$ 倒数第六位为 $0$，则 $n-m=\text{*****110000}_2$，由判定准则知 $C_n^m$ 是偶数；
如果 $m=\text{*****110000}_2$，因为 $n_2$ 倒数第六位为 $0$，则 $n-m=\text{*****101000}_2$，由判定准则知 $C_n^m$ 是偶数。
这足以说明，除了 $m=\text{*****0**000}_2$ 之外的所有情况都是偶数。

综上所述，所求的偶数个数为 $2009-128=1881$。

kuing

不难看出，楼上的方法具有一般性，也就是说，我们可以得到这样一条一般结论：

若正整数 $n$ 的二进制表达式中具有 $k$ 个 $1$，那么 $C_n^0$, $C_n^1$, $\ldots$, $C_n^n$ 中的奇数个数为 $2^k$。

这也可以算是“判定准则”的另一条推论了，比那篇文章的最后的推论要一般一些。

零定义

回复 5# kuing
虽然看不懂，但看起来很牛的样子…看到一个小小的笔误，应该是偶数…

kuing

回复 6# 零定义

嗯，改了

isee

我擦，2018年3月广州高三理科一模第16题原来是竞赛题（改）。

力工

回复 8# isee
这个应该就是湖南高考题的改动吧。

isee

不难看出，楼上的方法具有一般性，也就是说，我们可以得到这样一条一般结论：

若正整数 $n$ 的二进制表达 ...
kuing 发表于 2013-8-31 15:00

用二进制中$n$的数字和$S(n)$表示，奇数有$2^{S(n)}$个.

不知这样能不能推广到3的倍数之类。。。