Phantom Bird

外观

十万个冷笑话·其二 / 星轨 / FFMP 20250831

约 755 字大约 3 分钟

2025-8-31

“可恶的星穹列车，不许发车——”看着他创造铁墓的计划失败，来古士气急败坏地喊道。

宇宙本来是一个的 n×nn \times n 的网格图 GG，每个格点上有一个星系，每条边代表着一条跃迁航路。现在，来古士要把重构群星。具体而言，来古士会给每个星系一个 1∼n21 \sim n^2 的标号，然后选择一个 1∼n21 \sim n^2 的排列 pp，然后把星系 ii 移到 pip_i 处。由于开拓的奇妙设定，跃迁航路将会跟随星系的移动而移动。

星系移动结束之后，相邻的星系之间会新增一条直接航路。对于一条跃迁路径（指一个点列，满足相邻两点之间都有一条跃迁航路），定义它的混乱度为依次经过所有点所需要经过的直接航路数量与需要经过的跃迁航路的数量的比值。

来古士将各条跃迁路径混乱度的最小值称为宇宙的混乱度。对于每个 nn，试求混乱度的最大值。

形式化题面

有一个 n×nn \times n 的网格图 GG，对于所有排列 p:V→Vp: V \to V，求 min⁡(u,v)∈Edis⁡(p(u),p(v))\min_{(u,v) \in E} \operatorname{dis}(p(u), p(v)) 的最大值。

答案

n−1n - 1

证明：

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

ans=min⁡u∈Vmin⁡v∈N(u)dis(p(u),p(v))≤min⁡u∈Vkth-max⁡v′∈V(N(u))dis(p(u),v′)≤min⁡u∈V2nd-max⁡v′∈Vdis(p(u),v′)=min⁡u′∈V2nd-max⁡v′∈Vdis(u′,v′)\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*}

若 nn 为偶数 2m2m

ans≤2nd-max⁡v′∈Vdis⁡((m,m),v′)=dis⁡((m,m),(0,1))=2m−1.\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)↦(((m−1)x+my) mod n,(mx+(m−1)y) mod n)p: (x, y) \mapsto \Bigl( \bigl( (m-1)x+my \bigr) \bmod n, \bigl( mx+(m-1)y \bigr) \bmod n \Bigr)

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

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

dis⁡(p((x,y)),p(x,y+1)),dis⁡(p((x+1,y)),p(x,y))≥min⁡{m mod n,(−m) mod n}+min⁡{(m−1) mod n,(1−m) mod n}=min⁡{m,m}+min⁡{m−1,m+1}=2m−1\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*}

可以取到这个上界。

若 nn 为奇数 2m+12m+1

ans≤2nd-max⁡v′∈Vdis⁡((m,m),v′)=dis⁡((m,m),(0,0))=2m.\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)↦((mx+my) mod n,(mx+(m+1)y) mod n)p: (x, y) \mapsto \Bigl( \bigl( mx+my \bigr) \bmod n, \bigl( mx+(m+1)y \bigr) \bmod n \Bigr)

存在逆映射

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

因此是一个排列。

另一方面，

dis⁡(p((x,y)),p(x,y+1)),dis⁡(p((x+1,y)),p(x,y))≥min⁡{m,m+1}+min⁡{m,m+1}=2m\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*}

因此可以取到。

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)