目录#

起因
问题构建 & 前置知识
手推过程
$DS$ 过程
验证结论
补充

起因#

高中毕业，整理材料的时候，发现自己之前在草稿纸上探究到一半的变种取火柴问题。于是就展开来探究了一下。

问题构建 & 前置知识#

正常的取火柴问题是：一堆火柴一共有 $n$ 根，有两个足够聪明的人轮流取火柴，每次可以取 $1\sim a$ 根，取到最后一根火柴的人胜利，问先手必胜还是后手必胜。

例如，每次可以取 $1\sim 3$ 根。很容易知道，当 $4 \mid n$ 时，后手必胜，否则先手必胜。也就是说，对于取 $1\sim a$ 的情况，当且仅当 $n$ 是 $(a+1)$ 的倍数时，后手必胜。这里不展开赘述。

现在我们要讨论的是，如果在 $1\sim a$ 中跳过一个数不能取，周期会发生什么变化？如果跳过不止一个数，周期又会发生什么变化？

在后续的问题探讨中，可以采用线性递推的方式，例如，你已经知道总火柴数为 $1\sim n$ 时分别的必胜情况，那么对于总数 $(n+1)$ 的情况，只要能够一次取若干根跳到一个后手必胜的局面，那么该情况一定是先手必胜；若找不到，则后手必胜。

手推过程#

跳过一个数#

问题变为：每次可以取 $1\sim a$ 或 $(a+2)$

这个问题依然比较经典，经过几个例子的尝试后可以发现，后手必胜情况的周期为断点位置，即后手必胜当且仅当 $n=k(a+1),k$ 为正整数。

后面不止一个数#

问题变为：每次可以取 $1\sim a$ 或 $(a+2)\sim b$

我们尝试举例。

尝试 $1$ $2$ $4$ ：后手必胜周期 $3$

尝试 $1$ $3$ $4$ ：后手必胜周期 $2/5$ 交替，大周期 $7$

注意到，我们似乎需要比较前后两段数字的长短，也就是 $a$ 和 $(b-a-1)$ 的大小关系。

似乎，前半段较短时，会出现交替后手必胜周期；后半段较短时则不会？

尝试 $1\sim 6$ $8\sim 13$ ：后手必胜周期 $7$

尝试 $1\sim 6$ $8\sim 14$ ：后手必胜周期 $7/15$ 交替，大周期 $22$

推论：

当 $2a+1\geq b$ ：后手必胜周期 $(a+1)$
当 $2a+1 < b$ ：后手必胜周期 $(a+1)/(b+1)$ 交替，大周期 $(a+b+2)$

经过多轮验证，应该成立。

开头一般化#

问题变为：每次可以取 $a\sim b$ 或 $(b+2)\sim c$

这种情况不符合题目情况，总数为特定数时会出现最后几根怎么也取不走的情况，游戏无法进行。

故我们不讨论这种情况。

跳过若干数#

问题变为：每次可以取 $1\sim a$ 或 $(a+3)\sim b$

我们毫无头绪，于是举例：

尝试 $1$ $2$ $5$ ：后手必胜周期 $3$

尝试 $1$ $2$ $6$ ：后手必胜周期 $3/4$ 交替，大周期 $7$

尝试 $1$ $2$ $7$ ：后手必胜周期 $3$

尝试 $1$ $2$ $8$ ：后手必胜周期 $3$

尝试 $1$ $2$ $9$ ：后手必胜周期 $3/3/4$ 交替，大周期 $10$

尝试 $1$ $2$ $10$ ：后手必胜周期 $3$

尝试 $1$ $2$ $11$ ：后手必胜周期 $3$

尝试 $1$ $2$ $12$ ：后手必胜周期 $3/3/3/4$ 交替，大周期 $13$

尝试 $1$ $3$ $4$ ：后手必胜周期 $2/5$ 交替，大周期 $7$

尝试 $1$ $4$ $5$ ：后手必胜周期 $2/6$ 交替，大周期 $8$

尝试 $1$ $5$ $6$ ：后手必胜周期 $2/2/7$ 交替，大周期 $11$

尝试 $1$ $6$ $7$ ：后手必胜周期 $2/2/8$ 交替，大周期 $12$

尝试 $1$ $7$ $8$ ：后手必胜周期 $2/2/2/9$ 交替，大周期 $15$

