0%

组合趣题合集

7.15

一列

题面

设有 \(2^{n-1}\) 个不同的数列,每个数列有 \(n\) 项,每项都等于 \(0\)\(1\)。已知,对于这些数列任意 \(3\)个数列,都存在正整数 \(p\),使得这 \(3\) 个数列的第 \(p\) 项都为 \(1\),证明存在唯一的正整数 \(k\),使得对所有 \(2^{n-1}\) 个数列的第 \(k\) 项都等于 \(1\) #### 题解

\(S\) 为这 \(2^{n-1}\) 个不同序列构成的集合,那么 \(S\subseteq \lbrace0,1\rbrace^n\),定义元素之间的按位与运算 \(\circ\),和按位取反运算 \(\overline{\mathrm{x}}\)

首先证明 \((0,0,\dotsc,0)\notin S\),否则任取其余两个元素 \(\mathrm{x}\)\(\mathrm{y}\),则 \(\mathrm{x}\circ\mathrm{y}\circ\mathrm{0}=\mathrm{0}\)

再证明若 \(\mathrm{x}\),则 \(\overline{\mathrm{x}}\notin S\),否则取 \(\mathrm{x}\circ\overline{\mathrm{x}}\circ\mathrm{y}=\mathrm{0}\),矛盾。得到推论 \((\mathrm{x},\overline{\mathrm{x}})\) 必有其一 \(\in S\),否则不足 \(2^{n-1}\) 个;

最后证明,若 \(\mathrm{x},\mathrm{y}\in S\),则 \(\mathrm{x}\circ\mathrm{y}\in S\),否则 \(\overline{\mathrm{x}\circ\mathrm{y}}\in S\),则 \(x\circ y\circ \overline{\mathrm{x}\circ\mathrm{y}}=\mathrm{0}\) 矛盾。

所以 \(\bigcirc_{\mathrm{x}\in S}\mathrm{x}\) 不为 \(\mathrm{0}\),若有 \(k\) 个位置为 \(1\),则 \(|S|\) 最大只能为 \(2^{n-k}\),故 \(k\) 只能为 \(1\)