0%

TOAD-puzzle-13

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

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.