尝试 $1$ $8$ $9$ ：后手必胜周期 $2/2/2/10$ 交替，大周期 $16$

尝试 $1$ $2$ $5$ $6$ ：后手必胜周期 $3/4$ ，大周期 $7$

尝试 $1$ $2$ $6$ $7$ ：后手必胜周期 $3/5$ ，大周期 $8$

尝试 $1$ $2$ $7$ $8$ ：后手必胜周期 $3$

尝试 $1$ $2$ $8$ $9$ ：后手必胜周期 $3/3/4$ ，大周期 $10$

感觉似乎是有规律的，但是我搞不明白，于是，我转向了 $Deepseek$ 。

$DS$ 过程#

经过 $DS$ ，我们发现，当取 $1 \sim a$ $c \sim b$ $(c \ge a+2)$ 的时候：

如果不考虑 $c \sim b$ 的部分，大于 $a$ 的部分如果不是 $(a+1)$ 的倍数，一定先手胜，所有 $(a+1)$ 的倍数都是后手胜。

加入考虑， $c \sim b$ 中可能影响后手胜位置的，便是其中是 $(a+1)$ 倍数的数。例如含有 $(2a+2)$ ，那么此时比 $(2a+2)$ 略大的数，跳到的 $(2a+2)$ 就会变成先手胜。

这个时候我们需要讨论，通过 $1\sim 3$ $10\sim 13$ 和 $1\sim 3$ $10\sim 12$ 两个例子，我们发现前者是 $4/4/14$ ， $14$ 接在后边构成 $22$ 大周期，后者是 $13$ 把 $4/4$ 包在里面形成 $13$ 大周期。

于是我又 $DS$ 了一下，对于 $1 \sim a$ $c \sim b$ ，记 $L=a+1$ ，他给出的结论是:

1
if 后半段连续区间包含m*L（m为能取所有值的最小值）:
2
    if m>=2 and 后半段区间长>=L:
3
        T=(m-1)L+(b+1) 接尾型
4
    else:
5
        T=b+1 包裹型
6
else:
7
    T=a+1 断点型

对于分支一，通俗的解释是： $1\sim a$ 覆盖所有可到达的非倍数余数，如果无 $L$ 的倍数，那么所有后手胜的位置都不会受到影响，等于是先手胜的位置自己之间加了一些连接。

对于分支二，通俗的解释是： $b$ 是能减去的最大数， $(b+1)$ 之前的数都按照 $L$ 的倍数规则，其中 $c\sim b$ 全部标为先手胜，那么如果 $(b+1)$ 跳不到任何后手胜点，他自己就是后手胜，否则会被推迟到 $(m-1)L+(b+1)$ 。

验证结论#

验证方案#

验证规则成立：对拍

对拍，具体来说就是，对比“暴力递推”和“规律求解”两种方法得出的周期是不是都相同。

输入#

输入所有可以取的数，然后输出 $n$ 为 $1\sim 1000$ 分别是谁必胜，记先手必胜为 $0$ ，后手必胜为 $1$ 。

规律求解法#

于是我先写了一个按照规则输出周期的代码 answer.cpp 。

暴力递推法#

在写这个代码的时候，我发现，我需要根据获得的 $0/1$ $ans$ 数组来求它的最小周期，这个时候我们可以使用 $KMP$ 匹配算法，此处不展开讲述，代码写入 duipai.cpp 。

随机数据生成#

这里我们使用 C++ 中的均匀整数生成工具，代码如 random.cpp 。

比对数据#

我写了一个程序，让他们自动生成 $1000$ 次数据，比对 $1000$ 次，看结果是否有差异。代码如 check.cpp 。

参考代码#

