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\)。