基于质数的组合博弈规则解析及先手最优策略求解问询

首先，我得先明确这个博弈的规则，避免理解偏差：

给定整数$N \ge 2$，这是一个无限回合的博弈：

1. 先手玩家选择一个满足$p_1 \le N$的质数$p_1$；
2. 后手玩家必须选择一个满足$p_1 < p_2 \le p_1+N$的质数$p_2$；
3. 后续玩家每次都要选择比前一个质数大、且不超过其加$N$的质数；
4. 无法说出符合条件的质数的玩家落败。

我们的目标是找到先手玩家应该选择的最优质数——也就是能让先手确保获胜的初始质数（如果存在多个，全部列出）。

核心思路：用胜负态分析推导最优解 #

这个博弈属于无偏组合博弈，我们可以通过定义每个质数的胜负态来逐步推导：

状态定义 #

对于质数$p$，定义状态$S(p)$：

• $S(p) = \text{True}$：表示当前玩家面对最后一个数是$p$时，能获胜（必胜态）；
• $S(p) = \text{False}$：表示当前玩家面对最后一个数是$p$时，会落败（必败态）。

状态推导规则 #

1. 如果不存在任何质数$p'$满足$p < p' \le p+N$，当前玩家无法行动直接落败 → $S(p) = \text{False}$；
2. 如果存在至少一个质数$p'$使得$S(p') = \text{False}$，当前玩家可以选这个$p'$让对手进入必败态 → $S(p) = \text{True}$；
3. 如果所有可选的$p'$的状态都是$\text{True}$，当前玩家无论怎么选对手都能赢 → $S(p) = \text{False}$。

关键结论 #

先手要想获胜，需要选择初始质数$p_1 \le N$，使得后手处于状态$p_1$时必败（即$S(p_1) = \text{False}$）。因为此时后手无论怎么操作，先手都能引导游戏走向胜利。

实现步骤与代码 #

步骤1：生成足够多的质数 #

我们需要生成足够多的质数，直到能覆盖所有需要计算状态的质数。这里用埃氏筛法，并且动态扩展筛的范围，直到找到一个质数$p$，使得下一个质数大于$p+N$（这样$S(p) = \text{False}$，作为推导的起点）。

步骤2：从后往前计算每个质数的状态 #

每个质数的状态依赖于后续更大的质数的状态，所以我们从最大的质数开始，反向推导每个质数的$S(p)$值。

步骤3：筛选出符合条件的初始质数 #

找出所有$\le N$且$S(p) = \text{False}$的质数，这些就是先手的最优选择。

Python代码实现 #

import bisect

def sieve(max_limit):
    """埃氏筛生成质数列表"""
    sieve_list = [True] * (max_limit + 1)
    sieve_list[0] = sieve_list[1] = False
    for i in range(2, int(max_limit ** 0.5) + 1):
        if sieve_list[i]:
            sieve_list[i*i : max_limit+1 : i] = [False] * len(sieve_list[i*i : max_limit+1 : i])
    primes = [i for i, is_prime in enumerate(sieve_list) if is_prime]
    return primes

def find_optimal_start_primes(N):
    if N < 2:
        return []
    
    # 动态生成足够多的质数，直到找到一个质数p，其下一个质数 > p+N
    max_limit = N * 10
    primes = []
    while True:
        primes = sieve(max_limit)
        # 从后往前找第一个满足下一个质数 > p+N的质数
        found_terminal = False
        for i in range(len(primes)-1, -1, -1):
            p = primes[i]
            next_p = primes[i+1] if (i+1 < len(primes)) else float('inf')
            if next_p > p + N:
                found_terminal = True
                break
        if found_terminal:
            break
        max_limit *= 2
    
    # 从后往前计算每个质数的胜负态
    state = {}
    for i in range(len(primes)-1, -1, -1):
        p = primes[i]
        # 找到所有符合条件的后续质数p'
        right_idx = bisect.bisect_right(primes, p + N)
        next_primes = primes[i+1:right_idx]
        
        if not next_primes:
            state[p] = False
        else:
            # 检查是否存在后续必败态
            has_losing_state = any(not state[np] for np in next_primes)
            state[p] = has_losing_state
    
    # 筛选出<=N的必败态质数（先手选这些，后手必败）
    optimal_primes = [p for p in primes if p <= N and not state[p]]
    return optimal_primes

# 测试示例
if __name__ == "__main__":
    print(find_optimal_start_primes(2))  # 输出: []（先手只能选2，但后手能获胜）
    print(find_optimal_start_primes(3))  # 输出: [3]
    print(find_optimal_start_primes(5))  # 输出: [5]

测试结果解释 #

• 当$N=2$时，先手只能选质数2，而$S(2)=\text{True}$（后手处于状态2时能获胜），所以先手没有必胜策略，返回空列表；
• 当$N=3$时，先手选3，后手处于状态3（必败态），无论后手选5，先手都能选7让后手进入必败态，最终先手获胜；
• 当$N=5$时，先手选5，后手处于状态5（必败态），后续先手可以一直引导后手进入必败态，直到后手无法行动。

内容的提问来源于stack exchange，提问作者saulspatz