问题

有一个 $n \times n$ 的网格图 $G$，对于所有排列 $p: V \to V$，求 $\min_{(u,v) \in E} \operatorname{dis}(p(u), p(v))$ 的最大值。

答案

$$n - 1$$

证明

用 $\{0, 1, \dots, n-1\}^2$ 表示结点。定义 $\operatorname{kth-max}^{(k)}$ 为取第 $k$ 大符号，有

$$\begin{align*} \text{ans} &= \min_{u \in V} \min_{v \in N(u)} \mathrm{dis}(p(u), p(v)) \\ &\le \min_{u \in V} \underset{v' \in V}{\operatorname{kth-max}}^{(N(u))} \mathrm{dis}(p(u), v') \\ &\le \min_{u \in V} \operatornamewithlimits{2nd-max}_{v' \in V} \mathrm{dis}(p(u), v') \\ &= \min_{u' \in V} \operatornamewithlimits{2nd-max}_{v' \in V} \mathrm{dis}(u', v') \\ \end{align*}$$

若 n 为偶数 2m

$$\text{ans} \le \operatornamewithlimits{2nd-max}\limits_{v' \in V} \operatorname{dis}((m,m), v') = \operatorname{dis}((m,m),(0,1)) = 2m-1.$$

下证这个上界能取到。注意到映射

$$p: (x, y) \mapsto \Bigl( \bigl( (m-1)x+my \bigr) \bmod n, \bigl( mx+(m-1)y \bigr) \bmod n \Bigr)$$

存在逆映射（实际上不难验证 $p$ 是自逆的），因此它是一个排列。

另一方面，由于 $|a \bmod n - (a+d) \bmod n| \ge \min\{d \bmod n, (-d) \bmod n\}$，我们有

$$\begin{align*} &\operatorname{dis}(p((x,y)), p(x,y+1)), \operatorname{dis}(p((x+1,y)), p(x,y)) \\ \ge& \min\{m \bmod n, (-m) \bmod n\} + \min\{(m-1) \bmod n, (1-m) \bmod n\} \\ =& \min\{m, m\} + \min\{m-1, m+1\} = 2m-1 \end{align*}$$

可以取到这个上界。

若 n 为奇数 2m+1

$$\text{ans} \le \operatornamewithlimits{2nd-max}\limits_{v' \in V} \operatorname{dis}((m,m), v') = \operatorname{dis}((m,m),(0,0)) = 2m.$$

下证这个上界能取到。注意到映射

$$p: (x, y) \mapsto \Bigl( \bigl( mx+my \bigr) \bmod n, \bigl( mx+(m+1)y \bigr) \bmod n \Bigr)$$

存在逆映射

$$p^{-1}: (x, y) \mapsto \Bigl( (-y-x) \bmod n, (y-x) \bmod n \Bigr)$$

因此是一个排列。

另一方面，

$$\begin{align*} \operatorname{dis}(p((x,y)), p(x,y+1)), \operatorname{dis}(p((x+1,y)), p(x,y)) &\ge \min\{m, m+1\} + \min\{m, m+1\} = 2m \\ \end{align*}$$

因此可以取到。