查看源代码：
unnamed-problem-solution.md

---
title: 一个未命名问题的解答
createTime: 2025/8/31
categories:
    - study
tags:
    - maths
    - FFMP
---

:::note 问题
有一个 $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*}
$$
因此可以取到。