Chomp

题目

Alice和Bob轮流在一个\(m\times n\)的巧克力块上咬掉方块。每次咬掉某个小方格时，同时会把该格及其上方和/或右方的所有剩余小格一并咬掉¹。左下角的那个方格是有毒的，咬到它的人输。证明：当巧克力上不止一个方格时，先手Alice有必胜策略。

分析

直观思路：该结论通过“策略偷窃（strategy stealing）”证明。证明方法是假设后手Bob有必胜策略，然后说明先手可以通过先走一步并“偷用”Bob的策略来得到矛盾，从而得出后手不可能有必胜策略，先手必胜。该证明是非构造性的——它保证先手有必胜策略，但并不显式给出该策略。

严格证明（策略偷窃）：

1. 设存在一个\(m\times n\)的巧克力，且格数不止一个。假设反设：后手Bob有一个必胜策略\(S\)（对每一种先手的第一步，Bob都能作出回应并最终获胜）。

2. 先手Alice先随意咬下一格（但不咬毒格）。例如，她可以咬右上角的某一格。若此时Bob没有必胜的回应，则Alice这一步已经把Bob置于无胜法的局面，Alice必胜，和反设矛盾。故Bob对Alice的这一步必有某个必胜回应，我们记作\(B\)。

3. 现在Alice改变策略：她将\(B\)当作自己的第一手（也就是说，直接先做\(B\)这步），随后在每一步都按照原先假定的Bob的策略\(S\)来走——具体地，每当\(S\)建议后手应如何走时，Alice就把那一步作为自己下一步来走（因为此时角色对调，Alice把原来属于“后手”的应对策略当作自己的行动准则）。

4. 可能出现的问题是\(S\)会建议走已被提前吃掉的格子；此时Alice只需改走任何一个合法的格子来代替。这样的替代不会把胜利白白送给Bob：如果替代步会让Bob更容易获胜，那么原来在Bob按\(S\)下的对局中也不可能必胜（与设定矛盾）。因此替换步骤不会破坏偷用\(S\)的策略。

5. 因此，若Bob真的有一个必胜策略\(S\)，Alice就可以通过先走一步（任意非毒格）并随后“偷用”\(S\)来保证获胜——这与假设Bob必胜矛盾。

6. 所以后手不可能有必胜策略，先手Alice必定有某个必胜策略（虽然证明并不显示出该策略的具体形式）。

结论：Alice作为先手有必胜策略。

图示