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

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.