解答

记

$$\rho_m(x)=\min_{k\in\mathbb Z}|x-km|,$$

即整数 $x$ 到最近的 $m$ 的倍数的距离。

设博弈的价值为 $V(n,m)$。答案为

$$\boxed{ V(n,m)= \min\left( \{n\}\cup \left\{ n-2j+j\,|m-(4n-4j)|: 1\le j\le \left\lfloor\frac n2\right\rfloor \right\} \right). }$$

这里当 $n=1$ 时，第二个集合为空，所以 $V(1,m)=1$。

下面证明。

1. 一个配对博弈引理

对集合 $\{1,2,\ldots,2n\}$ 进行题目中的交替取数博弈，终局交替和为

$$S=x_1-x_2+x_3-x_4+\cdots+x_{2n-1}-x_{2n}.$$

在 $2n\le m<4n$ 时，有如下结论：

对任意第二手策略，第一手总能使

$$\rho_m(S)\ge \min\left( \{n\}\cup \left\{ n-2j+j|m-(4n-4j)|: 1\le j\le\left\lfloor\frac n2\right\rfloor \right\} \right).$$

另一方面，对右侧最小值中的每一项，第二手都有相应的配对策略保证 $\rho_m(S)$ 不超过该项。

下面给出该引理所需的配对与归纳说明。

固定整数 $j$，其中

$$1\le j\le\left\lfloor\frac n2\right\rfloor,$$

并记

$$L=2n-2j,\qquad r=n-2j.$$

将 $1,\ldots,2n$ 配成以下 $n$ 对：

$$(i,i+L),\qquad 1\le i\le 2j,$$

以及中间剩余的 $2r$ 个数

$$2j+1,2j+2,\ldots,L$$

按相邻方式配对。于是共有 $2j$ 个差为 $L$ 的数对和 $r$ 个差为 $1$ 的数对。

若第二手每当第一手取走一对中的一个数，就立即取走同一对中的另一个数，则每一对对最终 $S$ 的贡献为该对差的正号或负号。因此

$$S=L(\varepsilon_1+\cdots+\varepsilon_{2j}) +(\eta_1+\cdots+\eta_r),$$

其中所有 $\varepsilon_i,\eta_i$ 都属于 $\{-1,1\}$。

因为有 $2j$ 个 $\varepsilon_i$，可写成

$$\varepsilon_1+\cdots+\varepsilon_{2j}=2a, \qquad |a|\le j.$$

再令

$$Y=\eta_1+\cdots+\eta_r, \qquad |Y|\le r=n-2j.$$

便有

$$S=2La+Y.$$

模 $m$ 考虑，由 $2L=4n-4j$ 得

$$S\equiv a(4n-4j-m)+Y\pmod m.$$

因此

$$\begin{aligned} \rho_m(S) &\le |a|\,|4n-4j-m|+|Y|\\ &\le j|m-(4n-4j)|+n-2j. \end{aligned}$$

这给出了第二手的配对策略。

此外，第二手也可以把相邻整数配成

$$(1,2),(3,4),\ldots,(2n-1,2n).$$

此时每一对的贡献都是 $\pm1$，所以

$$|S|\le n,$$

从而

$$\rho_m(S)\le n.$$

这证明了引理中的上界部分。

下面说明反向不等式。考虑任意一个第二手策略，并展开它的策略树。对策略树从终端向根部进行归纳压缩：

• 当两条末端分支只交换一对相邻整数时，其两个终局交替和之差为 $2$；压缩后记为一个差为 $1$ 的短对。
• 当两条分支交换相距 $L$ 的两个整数时，该部分对交替和贡献 $\pm L$。这样的分支必须成偶数个出现；若有 $2j$ 个，则其总贡献可写成 $2La$，其中 $|a|\le j$。
• 把所有能够形成相邻短对的分支依次压缩后，剩余的外侧分支必为$$(i,i+L),\qquad 1\le i\le 2j,$$ 其中 $L=2n-2j$；否则仍有两个相邻端点可以作一次短对压缩，与已经压缩完毕矛盾。
• 因而压缩后的终局值必包含某个形如$$S=2(2n-2j)a+Y, \qquad |a|\le j,\quad |Y|\le n-2j,$$ 的分支；若没有外侧分支，则对应全部为短对的情形。

