BOB问题的较复杂解法

改编自我一年前出的一道 OI 题。

题目

$a$ 是一个数列，初始时长度为 $0$。甲和乙轮流操作，每次可以在 $a$ 的末尾添加一个数 $x(x\in {0,1})$，直至 $a$ 的长度为 $n$。

记 $S$ 为“好三元组”的个数。若整数三元组 $(i,j,k)$ 满足 $1\le i<j<k\le n$ 并且 $a_i=0,a_j=1,a_k=0$，则记其为“好三元组”。记 $S$ 为“好三元组”的个数。若 $S=0$ 或 $S$ 为指数，则乙获胜，否则甲获胜。

求出所有正整数 $n$，使得甲先手和甲后手两种情况中，有且仅有一种情况下，甲有必胜策略。

解法

由枚举可得：

当 $1\le n\le6$ 时，无论甲是先手还是后手，都必输；

当 $n=7$ 且甲先手时，甲必胜；

当 $n=7$ 且甲后手时，甲必输；

当 $n=8$ 时，无论甲是先手还是后手，都必胜。

下证 $n \ge 9$ 时，无论甲是先手还是后手，都必胜。$(*)$

1. 若 $n$ 为奇数且甲先手，或者 $n$ 为偶数且甲后手：

由前提可知最后一次操作是甲操作的。

因为 $n \ge 9$，所以甲至少有五次操作机会。此时甲前四次分别添加 $0,1,1,0$，第五次添加 $0$ 或 $1$ 使得 $a$ 中 $0$ 的个数为奇数。

对于每个 $a_i=1$，记其左边 $0$ 的个数为 $p$，右边 $0$ 的个数为 $q$，所以以 $a_i$ 为中间一项的“好三元组”个数为 $p\cdot q$。

因为 $0$ 的总个数为奇数，所以 $p+q$ 为奇数，所以 $p,q$ 中有且仅有一个为偶数，所以 $p\cdot q$ 为偶数。

所以以每个 $a_i=1$ 为中间项的“好三元组”个数均为偶数，所以 $S$ 为偶数。

又因为无论乙在 $a_2$ 填 $0$ 还是 $1$，$S$ 必定大于 $2$，所以 $S$ 必定为合数。

所以当 $n$ 为奇数且甲先手，或者 $n$ 为偶数且甲后手时，甲有必胜策略。

2. 若 $n$ 为奇数且甲后手，或者 $n$ 为偶数且甲先手：

考虑数学归纳法。

若 $n\le k$ 时 $(*)$ 成立，则 $n=k+1$ 时：

若 $n$ 为偶数且甲先手，则甲只需第一轮放 $1$，转化为 $n=k$ 且甲后手的情况，由归纳可知甲必胜。

若 $n$ 为奇数且甲后手，则甲先一直模仿乙上一轮的操作，直至字符串长度为 $n-8$。

1. 若前 $n-8$ 个数中已经出现了“好三元组”，那么接下来甲一直模仿乙的操作。所以除 $a_{n-8}$ 外，有 $a_{2i}=a_{2i+1}$，因此 $S$ 一定为 $4$ 的倍数，为合数。

2. 若前 $n-8$ 个数全为 $1$，则转化为 $n=8$ 且甲先手的情况，甲必胜。

3. 若前 $n-8$ 个数全为 $0$，接下来三轮甲分别放 $1,0,0$，若乙这三轮都放 $1$，则甲最后一轮放 $1$，否则放 $0$。依此策略甲可获胜。

4. 若前 $n-8$ 个数中，存在整数 $i,j \in [1,n-8]$ 且 $i < j$，使得 $a_i=0,a_j=1$，但不存在“好三元组”，则前 $n-8$ 个数形如 $11\cdots 100\cdots 0 11\cdots 1$。此时甲在前三轮一直模仿乙的操作，若前三轮乙都放 $1$，则甲第四轮放 $0$，否则继续模仿乙的操作。依此策略甲可获胜。

综上 $(*)$ 得证。

所以当且仅当 $n=7$ 时满足题意。