所有代码如下：

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,A[105],m,L,a,c,b,T;
4
bool flag;
5
int read(){
6
    int x=0,f=0;
7
    char c=getchar();
8
    while(c<'0'||c>'9'){
9
        if(c=='-') f=1;
10
        c=getchar();
11
    }
12
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
13
    return f?-x:x;
14
}
15
int main(){
16
    n=read();
17
    for(int i=1;i<=n;++i) A[i]=read();
18
    //1.successive?
19
    flag=1;
20
    for(int i=2;i<=n;++i) if(A[i]!=A[i-1]+1){
21
        flag=0;
22
        a=A[i-1],c=A[i],b=A[n];
23
        break;
24
    }
25
    if(flag) T=A[n]+1;
26
    else{
27
        L=a+1;
28
        //2.mL?
29
        flag=0;
30
        for(int i=c;i<=b;++i) if(i%L==0){
31
            flag=1;
32
            m=i/L;
33
            break;
34
        }
35
        if(flag){
36
            if(m>=2&&b-c+1>=L) T=(m-1)*L+b+1;
37
            else T=b+1;
38
        }else T=L;
39
    }
40
    cout<<T;
41
    return 0;
42
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,a[105],pi[1005];
4
bool flag,ans[1005];
5
int read(){
6
    int x=0,f=0;
7
    char c=getchar();
8
    while(c<'0'||c>'9'){
9
        if(c=='-') f=1;
10
        c=getchar();
11
    }
12
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
13
    return f?-x:x;
14
}
15
int main(){
16
    n=read();
17
    for(int i=1;i<=n;++i) a[i]=read();
18
    for(int i=0;i<1000;++i){
19
        flag=1,ans[i]=0;
20
        for(int j=1;j<=n;++j) if(i-a[j]==0||(i-a[j]>0&&ans[i-a[j]])) flag=0;
21
        if(flag) ans[i]=1;
22
    }
23
    //find circle
24
    for(int i=1;i<1000;++i){
25
        int j=pi[i-1];
26
        while(j>0&&ans[i]!=ans[j]) j=pi[j-1];
27
        if(ans[i]==ans[j]) ++j;
28
        pi[i]=j;
29
    }
30
    cout<<1000-pi[999];
31
    return 0;
32
}

1
#include<bits/stdc++.h>
2
#include<random>
3
using namespace std;
4
int a,c,b,n,A[55];
5
int main(){
6
    default_random_engine e;
7
    uniform_int_distribution<int> u(1,20);
8
    e.seed(time(0));
9
    a=u(e);
10
    c=u(e)+a;
11
    b=u(e)+c;
12
    for(int i=1;i<=b;++i) if(i<=a||(c<=i&&i<=b)) A[++n]=i;
13
    cout<<n<<"\n";
14
    for(int i=1;i<=n;++i) cout<<A[i]<<" ";
15
    return 0;
16
}

1
#include<bits/stdc++.h>
2
#include<windows.h>
3
using namespace std;
4
int main(){
5
    int T=1000;
6
    while(T--){
7
        printf("#%d\n",1000-T);
8
        system("random.exe > random.txt");
9
        system("duipai.exe < random.txt > duipai.txt");
10
        double st=clock();
11
        system("answer.exe < random.txt > answer.txt");
12
        double ed=clock();
13
        if(system("fc duipai.txt answer.txt")) return(printf("Wrong Answer  %.0lfms",ed-st))&&0;
14
        else if(ed-st>1000) return(printf("Time Limit Exceeded  %.0lfms",ed-st))&&0;
15
        else printf("Accepted  %.0lfms\n",ed-st);
16
        puts("");
17
    }
18
    return 0;
19
}

结果#

一开始，第 $74$ 个比对出现差异，原因是当时 answer.cpp 第 $33$ 行的 break 忘记加了。

更正后， $1000$ 次答案均无差异。

因此，推断结论成立。

若后半段不是连续区间呢？

似乎没有确切规律，或者说规律太过复杂，有兴趣的读者可以自行探究。

补充#

最后问了一下 $DS$ 这在博弈论里是什么问题，他是这么说的，仅供参考：

是的，这个问题属于组合博弈论（Combinatorial Game Theory）的范畴，具体是无偏博弈（impartial game）中的减法游戏（subtraction game），也可以看成是单堆 Nim 的变种。

目录#

起因#

问题构建 & 前置知识#

手推过程#

跳过一个数#

后面不止一个数#

开头一般化#

跳过若干数#

$DS$ 过程#

验证结论#

验证方案#

输入#

规律求解法#

暴力递推法#

随机数据生成#

比对数据#

参考代码#

结果#

补充#

支持与分享

评论区

文章目录

取火柴问题变种

目录#

起因#

问题构建 & 前置知识#

手推过程#

跳过一个数#

后面不止一个数#

开头一般化#

跳过若干数#

DSDSDS 过程#

验证结论#

验证方案#

输入#

规律求解法#

暴力递推法#

随机数据生成#

比对数据#

参考代码#

结果#

补充#

支持与分享

评论区

文章目录

$DS$ 过程#