简单证明:
查看原帖
简单证明:
1101254
Louisdlee楼主2024/5/2 20:50

问题:

有一堆石头,数量为NN,由Taka、AokiTaka、Aoki两名玩家轮流操作拿走石头。

TakaTaka一次能拿走1∼A1\sim A块石头,AokiAoki一次能拿走1∼B1\sim B块石头。

谁先拿光石头,谁获胜。

请问最终谁获胜?

证明:

1、A>BA>B,TakaTaka必胜

反向思考,AokiAoki获胜的条件是什么:

当AokiAoki 先手,且石子个数t≤Bt\leq B时,AokiAoki获胜。

那么什么样的状态能转移到这个状态:

当TakaTaka先手,且石子个数为t+At+A的时候,

但...因为A>BA>B,所以TakaTaka只需要将石子控制在B+1B+1就必胜了。

即拿走x=t+A−(B+1)x = t+A - (B+1)个石头。

因为t≤Bt\leq B

所以 t−(B+1)<0 t - (B+1)<0

所以x<Ax<A

这是完全能做到的。

所以AokiAoki​不可能赢。

2、A<BA<B

当TakaTaka拿过一次之后,就变成了上面证明的状态:AkoiAkoi先手,且A<BA<B的必败态

所以TakaTaka胜利机会只能在第一次拿石头的时候,即N≤AN\leq A,TakaTaka必胜

3、A=BA=B

经典的BashBash博弈,答案是:当N≡0( mod A+1)N\equiv0(\:mod \:A+1),先手必败

否则先手必胜

2024/5/2 20:50
加载中...