精选优质文档-倾情为你奉上7 数学与统计学院 全秋洪残缺棋盘问题残缺棋盘（defective chess board）是一个有2k2k个方格的棋盘，其中恰有一个方格残缺。图3给出k2时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当k=0时，仅存在一种可能的残缺棋盘（如图3a所示）。事实上，对于任意k，恰好存在22k种不同的残缺棋盘。残缺棋盘的问题要求用3个方格的板（三格板）（triominoes）覆盖残缺棋盘（如图4所示）。在此覆盖中，两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。在这种限制条件下，所需要的三格板总数为(22k-1)/3。可以验证(22k-1)/3是一个整数。k为0的残缺棋盘很容易被覆盖，因为它没有非残缺的方格，用于覆盖的三格板的数目为0。当k=1时，正好存在3个非残缺的方格，并且这三个方格可用图4中的某一方向的三格板来覆盖。实际是要求用三格板覆盖n*n的方格棋盘，空出指定位置。图3 残缺棋盘图4 不同方向的三格板用分而治之方法可以很好地解决残缺棋
