证明过程

题目描述

博弈论–取石子游戏
Alice 和 Bob 正在玩一个取石子游戏。共有 n个石子，双方轮流采取行动。每当轮到一人行动时，该名玩家需要从石子堆中取走恰好 1或 2或 k个石子。
如果轮到一人行动时，已经没有石子可取，则该名玩家失败。已知，双方都会采取最优策略，且 Alice 率先行动。
请问，最终谁将获胜。
输入格式
第一行包含整数 T，表示共有 T组测试数据。
每组数据占一行，包含两个整数 n,k。
输出格式
每组数据输出一行结果，如果 Alice 获胜，则输出 Alice，否则输出 Bob。
数据范围
前三个测试点满足，1≤T≤10。
所有测试点满足，$1\leq T \leq 100，0\leq n \leq 100，3\leq k \leq 109$。

样例

如图，当用一个数表示状态时，可以利用一维的list来枚举取法结果。当k取不同的值时，对应不用的n值的必胜、必败态不一致，但是也可以大致看出来有两种情况：1.$3\mid k$，2.$3\nmid k$。

必胜态的理解：当前状态时石子有n个，面对当前这种状态我至少有一种取法可以到达必败态

必败态的理解：当前状态时石子有n个，面对当前这种状态我没有任何一种取法可以到达必胜态

1. k不是3的倍数时，结论：从上图可以看出，n只要不是3的倍数就是必胜态，n是3的倍数就是必败态。

​ 证明：

​ 必败态==》必胜态：假设此时状态是先手必败，按条件有n是3的倍数($3\mid n$)，下一步对手可以取1或2或k个，设取完之后石子还剩$n^i$个，存在关系($n=n^i+1$)或($n=n^i+2$)或($n=n^i+k$)，n本来是3的倍数，取完1个或2个，$n^i$肯定不是3的倍数了，而大条件是“k不是3的倍数”，所以取了k个，$n^i$肯定也不是3的倍数了。

​ 必胜态==》必败态：假设此时状态是先手必胜，按条件有n不是3的倍数($3\nmid n$)，即存在k,r，使得$n=3\times k+r$，r作为余数，肯定＞0且＜3，可以是1或2，当前面对这个状态，自己可以取1或2个（r=1或r=2），设取完之后石子还剩$n^i$个，n本来是3的倍数，余数是r，取完r个，$n^i$肯定就是3的倍数了，就进入必败态（石子个数又变成3的倍数了）

1. k是3的倍数时，设有r满足$r = n\%(k+1)$，r的取值范围是[1-k]，结论：当r=k或者$3\nmid r$时必胜态；当$r<k且3\mid r$时必败态。

​ 证明：

​ 必败态==》必胜态：

必胜态==》必败态：两个条件满足之一即可。先证明条件1(r=k)：此时石子有n个，面对这种状态，自己可以选择拿k个，那下一个状态的$r^i$就满足$r^i=(n-k)\%(k+1)=(r-k)$，对于下一个状态来说，r是等于k的，那$r^i$就等于0，肯定满足“当$r<k且3\mid r$时必败态”这个条件，从而进入必败态，证毕；再证明条件2. r<k且($3\nmid r$)：此时石子有n个，面对这种状态，自己可以选择拿m个(也就是1个或2个)，这个m要满足$m=r\%3$，那下一个状态的$r^i$就满足$r^i=(n-m)\%(k+1)=(r-m)$，对于下一个状态来说，r是等于k的，m不是1就是2，那$r^i$就一定＜r，也就小于k，另一个，r不是3的倍数，余数是m，那(r-m)一定是3的倍数了，而$r^i=(r-m)$，所以$r^i$一定是3的倍数，肯定满足“当$r<k且3\mid r$时必败态”这个条件，从而进入必败态，证毕；

枚举找规律的代码:

N = 110
f = [0]*N
T = int(input())
n,k = map(int,input().split())
for i in range(1,n+1):
    d = [1,2,k]
    for x in d:
        #拿走x个之前是必败，表示我拿着这x个，一定就变成了必败态，自己就是必胜，设为1
        if i>=x and not f[i-x]:
            f[i] = 1
for i in range(n+1):
    print(f[i],end=" ")

AC代码：

def check(n,k):
    if k%3!=0:
        if n%3!=0:
            return 1
        else:
            return 0
    else:
        r = n%(k+1)
        if r==k or r%3!=0:
            return 1
        elif r<k and r%3==0:
            return 0

T = int(input())


for _ in range(T):
    n,k = map(int,input().split())
    if check(n,k):
        print('Alice')
    else:
        print('Bob')

如有问题，可以留言