有一个m*n方格的巧克力,最左上角一个方格有毒,两个人轮流在这个巧克力上选一个方格吃,当一个方格被选了以后,它的右边和下边的所有方格全被吃掉。每个人每轮必须吃,吃到有毒的一方为输。怎么选择你的策略?
策梅洛定理(Zermelo'stheorem):二人参与的游戏中,如果满足以下条件,那么先行一方有必胜策略或者后行一方有必胜策略。
用有向图的方法标识可行方案。用点Pi表示棋盘所有的可达状态,并用P和N分别标识所有先者胜或后者胜的状态;用有向边,如(P1,P2),表示存在从状态P1到状态P2的一步可行走法(吃法)。那么标记有向图中出度为0的点为P,标记至少存在一条边到P点的所有点为N,然后标记那些所有边到达的都是N状态的点为P,重复操作。
论文[1]陈述了两个结论,并予以证明:
证明(联合归纳):结论1显然是正确的。由结论2,从状态(a,a-1)经一步能到达的状态都是Nposition,如(a-1,a-1),(a-1,a-2),(a-1,a-3),...,(a,0),因此P2(b)隐含P1(a)。并且a=b或a-b=2,P2(b)隐含在P1(b-1)或P1(b)中。所以有P1(b-1)和P1(b)隐含P2(b),P2(b-1),...,p2(1),能推出P1(b)。又P1(1)是一个Pposition,得证。
对不确定的棋盘大小M*N,不存在一个多项式时间算法。特别地当M=2时,对于(a,a-1)这样的棋盘,能确定P和N状态,并且能找到先者胜的方案。下面讨论M=3的情况,设P(a,b,c)。
分析:根据最开始的依据,出度为0的点是P点、能一步达P点的是N点和只能从N点一步到达的状态是P点,可以从两行的棋盘总结出如下规律。
特别地当格子数一共有4格或5格时,情况如下:
由前面的结论,我们知道,
【1】DoronZeilberger,Three-RowedCHOMP,DepartmentofMathematics,TempleUniversity,Philadelphia,Pennsylvania19122,AdvancesinAppliedMathematics26,168–179(2001)
【2】https://zhuanlan.zhihu.com/p/30377770