查看源代码：
ATTIII-solution-4.md

---
title: 注意力测试 Ⅲ P4 解答
createTime: 2026/4/4
categories:
  - study
tags:
  - maths
  - FFMP
---

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

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

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

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

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

(2) 存在数列 $\{t_i\}$, 使得 $T(n,m) = 0 \iff m \ge t_{n-m}$.
:::

## (1)

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

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

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

## (2)

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

:::lemma 命题 1
对于任意 $k$ 存在 $n-m=k$ 使得 $T(n,m)=0$。
:::

:::lemma 命题 2
若 $T(n,m)=0$，则 $T(n+1, m+1)=0$。
:::

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

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

### 步骤 1

:::lemma 引理 1
对于任意 $n \ge 11$ 有 $T(n,11)=0$。
:::

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

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

:::center
![配对](./ATTIII-solution-4/image.png)  
（红色：相邻格子；蓝色：不相邻格子；绿色：跨子棋盘）
:::

于是后手有以下策略：
- 若先手前一手的配对点存在且未被占据，则在此处落子；
- 否则，在一个随机位置落子。
即可保证先手不同时占据两个配对点，从而最多连成 $10$ 子。

:::right
$\square$
:::
::::

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

### 步骤 2

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

:::proof
- $n$ 为奇数时使用配对 $1 \leftrightarrow \varnothing, 3 \leftrightarrow 4, 5 \leftrightarrow 6, \dots, n-2 \leftrightarrow n-1$；
- $n$ 为偶数时使用配对 $1 \leftrightarrow 3, 4 \leftrightarrow 5, 6 \leftrightarrow 7, \dots, n-2 \leftrightarrow n-1$。

配对的处理方法同上。
:::

:::lemma 引理 3
当 $m \ge 3$ 时，$T(n,m)=0 \Longrightarrow T(n+1,m+1)=0$。
:::

::::proof
若有一方获胜时，一定满足以下四点之一：
- 在左下角的 $n \times n$ 棋盘连成 $m$ 子；
- 在上方的 $(n+1) \times 1$ 棋盘连成 $(m+1)$ 子；
- 在右方的 $1 \times (n+1)$ 棋盘连成 $(m+1)$ 子；
- 同时占领 $(2, n+1)$ 和 $(n+1, 2)$。

从而当 $T(n,m)=0$ 时，后手有如下策略：
- 若对手上一手在左下角的 $n \times n$ 棋盘落子，则按照 $n \times n$ 的 $m$ 子棋策略应对；
- 若对手上一手在 $(2, n+1)$ 和 $(n+1, 2)$ 中的任意一格落子，则自己在另一格落子；
- 若对手上一手在 $(n,n)$ 落子，则自己在随机位置落子。之后落子与该手位置重复的解决方法同上；
- 否则，按照引理 2 在上方的 $(n+1) \times 1$ 棋盘或右方的 $1 \times (n+1)$ 棋盘进行落子。

:::right
$\square$
:::
::::

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