关于《训练指南》中的“翻棋子游戏”

刘汝佳的《训练指南》组合游戏部分中写了“翻棋子游戏”这样一个问题:一个棋盘上每个格子有一个棋子,每次操作可以随便选一个朝上的棋子(x,y),代表第i行第j列的棋子,选择一个形如(x,b)或(a,y)(其中b < y,a < x)的棋子,然后把它和(x,y)一起翻转,无法操作的人输。

对于该问题,书上的分析如下:把坐标为(x,y)的棋子看成大小分别为x和y的两堆石子,则本题转化为了经典的Nim游戏,如果难以把棋子看作石子,可以先把Nim游戏中的一堆石子看成一个正整数,则Nim游戏中的每次操作是把其中一个正整数减小或者删除。

对于如何将棋子看成石子堆,最开始也是十分疑惑,后来想通了,现将完整思路整理如下:

首先对于当前所有n个正面朝上的棋子,看做数量分别为其横纵坐标大小的两堆石子,总共即为2n堆石子。现选择棋子(x,y),同时也选择了(a,y),其中a<x。这时分两种情况:

  1. 如果(a,y)也是正面朝上,那么相当于删去了大小为x,y,a,y的四堆石子。设原所有石子堆的Nim和为K,则现在的Nim和变为Kxyay=Kxa 这可以看成是一个Nim和为K的石子堆中去掉了一个大小为x的堆,而后又增添了一个大小为a的堆,也就相当于某个大小为x的堆去掉了x-a个石子。
  2. 如果(a,y)是反面朝上,那么相当于添加了a,y大小的石子堆,删去了x,y大小的石子堆,Nim和同样变为Kxyax,与1.中本质上是一样的。
    综上所述,对棋子的每一次操作都相当于是在初始的2n堆石子堆中进行了一次类似Nim游戏的操作,因此可以将翻棋子游戏看作是有这样2n堆石子的Nim游戏。
原文地址:https://www.cnblogs.com/DrCarlluo/p/6746106.html