集合 $\left\{ 0,1,2,\cdots ,2012\right\}$ 中有多少个元素 $k$，使得 $C_{2012}^{k}$ 是2012的倍数？
【难度】
【出处】
2012第11届CGMO试题
【标注】
【答案】
$1498$
【解析】
注意到 $2012=4\times 503$，其中 $p=503$ 是质数。
首先考虑组合数 $C_{2012}^{k}$ 是否是 $p=503$ 的倍数。
若 $p\not{|}k$，由得，从而
$C_{2012}^{k}=C_{4p}^{k}=\frac{(4p)!}{k!\cdot(4p-k)!}=\frac{4p}{k}C_{4p-1}^{k-1}\Rightarrow p|kC_{4p}^{k}\Rightarrow p|C_{4p}^{k}\Rightarrow p|C_{2012}^{k}$ 。
若 $p|k$，则只有下列五种情形：
$C_{4p}^{0}=C_{4p}^{4p}=1$，$C_{4p}^{p}=C_{4p}^{3p}=\frac{4p\cdot(4p-1)\cdot \cdots \cdot (3p+1)}{p\cdot (p-1)\cdot \cdots \cdot 1}\equiv4(\bmod p)$
$C_{4p}^{2p}=\frac{4p\cdot (4p-1)\cdot \cdots \cdot(3p+1)\cdot 3p\cdot (3p-1)\cdot \cdots \cdot (2p+1)}{2p\cdot (2p-1)\cdot \cdots\cdot (p+1)\cdot p\cdot (p-1)\cdot \cdots \cdot 1}\equiv 6(\bmod p)$
而这5个数都不是的倍数。
其次考虑组合数的奇偶性。
先考察的 $n$ 阶乘所含的2的方幂。假设 $n$ 的二进制表示为 $n={{({{a}_{r}}{{a}_{r-1}}\cdots{{a}_{1}}{{a}_{0}})}_{2}}$ 。则 $n$ 的阶乘中所含的2的方幂为
$\begin{align}
& \left[\frac{n}{2} \right]+\left[ \frac{n}{4} \right]+\cdots +\left[\frac{n}{{{2}^{m}}} \right]+\cdots ={{({{a}_{r}}{{a}_{r-1}}\cdots{{a}_{2}}{{a}_{1}})}_{2}}+{{({{a}_{r}}{{a}_{r-1}}\cdots {{a}_{3}}{{a}_{2}})}_{2}}+\cdots+{{a}_{r}} \\
& ={{a}_{r}}({{2}^{r}}-1)+{{a}_{r-1}}({{2}^{r-1}}-1)+\cdots+{{a}_{1}}({{2}^{1}}-1)+{{a}_{0}}({{2}^{0}}-1) \\
& =n-s(n)
\end{align}$，其中 $s(n)={{a}_{r}}+{{a}_{r-1}}+\cdots+{{a}_{0}}$ 表示的二进制数码之和，也就是1的个数。
若组合数 $C_{2012}^{k}=\frac{2012!}{k!\cdot(2012-k)!}=\frac{(k+m)!}{k!\cdot m!}(m=2012-k)$ 是奇数，则其分子和分母所含的2的方幂相同 $\Rightarrow k+m-s(k+m)=k-s(k)+m-s(m)\Rightarrow s(k+m)=s(k)+s(m)$，即 $k+m=2012$ 在二进制下的加法不进位（每进一次位意味着把某一位的 ${{(10)}_{2}}$ 变成了前一位的 ${{(1)}_{2}}$，数字和减少1）
注意到 $2012={{(11111011100)}_{2}}$，共有8个1和3个0构成。
若 $k+m={{(11111011100)}_{2}}$ 不进位，则在0的位上，$k,m$ 都必须是 $0(0=0+0)$，选择唯一；在1的位上，$k,m$ 一个是0一个是1，有两种选择。所以非负整数 $k+m=2012$ 二进制下不进位的情形共有 ${{2}^{8}}=256$ 种，即有256个组合数是奇数，剩下 $2013-256=1757$ 个是偶数。
再次，考虑组合数 $C_{2012}^{k}=\frac{2012!}{k!\cdot(2012-k)!}=\frac{(k+m)!}{k!\cdot m!}(m=2012-k)$ 是偶数，但不是4的倍数。此时，分子比分母所含有的2的方幂恰好多1．从而有 $s(k+m)=s(k)+s(m)-1$，也即在二进制下的加法有且只有一个进位，这个唯一的进位是相邻两项的后位进到前位。由于后位的后位没有向前进位，后位上发生的二进制加法一定是 ${{(1)}_{2}}+{{(1)}_{2}}={{(10)}_{2}}$（否则，无法向前进位），即 $k,m$ 在后位都是1。而前位接受了后位的进位，没有继续向前进位，只可能是 $0+0=0$，接受进位后变成1，即 $k,m$ 在前位上都是0．
进位的那两位的加法是 ${{(01)}_{2}}+{{(01)}_{2}}={{(10)}_{2}}$
从和的二进制表示 $k+m={{(11111011100)}_{2}}$ 来看，进位只可能是从前向后数第五、六位或者是第九、十为的10。无论如何，进位的前后两位固定了 ${{(01)}_{2}}+{{(01)}_{2}}={{(10)}_{2}}$ 。其余位置不进位，0的位只能是 $0+0=0$，1的位可以是 $1+0=1$ 或 $0+1=1$ 两种选择。两种位置的进位各有 ${{2}^{7}}=128$ 种情形，共 $256$ 种情形。也就是说，组合数中有 $256$ 个偶数但非 $4$ 的倍数。
这样组合数是 $4$ 的倍数的有 $2013-256-256=1501$ 个。
最后，考虑不是 $p=503$ 的倍数的情形。
$C_{4p}^{0}=C_{4p}^{4p}=1$ 不是4的倍数。
$C_{4p}^{p}=C_{4p}^{3p}$ 中2的方幂数是 $s(p)+s(3p)-s(4p)=s(3p)\geqslant 2$ 。
$C_{4p}^{2p}$ 中 $2$ 的方幂数是 $s(2p)+s(2p)-s(4p)=s(p)=s(2012)=8$ 。
这三个组合数都是 $4$ 的倍数，但不是 $p=503$ 的倍数。
所以既是 $4$ 的倍数又是的倍数的组合数有 $1501-3=1498$ 个。
综上，组合数是 $2012$ 的倍数的有 $1498$ 个。
首先考虑组合数 $C_{2012}^{k}$ 是否是 $p=503$ 的倍数。
若 $p\not{|}k$，由得，从而
$C_{2012}^{k}=C_{4p}^{k}=\frac{(4p)!}{k!\cdot(4p-k)!}=\frac{4p}{k}C_{4p-1}^{k-1}\Rightarrow p|kC_{4p}^{k}\Rightarrow p|C_{4p}^{k}\Rightarrow p|C_{2012}^{k}$ 。
若 $p|k$，则只有下列五种情形：
$C_{4p}^{0}=C_{4p}^{4p}=1$，$C_{4p}^{p}=C_{4p}^{3p}=\frac{4p\cdot(4p-1)\cdot \cdots \cdot (3p+1)}{p\cdot (p-1)\cdot \cdots \cdot 1}\equiv4(\bmod p)$
$C_{4p}^{2p}=\frac{4p\cdot (4p-1)\cdot \cdots \cdot(3p+1)\cdot 3p\cdot (3p-1)\cdot \cdots \cdot (2p+1)}{2p\cdot (2p-1)\cdot \cdots\cdot (p+1)\cdot p\cdot (p-1)\cdot \cdots \cdot 1}\equiv 6(\bmod p)$
而这5个数都不是的倍数。
其次考虑组合数的奇偶性。
先考察的 $n$ 阶乘所含的2的方幂。假设 $n$ 的二进制表示为 $n={{({{a}_{r}}{{a}_{r-1}}\cdots{{a}_{1}}{{a}_{0}})}_{2}}$ 。则 $n$ 的阶乘中所含的2的方幂为
$\begin{align}
& \left[\frac{n}{2} \right]+\left[ \frac{n}{4} \right]+\cdots +\left[\frac{n}{{{2}^{m}}} \right]+\cdots ={{({{a}_{r}}{{a}_{r-1}}\cdots{{a}_{2}}{{a}_{1}})}_{2}}+{{({{a}_{r}}{{a}_{r-1}}\cdots {{a}_{3}}{{a}_{2}})}_{2}}+\cdots+{{a}_{r}} \\
& ={{a}_{r}}({{2}^{r}}-1)+{{a}_{r-1}}({{2}^{r-1}}-1)+\cdots+{{a}_{1}}({{2}^{1}}-1)+{{a}_{0}}({{2}^{0}}-1) \\
& =n-s(n)
\end{align}$，其中 $s(n)={{a}_{r}}+{{a}_{r-1}}+\cdots+{{a}_{0}}$ 表示的二进制数码之和，也就是1的个数。
若组合数 $C_{2012}^{k}=\frac{2012!}{k!\cdot(2012-k)!}=\frac{(k+m)!}{k!\cdot m!}(m=2012-k)$ 是奇数，则其分子和分母所含的2的方幂相同 $\Rightarrow k+m-s(k+m)=k-s(k)+m-s(m)\Rightarrow s(k+m)=s(k)+s(m)$，即 $k+m=2012$ 在二进制下的加法不进位（每进一次位意味着把某一位的 ${{(10)}_{2}}$ 变成了前一位的 ${{(1)}_{2}}$，数字和减少1）
注意到 $2012={{(11111011100)}_{2}}$，共有8个1和3个0构成。
若 $k+m={{(11111011100)}_{2}}$ 不进位，则在0的位上，$k,m$ 都必须是 $0(0=0+0)$，选择唯一；在1的位上，$k,m$ 一个是0一个是1，有两种选择。所以非负整数 $k+m=2012$ 二进制下不进位的情形共有 ${{2}^{8}}=256$ 种，即有256个组合数是奇数，剩下 $2013-256=1757$ 个是偶数。
再次，考虑组合数 $C_{2012}^{k}=\frac{2012!}{k!\cdot(2012-k)!}=\frac{(k+m)!}{k!\cdot m!}(m=2012-k)$ 是偶数，但不是4的倍数。此时，分子比分母所含有的2的方幂恰好多1．从而有 $s(k+m)=s(k)+s(m)-1$，也即在二进制下的加法有且只有一个进位，这个唯一的进位是相邻两项的后位进到前位。由于后位的后位没有向前进位，后位上发生的二进制加法一定是 ${{(1)}_{2}}+{{(1)}_{2}}={{(10)}_{2}}$（否则，无法向前进位），即 $k,m$ 在后位都是1。而前位接受了后位的进位，没有继续向前进位，只可能是 $0+0=0$，接受进位后变成1，即 $k,m$ 在前位上都是0．
进位的那两位的加法是 ${{(01)}_{2}}+{{(01)}_{2}}={{(10)}_{2}}$
从和的二进制表示 $k+m={{(11111011100)}_{2}}$ 来看，进位只可能是从前向后数第五、六位或者是第九、十为的10。无论如何，进位的前后两位固定了 ${{(01)}_{2}}+{{(01)}_{2}}={{(10)}_{2}}$ 。其余位置不进位，0的位只能是 $0+0=0$，1的位可以是 $1+0=1$ 或 $0+1=1$ 两种选择。两种位置的进位各有 ${{2}^{7}}=128$ 种情形，共 $256$ 种情形。也就是说，组合数中有 $256$ 个偶数但非 $4$ 的倍数。
这样组合数是 $4$ 的倍数的有 $2013-256-256=1501$ 个。
最后，考虑不是 $p=503$ 的倍数的情形。
$C_{4p}^{0}=C_{4p}^{4p}=1$ 不是4的倍数。
$C_{4p}^{p}=C_{4p}^{3p}$ 中2的方幂数是 $s(p)+s(3p)-s(4p)=s(3p)\geqslant 2$ 。
$C_{4p}^{2p}$ 中 $2$ 的方幂数是 $s(2p)+s(2p)-s(4p)=s(p)=s(2012)=8$ 。
这三个组合数都是 $4$ 的倍数，但不是 $p=503$ 的倍数。
所以既是 $4$ 的倍数又是的倍数的组合数有 $1501-3=1498$ 个。
综上，组合数是 $2012$ 的倍数的有 $1498$ 个。
答案
解析
备注