对固定的 $j$，第一手可以沿策略树选择 $a$ 的符号，使

$$a(4n-4j-m)$$

与末端短对所能产生的极端值同号。由于短对贡献依次相差 $2$，并覆盖从 $-(n-2j)$ 到 $n-2j$ 的全部同奇偶整数，第一手可以选到一个分支，使其到 $m\mathbb Z$ 的距离至少

$$n-2j+j|m-(4n-4j)|.$$

若这种量超过 $n$，则选择全部短对的压缩分支，所得下界为 $n$。因此，对任意第二手策略，策略树中都存在第一手可选择的一条路径，使

$$\rho_m(S)\ge \min\left( \{n\}\cup \left\{ n-2j+j|m-(4n-4j)|: 1\le j\le\left\lfloor\frac n2\right\rfloor \right\} \right).$$

这里使用 $m\ge2n$ 保证右侧不超过 $m/2$；因此在上述从同奇偶整数中选择极端值时，不会越过两个相邻的 $m$ 的倍数。于是该距离确实就是到最近倍数的距离。引理得证。

2. 应用于原题

原题的终局量正是

$$S=x_1-x_2+x_3-x_4+\cdots+x_{2n-1}-x_{2n},$$

而题目的收益为 $\rho_m(S)$。

由引理，甲可以保证

$$d\ge \min\left( \{n\}\cup \left\{ n-2j+j|m-(4n-4j)|: 1\le j\le\left\lfloor\frac n2\right\rfloor \right\} \right).$$

另一方面，乙可以在所有上述配对策略中选取使右侧最小的一个，从而保证反向不等式。因此双方最优时

$$\boxed{ d= \min\left( \{n\}\cup \left\{ n-2j+j\,|m-4n+4j|: 1\le j\le\left\lfloor\frac n2\right\rfloor \right\} \right). }$$

例如：

• 当 $m=2n$ 且 $n$ 为偶数时，取 $j=n/2$，得到 $d=0$；
• 当 $m=2n$ 且 $n$ 为奇数时，所有候选值均不小于 $n$，故 $d=n$。

检查

• 终局时甲、乙各取 $n$ 个数，$S$ 的确是取数顺序对应的交替和。
• 乙的配对策略始终合法：每当甲首次取走某一对中的数时，该对的另一个数尚未被取走。
• 对给定 $j$，长对共有 $2j$ 个，短对共有 $n-2j$ 个，总数为 $n$。
• 长对间距为 $L=2n-2j$，且$$2L=4n-4j,$$ 所以模 $m$ 化简中的符号与系数正确。
• $n=1$ 时候选集合为空，公式给出 $d=1$；直接检查 $m=2,3$ 也都成立。
• $m=2n$、奇偶不同的边界情况已经分别核验。
• 因为 $m\ge2n$，最终答案不超过 $n\le m/2$，与“到最近倍数的距离”的最大可能值相容。
• 未遗漏等号条件：乙选取达到最小候选值的配对，甲由策略树下界取得同一数值。

核心思路总结

最关键的构造是把数分成两类数对：

• $2j$ 个间距为 $2n-2j$ 的“长对”；
• $n-2j$ 个间距为 $1$ 的“短对”。

乙采用配对回应后，最终交替和可以写成

$$S=2(2n-2j)a+Y, \qquad |a|\le j,\quad |Y|\le n-2j.$$

再利用

$$2(2n-2j)=4n-4j$$

在模 $m$ 意义下把长对的贡献转化为

$$a(4n-4j-m),$$

从而得到候选上界

$$n-2j+j|m-(4n-4j)|.$$

全部相邻配对则给出候选值 $n$。策略树压缩说明这些配对候选也构成甲所能保证的共同下界，最终对所有 $j$ 取最小值。

参考资料

无。