Phantom Bird

外观

注意力测试 Ⅲ P4 解答

约 1151 字大约 4 分钟

mathsFFMP

2026-4-4

传统的五子棋/就是把五个子连成一条线/好无趣/好无聊; 而数学五子棋/就是在传统的五子棋/加入数学/好好玩. 要爆啦!

问题

设 n,mn,m 为满足 1≤m≤n1 \le m \le n 的正整数. F 和 T 正在一个平面直角坐标系中下棋, 规则如下:

  • 棋盘由点集 S={(x,y)∣x,y∈{1,2,…,n}}S = \bigl\{ (x,y) \mid x,y\in\{1,2,\dots,n\} \bigr\} 构成.
  • F 与 T 轮流行动, F 先手.
  • 每一步, 当前玩家挑选一个未被占据的点 P∈SP \in S, 并将其标记为自己的棋子.
  • 若某一方落子之后, 存在 mm 个属于这一方的不同棋子 P1,P2,…,PmP_1, P_2, \dots, P_m 满足 P1,P2,…,PiP_1, P_2, \dots, P_i 在同一直线上, 且 ∀i∈{1,2,…,m−1},∣PiPi+1∣≤2\forall i\in\{1,2,\dots,m-1\}, \left|P_iP_{i+1}\right| \le \sqrt{2}, 则这一方获胜.
  • 若 SS 中的所有点都被占据, 且没有任何一方获胜, 则为平局.

记 T(n,m)={1,F 有必胜策略−1,T 有必胜策略0,双方均无必胜策略T(n,m) = \begin{cases} 1, & \text{F 有必胜策略} \\ -1, & \text{T 有必胜策略} \\ 0, & \text{双方均无必胜策略} \end{cases}, 证明:

(1) T(n,m)≥0T(n,m) \ge 0;

(2) 存在数列 {ti}\{t_i\}, 使得 T(n,m)=0  ⟺  m≥tn−mT(n,m) = 0 \iff m \ge t_{n-m}.

(1)

反证法，假设后手有必胜策略，则先手有如下策略：

  1. 开始第一手随便下，将这颗棋子记作 AA；
  2. 之后，忽略随便下的子，然后根据后手的必胜策略：
    • 若要下的子与 AA 重合，则继续随便下一颗子，并将 AA 更新为这颗子；
    • 否则，直接按照后手的必胜策略下。

于是先手有必胜策略，矛盾，因此原假设不成立，命题得证。

(2)

要证明原命题，只需证明以下两个命题：

命题 1

对于任意 kk 存在 n−m=kn-m=k 使得 T(n,m)=0T(n,m)=0。

命题 2

若 T(n,m)=0T(n,m)=0，则 T(n+1,m+1)=0T(n+1, m+1)=0。

证明这两个命题之后，只需取 tk=min⁡{m∣T(m+k,m)}t_k = \min\{m \mid T(m+k,m)\} 即可。（命题 1 保证集合非空）

接下来我们来分别证明这两个命题。

步骤 1

引理 1

对于任意 n≥11n \ge 11 有 T(n,11)=0T(n,11)=0。

注

更好的结论是 T(n,8)=0T(n,8)=0（由一群荷兰数学家在 1980 年证明）。不过对于此题，T(n,11)=0T(n,11)=0 已经足够了。

证明

将棋盘划分成若干个 8×88 \times 8 的子棋盘，然后以如下方式为格子配对（若一个格子本应配对的位置超出棋盘范围，则认为该格子没有配对）：

配对
（红色：相邻格子；蓝色：不相邻格子；绿色：跨子棋盘）

于是后手有以下策略：

  • 若先手前一手的配对点存在且未被占据，则在此处落子；
  • 否则，在一个随机位置落子。 即可保证先手不同时占据两个配对点，从而最多连成 1010 子。

□\square

于是 T(k+11,11)=0T(k+11, 11)=0，命题 1 证毕。

步骤 2

引理 2

在 nn 格的长条形棋盘上，2,n2, n 两处摆放了先手的棋子。接下来，先手、后手交替落子。则后手存在一种策略，使先手不能连成四子。

证明
  • nn 为奇数时使用配对 1↔∅,3↔4,5↔6,…,n−2↔n−11 \leftrightarrow \varnothing, 3 \leftrightarrow 4, 5 \leftrightarrow 6, \dots, n-2 \leftrightarrow n-1；
  • nn 为偶数时使用配对 1↔3,4↔5,6↔7,…,n−2↔n−11 \leftrightarrow 3, 4 \leftrightarrow 5, 6 \leftrightarrow 7, \dots, n-2 \leftrightarrow n-1。

配对的处理方法同上。

引理 3

当 m≥3m \ge 3 时，T(n,m)=0⟹T(n+1,m+1)=0T(n,m)=0 \Longrightarrow T(n+1,m+1)=0。

证明

若有一方获胜时，一定满足以下四点之一：

  • 在左下角的 n×nn \times n 棋盘连成 mm 子；
  • 在上方的 (n+1)×1(n+1) \times 1 棋盘连成 (m+1)(m+1) 子；
  • 在右方的 1×(n+1)1 \times (n+1) 棋盘连成 (m+1)(m+1) 子；
  • 同时占领 (2,n+1)(2, n+1) 和 (n+1,2)(n+1, 2)。

从而当 T(n,m)=0T(n,m)=0 时，后手有如下策略：

  • 若对手上一手在左下角的 n×nn \times n 棋盘落子，则按照 n×nn \times n 的 mm 子棋策略应对；
  • 若对手上一手在 (2,n+1)(2, n+1) 和 (n+1,2)(n+1, 2) 中的任意一格落子，则自己在另一格落子；
  • 若对手上一手在 (n,n)(n,n) 落子，则自己在随机位置落子。之后落子与该手位置重复的解决方法同上；
  • 否则，按照引理 2 在上方的 (n+1)×1(n+1) \times 1 棋盘或右方的 1×(n+1)1 \times (n+1) 棋盘进行落子。

□\square

而显然当 m=1,2m=1,2 时，对于任意 n≥mn \ge m，总有 T(n,m)=1T(n,m)=1。于是命题 2 得证。

版权归属：Phantom-Bird

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