问题:
有一堆石头,数量为N,由Taka、Aoki两名玩家轮流操作拿走石头。
Taka一次能拿走1∼A块石头,Aoki一次能拿走1∼B块石头。
谁先拿光石头,谁获胜。
请问最终谁获胜?
证明:
1、A>B,Taka必胜
反向思考,Aoki获胜的条件是什么:
当Aoki 先手,且石子个数t≤B时,Aoki获胜。
那么什么样的状态能转移到这个状态:
当Taka先手,且石子个数为t+A的时候,
但...因为A>B,所以Taka只需要将石子控制在B+1就必胜了。
即拿走x=t+A−(B+1)个石头。
因为t≤B
所以 t−(B+1)<0
所以x<A
这是完全能做到的。
所以Aoki不可能赢。
2、A<B
当Taka拿过一次之后,就变成了上面证明的状态:Akoi先手,且A<B的必败态
所以Taka胜利机会只能在第一次拿石头的时候,即N≤A,Taka必胜
3、A=B
经典的Bash博弈,答案是:当N≡0(modA+1),先手必败
否则先手必胜