设 $x_{i} \in\{0,1\}(i=1,2, \cdots, n)$,若函数 $f=f\left(x_{1}, x_{2}, \cdots, x_{n}\right)$ 的值只取 $0$ 或 $1$,则称 $f$ 是一个 $n$ 元布尔函数,并记 $D_{n}(f)=\left\{\left(x_{1}, x_{2}, \dots\right.\right.x_{n} ) | f\left(x_{1}, x_{2}, \cdots, x_{n}\right)=0 \}$.
(1)求 $n$ 元布尔函数的个数;
(2)设 $g$ 是 $n$ 元布尔函数,满足 $\begin{aligned} g\left(x_{1}, x_{2}, \cdots, x_{10}\right) \equiv 1+x_{1}+x_{1} x_{2}+x_{1} x_{2} x_{3}+\cdots+x_{1} x_{2} \cdots x_{n}(\bmod 2) \end{aligned}$
求集合 $D_{10}(g)$ 的元素个数,并求 最大的正整数 $n$,使得 $\displaystyle \sum\limits_{\left(x_{1}, \cdots, x_{n}\right) \in D_{n}(g)}\left(x_{1}+x_{2}+\cdots+x_{n}\right)\leqslant 2017$.
【难度】
【出处】
2017中国东南数学奥林匹克试题(高二)
【标注】
  • 知识点
    >
    二试组合部分
