TOAD 13 - The Voting Problem

今天的题非常漂亮，但是证明实在是不忍直视。这题解写的是有多蛋疼啊 →_→

Problem

有一个 \(n\) 元函数 \(f(x_1, x_2, \dots, x_n)\) ，其中每个参数的定义域以及函数的值域均为 \(\{0, 1, 2\}\) 。且 \(f\) 满足，若 \(x_1 \neq y_1, x_2 \neq y_2, \dots, x_n \neq y_n\) ，则 \(f(x_1, x_2, \dots, x_n) \leq f(y_1, y_2, \dots, y_n)\) 。

是否对于每个满足条件的 \(f\) ，都存在一个 \(j\) ，使得 \(f\) 的函数值只与第 \(j\) 个参数相关？

Solution

还真就是的。尽管我第一反应还不相信 →_→

我这证明真心不敢恭维。如果你没看懂的话，这里 是原题 solution 。如果还是没看懂的话，那就算了吧。我觉得这个结论比证明漂亮多了 →_→

下文中为了叙述简洁，我直接用 \(\vec{x}\) 表示依次填入 \(x_1, x_2, \dots, x_n\) ，即 \(f(\vec{x})\) 等价于 \(f(x_1, x_2, \dots, x_n)\) 。

对于 \(n\) 使用数学归纳法。

当 \(n = 1\) 时，结论显然正确。

当 \(n\) 时成立，我们要证明 \(n + 1\) 时也成立。考虑是否存在一个 \(n\) 维向量 \(\vec{x}\) ，使得对于任意的 \(1 \leq i \leq 3\) ，会产生 3 个不同的 \(f(\vec{x}, i)\) 。

如果存在这么一组 \(x\) ，则再考虑另一组 \(n\) 维向量 \(\vec{y}\) 满足 \(\forall 1 \leq i \leq n, x_i \neq y_i\) 。对于任意 \(1 \leq i \leq 3, 1 \leq j \leq 3, i \neq j\) ，我们均有 \(f(\vec{x}, i) \neq f(\vec{y}, j)\) ，如果固定 \(j\) 枚举 \(i\) ，则 \(f(\vec{x}, i)\) 会取遍其余 2 个数，可知 \(f(\vec{x}, j) = f(\vec{y}, j)\) 。这样我们发现 \(f\) 的值与前 \(n\) 个数是无关的，只与第 \(n + 1\) 个参数相关，结论成立。

如果不存在，则对于每个 \(n\) 维向量 \(\vec{x}\) ，均存在一对 \(i, j\) 满足 \(f(\vec{x}, i) = f(\vec{x}, j)\) 。我们定义 \(g(\vec{x})\) 表示其中一个 \(f(\vec{x}, i)\) （即 \(g(\vec{x})\) 有若干种可能的取值）。现在我们要证明 令 \(g'(\vec{x})\) 是 \(n\) 时的一个满足要求的 \(f\) 。

注意到，对于两个完全不同的向量 \(\vec{x}, \vec{y}\) ，我们有 \(f(\vec{x}, i) = f(\vec{x}, j)\) ，且存在 \(m \neq i\) 或 \(m \neq j\) 使得 \(f(\vec{y}, m) = g(\vec{x})\) 。不妨设 \(m \neq j\) 。我们有 \(f(\vec{x}, i) \neq f(\vec{y}, m)\) ，即 \(g(\vec{x}) \neq g(\vec{y})\) 。

对于 \(n\) 个元素来说， \(g\) 是一个满足要求的函数。同样原理，我们可以把 \(g(\vec{x})\) 其中一个函数值作小小的修改，即 \[g'(\vec{x}) = \begin{cases} g(\vec{x}) & \textnormal{if} \vec{x} \neq \vec{z} \ f(\vec{z}, k) & \textnormal{otherwise} \end{cases}\] 这个函数仍然满足要求。

由归纳法知， \(g'\) 的函数值只与其中一个参数相关，则易知所有可能的 \(g'\) 都是一样的。这表示对于任意一个 \(i\) ， \(f(\vec{x}, i)\) 只与 \(\vec{x}\) 相关。Q.E.D.