……很久没更新了，随手更一发 →_→ 这次选取的题是 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$ 。