【答案】
【解析】
证法一
(1)$x_{1}, x_{2}, \cdots, x_{n}$ 的所有可能的取值共有 $2^n$ 个,每个对应的函数值都有 $0$ 或 $1$ 两个,故所有不同的 $n$ 元布尔函数的个数为 $2^{2^n}$ 个.
(2)记 $\left|D_{n}(g)\right|$ 表示集合 $D_{n}(g)$ 中元素的个数,显然有 $|D_1(g)|=1,|D_2(g)=1|$,再由
$\begin{aligned} g\left(x_{1}, x_{2}, \cdots, x_{n}\right) & \equiv 1+x_{1}+x_{1} x_{2}+x_{1} x_{2} x_{3}+\cdots+x_{1} x_{2} \cdots x_{n}(\bmod 2) \\ &=\left(1+x_{1}\left(1+x_{2}+x_{2} x_{3}+\cdots+x_{2} x_{3} \cdots x_{n}\right)\right)(\bmod 2) \end{aligned}$
所以 $\left|D_{n}(g)\right|=2^{n-1}-\left|D_{n-1}(g)\right|, n=3,4, \cdots$,即
$\begin{aligned}\left|D_{n}(g)\right| &=2^{n-1}-2^{n-2}+\left|D_{n-2}(g)\right|=\cdots \\ &=2^{n-1}-2^{n-2}+2^{n-3}+\cdots+(-1)^{n-2} 2+(-1)^{n-1} \end{aligned}$
从而有 $\left|D_{n}(g)\right|=\dfrac{2^{n}+(-1)^{n+1}}{3}, n=1,2, \cdots$,
所以集合 $D_n(g)$ 的元素个数为 $\dfrac{2^{n}+(-1)^{n+1}}{3}$.
记 $c_{n}=\sum_{\left(x_{1}, x_{2}, \cdots, x_{n}\right) \in D_{n}(g)}\left(x_{1}+x_{2}+\cdots+x_{n}\right)$,由 $\begin{aligned} g\left(x_{1}, x_{2}, \cdots, x_{n-1}, 0\right) \equiv 1+x_{1}+x_{1} x_{2}+x_{1} x_{2} x_{3}+\cdots+x_{1} x_{2} \cdots x_{n-1}(\bmod 2) \end{aligned}$,及 $\begin{aligned} g\left(x_{1}, x_{2}, \cdots, x_{n-1}, 1\right) = 1+x_{1}+x_{1} x_{2}+x_{1} x_{2} x_{3}+\cdots+x_{1} x_{2} \cdots x_{n-1}+x_{1} x_{2} \cdots x_{n-1}(\bmod 2) \end{aligned}$,
如果 $x_{1} x_{2} \cdots x_{n-1}=1$,则
$g\left(x_{1}, x_{2}, \cdots, x_{n-1}, 1\right) \equiv(n+1)(\bmod 2)=\begin{cases}0, & n为奇数 \\ 1, & n为偶数\end{cases}$
如果 $x_{1} x_{2} \cdots x_{n-1}=0$,则
$\begin{aligned} & g\left(x_{1}, x_{2}, \cdots, x_{n-1}, 1\right) \\ \equiv & 1+x_{1}+x_{1} x_{2}+x_{1} x_{2} x_{3}+\cdots+x_{1} x_{2} \cdots x_{n-1}(\bmod 2)=0 \end{aligned}$
等价于
$\begin{aligned} & g\left(x_{1}, x_{2}, \cdots, x_{n-1}\right) \\ \equiv & 1+x_{1}+x_{1} x_{2}+x_{1} x_{2} x_{3}+\cdots+x_{1} x_{2} \cdots x_{n-1}(\bmod 2)=0 \end{aligned}$
因此可得当 $n\geqslant 2$ 时有
$c_{n}=\begin{cases}n+2 c_{n-1}+\left|D_{n-1}(g)\right|, & n为奇数 \\ 2 c_{m-1}+\left|D_{n-1}(g)\right|-n, & n为偶数\end{cases}$
显然 $c_{1}=1, c_{2}=1$.
当 $n=2m$ 为偶数时,有
$\begin{aligned} c_{2 m} &=2 c_{2 m-1}+\frac{2^{2 m-1}+(-1)^{2 m}}{3}-2 m \\ &=-\frac{1}{3}+\frac{4}{3} \cdot 2^{2 m-2}+(2 m-2)+4 c_{2m-2} \\ &=\frac{(3 m+1) 4^{m}-(6 m+1)}{9} \end{aligned}$
即 $c_{2 m}=\dfrac{(3 m+1) 4^{m}-(6 m+1)}{9}, m=1,2,3, \cdots$ ①
同理,当 $ n = 2m+1$ 为奇数时,有
$\begin{aligned} c_{2 m+1} &=2 m+1+2 c_{2 m}+\frac{2^{2 m}+(-1)^{2 m+1}}{3} \\ &=\frac{1}{3}+\frac{4}{3} \cdot 2^{2 m-1}-(2 m-1)+4 c_{2 m-1} \\ &=\frac{(6 m+5) 4^{m}+6 m+4}{9} \end{aligned}$
即 $c_{2 m+1}=\frac{(6 m+5) 4^{m}+6 m+4}{9}, m=0,1,2, \cdots$ ②
因此由 ①、②,以及 $c_{9}=828<3986=c_{11}, c_{10}=1817<8643=c_{12}$,可知使得 $\displaystyle \sum\limits_{\left(x_{1}, x_{2}, \cdots, x_{n}\right) \in D_{2}(g)}\left(x_{1}+x_{2}+\cdots+x_{n}\right) \leqslant 2017$ 成立的最大正整数 $n=10$.
证法二
(1)同证法一.
(2)记 $|D_n(g)|$ 表示集合 $|D_n(g)|$ 中元素的个数,下面用 $*$ 表示可以取 $0$ 或 $1$,因此
当 $n=2m$ 时为偶数时,有
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,0, *, *, \cdots, *)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$,共有 $2^{2 m-2}$ 个;
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,1,1,0, *, *, *, *)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$,共有 $2^{2 m-4}$ 个;
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,1,1,1,1,0, *, *, *, *)$ 时;$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$,共有 $2^{2 m-6}$ 个;
$\cdots\cdots$
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,1, \cdots, 1,0, *, *)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$,共有 $2^2$ 个;
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,1, \cdots, 1,0)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$,共有 $1$ 个;
所以集合 $ D_{2m}(g)$ 的元素个数为:$\left|D_{2 m}(g)\right|=2^{2 m-2}+2^{2 m-4}+\cdots+2^{2}+1=\dfrac{2^{2 m}-1}{3}$.
同理,当 $n=2 m+1$ 为奇数时,集合 $D_{2 m+1}(g)$ 的元素个数为:$\left|D_{2 m+1}(g)\right|=2^{2 m-1}+2^{2 m-3}+\cdots+2^{1}+1=\dfrac{2^{2 m+1}+1}{3}$.
综合可得集合 $D_{n}(g)$ 的元素个数为:$\dfrac{2^{n}+(-1)^{n+1}}{3}, n=1,2, \cdots$.
记 $\displaystyle c_{n}=\sum\limits_{\left(x_{1}, x_{2}, \ldots, x_{n}\right) \in D_n(g)}\left(x_{1}+x_{2}+\cdots+x_{n}\right)$
当 $n=2m$ 为偶数时,有
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,0, *, *, \cdots, *)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right )=0$ 的所有解中 $1$ 的个数共有 $1 \times 2^{2 m-2}+2^{2 m-3} \times(2 m-2)=m \times 2^{2 m-2}$ 个;
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,1,1,0, *, *, *, *)$ 时,$g\left(x_{1}, x_{2}, \cdots,x_{2 m} \right)=0$ 的所有解中 $1$ 的个数共有 $3 \times 2^{2 m-4}+2^{2 m-5} \times(2 m-4)=(m+1) \times 2^{2 m-4}$ 个.
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,1,1,1,1,0, *, *, *, *)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$ 的所有解中 $1$ 的个数共有 $5 \times 2^{2 m-6}+2^{2 m-7} \times(2 m-6)=(m+2) \times 2^{2 m-6}$ 个;
$\cdots\cdots$
当 $\left(x_{1}, x_{2}, \cdots, x_{2m}\right)=(1,1, \cdots, 1,0, *, *)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$ 的所有解中 $1$ 的个数共有 $(2 m-3) \times 2^{2}+2 \times 2=(m+(m-2)) \times 2^{2}$ 个;
当 $\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=(1,1, \cdots, 1,0)$ 时,$g\left(x_{1}, x_{2}, \cdots, x_{2 m}\right)=0$ 的所有解中 $1$ 的个数共有 $(2 m-1) \times 1$ 个;
所以
$\displaystyle \begin{aligned} c_{2m}&=\sum\limits_{(x_1,x_2,\cdots,x_{2m})\in D_{2m}(g)}(x_1+x_2+\cdots+x_{2m})\\&= m \times 2^{2 n n-2}+(m+1) \times 2^{2 m-4}+(m+2) \times 2^{2 m-6}+\cdots +(m+m-2) \times 2^{2}+2 m-1 \\&= \frac{(3 m+1) 4^{m}-(6 m+1)}{9} \end{aligned}$
同理,当 $n= 2m+1$ 为奇数时,有
$\displaystyle \begin{aligned} c_{2m+1}&=\sum\limits_{(x_1,x_2,\cdots,x_{2m+1})\in D_{2m+1}(g)}(x_1+x_2+\cdots+x_{2m+1})
\\=&(2 m+1) \times 2^{2 m-2}+(2 m+3) \times 2^{2 m-4}+(2 m+5) \times 2^{2 n-6}+\cdots+(2 m+2 m-1) \times 2^{0}+2 m+1 \\=& \frac{(6 m+5) 4^{m}+6 m+4}{9} \end{aligned}$
因此由 ③,④,以及 $c_{9}=828<3986=c_{11}, c_{10}=1817<8643=c_{12}$,可知使得使得 $\displaystyle \sum\limits_{\left(x_{1}, \cdots, x_{n}\right) \in D_{n}(g)}\left(x_{1}+x_{2}+\cdots+x_{n}\right)\leqslant 2017$ 成立的最大正整数 $n=10$.
答案 解析 备注
0.111127s