UyHiP 2016 Feb Riddle

……很久没更新了，随手更一发 →_→ 这次选取的题是 UyHiP 2016 Feb 的题，然而我并不会做。

Problem

给定一个 \(n\) 维的 0/1 cube，要求找若干个不过原点的超平面，使得这些超平面能够覆盖除了原点以外任意 \(\{0, 1\}^n\) 的整点。求至少要多少个超平面。

Solution

不妨设 \(k\) 个超平面能满足要求。考虑一个超平面，其方程为 \(\mathbf{w}^T\mathbf{x} + b = 0\)。则所有被这 \(k\) 个超平面覆盖的点即为满足 \[ f(\mathbf{x}) = \prod_{i=1}^k \left( \mathbf{w}_i^T \mathbf{x} + b_i \right ) = 0 \] 的所有点。

我们把 \(f(\mathbf{x})\) 展开，写成一个关于 \(\textbf{x} = x_{1, 2, \dots, n}\) 的多项式。如果我们只关注 \(\{0, 1\}^n\) 上面的点的话，可以发现 \(x_i^t = x_i\) 。这关键的一步成为 Arithmetical method，还记得 TQBF 是 PSPACE-complete 的证明的同学应该知道这货。于是我们可以把 \(f(\mathbf{x})\) 化简为 \[f(\mathbf{x}) = \sum_{S \in [n]} c_S \prod_{i \in S} x_i,\] 其中 \(c_S\) 为对应的系数。注意到 \(f(\mathbf{0}) \neq 0\)，故 \(c_\emptyset \neq 0\)。不妨把 \(f(\mathbf{x})\) 的常数项归一化，则我们有 \(2^{n}-1\) 个未知的 \(c_S\)，另外由于除原点以外的其余所有点都有 \(f(\mathbf{x}) = 0\)，我们还可以列出 \(2^n - 1\) 个方程，且这些方程之间是线性无关的（原因请自行思考）。故 \(c_S\) 的解是唯一的。又有 \[\prod_{i=1}^n (1 - x_i)\] 能满足要求，故有 \[c_S = (-1)^{|S|}c_\emptyset \neq 0.\]

注意到 \(f(\mathbf{x})\) 的每个单项式至多包含 \(k\) 个不同的 \(x_i\) ，但是算术化之后的 \(f(\mathbf{x})\) 却有一项 \(x_1 x_2 \cdots x_n\) ，所以我们有 \(k \geq n\)。

找出 \(n\) 个超平面满足给定条件是很简单的事，例如 \(\forall i \in [n], x_i = 1\) 或者 \(\forall t \in [n], \sum x_i = t\) 。