棋盘的完美覆盖

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《棋盘的完美覆盖》，欢迎阅读！

棋盘的完美覆盖

考虑一张普通的棋盘，它被分成8行8列共64个方格。假设有一些形状相同的多米诺骨牌，每张牌正好可以覆盖棋盘上两个相邻的方格。是否能够把32张 多米诺骨牌摆放在棋盘上，使得没有两张牌重叠，且在每张牌覆盖两个方格的条件下覆盖棋盘上的所有方格呢？我们把这样的摆放称为棋盘的多米诺骨牌完美覆盖或 者盖瓦。这是一个很简单的摆放问题，我们可以很快构造出很多不同的完美覆盖。计数出不同完美覆盖的数量虽说比较困难，但也不是没有可能。1961年 Fischer1发现了这个数，它是12988816=24×172×532。 我们可以用更一般的棋盘代替这常用的棋盘，这个更一般的棋盘拥有m行n列，被分成mn个方格。此时，它的完美覆盖不一定存在。事实上，对于3×3的棋盘来 说，它就不存在完美覆盖。那么对于什么样的m×n棋盘存在完美覆盖呢？不难看出，对于m×n棋盘，它有完美覆盖当且仅当m和n中至少有一个是偶数，或者等 价地说成：当且仅当这个棋盘的方格总数是偶数。Fischer得出了计算m×n棋盘的不同完美覆盖数的一般公式，这个公式中含有三角函数。这个问题等价于 分子物理学中一个非常著名的问题，即所谓的二聚物问题。这一问题始于对表面上的双原子（二聚物）吸收的研究。棋盘方格对应于分子，而多米诺骨牌对应于二聚 物。 再来考虑8×8棋盘，并用一把剪刀剪掉一条对角线上两个对角上的两个方格，于是剩余方格总数是62个。那么是否有可能用31张多米诺骨牌得到这个 “被剪过的”棋盘的完美覆盖呢？尽管这个被剪过的棋盘与8×8棋盘非常接近，尽管原来的棋盘有1200多万个完美覆盖，但是这个被剪过的棋盘却没有完美覆 盖。这一结论的证明本身就是一个简单但又巧妙的组合推理的实例。在标准的8×8棋盘上，通常把方格交替地着上黑色和白色，于是有32个白色方格和32个黑 色方格。如果我们剪掉一条对角线上的两个对角上的方格，那么就剪掉了相同颜色的两个方格,比如说是两个白色方格。因此就剩下32个黑色方格和30个白色方 格。但是每一张多米诺骨牌要覆盖一个黑格和一个白格，因此在棋盘上31张不重叠的多米诺骨牌覆盖31个黑格和31个白格。这样我们得出结论是这个被剪过的 棋盘没有完美覆盖。上述推理可以总结为：31BW≠32B+30W更一般地，我们可以取一个m×n棋盘，它的方格也交替地着上黑色和白色，而且随机切掉一 些方格，于是剩下一个切过的棋盘。什么时候这个切过的棋盘有完美覆盖呢？要使完美覆盖存在，这个切过的棋盘必须有相同数目的黑格和白格。但是这个条件不是 充分条件，如图1-1所示。

因此，我们就要问：一个切过的棋盘存在完美覆盖的充分必要条件是什么？我们将在第9章再讨论这个问题，并得到一个圆满的答案。在那里，我们就分配胜任工作的应用例子给出这个问题的一个实用公式。

对于m×n棋盘的多米诺骨牌完美覆盖的问题,还有另外一个拓展。设b是一个正整数。现在我们不用多米诺骨牌,取而代之的是1×b的条形牌,它是由b 个1×1方格并排连接而成的。这样的条形牌称为b格牌（b-ominoe）。它们可以覆盖一行或一列上连续的b个方格。图1-2图示的是一个5格牌。2格 牌是多米诺骨牌。1格牌也被称为单牌。


m×n棋盘的b格牌完美覆盖是棋盘上b格牌的一个排列，使得（1）没有两个b格牌重叠，（2）每一个b格牌覆盖棋盘上b个方格，（3）棋盘上的所有 方格被覆盖。什么时候m×n棋盘有b格牌覆盖的完美覆盖呢？因为棋盘上的每一个方格正好被一个b格牌覆盖，为了有完美覆盖，b必须是mn的一个因子。的 确，完美覆盖存在的一个充分条件是b是m或者n的一个因子。因为如果b是m的一个因子，那么我们就可以正好把m/b个b格牌覆盖在这个m×n棋盘上的n列 中的每一列上，而如果b是n的一个因子，那么我们就可以正好把n/b个b格牌覆盖在这个m×n棋盘上的m行中的每一行上。在这里，这个充分条件是否也是完 美覆盖的必要条件呢？暂时假设b是一个素数，而且存在m×n棋盘的b格牌覆盖的完美覆盖。那么，因为b是mn的一个因子，根据素数的性质可知b是m或者n 的因子。因此我们说至少当b是素数时，m×n棋盘可能被b格牌完美覆盖的充分必要条件是b是m或者n的因子。

当b不是素数时，我们必须采用不同的方式加以讨论。假定有m×n棋盘的b格牌覆盖的完美覆盖。我们要证明m或者n被b除时余数是0。设m和n除以b 时的商和余数分别是p,q和r,s，则：m=pb+r, 其中0≤r≤b-1 n=qb+s, 其中0≤s≤b-1如果r=0，那么b是m的一个因子。如果s=0，那么b是n的一个因子。通过交换这个棋盘的行和列，不妨设r≤s。 于是我们要证明r=0。 现在把多米诺骨牌（b=2）覆盖时棋盘交替着成黑白两色的情况推广到b种颜色的情况。我们选出b种颜色并把它们标注上1,2,„，b。接下来用图1-3所示的方式5给b×b棋盘着色，然后再用图1-4给出的方式把这种着色扩展到m×n棋盘。图1-4是m=10,n=11,b=4的情况。



完美覆盖的每一张b格牌覆盖b个方格且每一个方格覆盖一种颜色。于是，在棋盘上每一种颜色的方格数一定相同。下面我们考虑把这个棋盘分成三个部分： 上方pb×n部分，左下方r×qb部分和右下方r×s部分。（图1-4给出的是10×11棋盘，我们已经有的三个部分是上方8×11，左下方2×8，右下 方2×3。）在上方部分，在每一列上，因为每一种颜色出现p次，所以它们总共出现pn次。在左下方部分，在每一行上，因为每一种颜色出现q次，因此它们总 共出现rq次。因为在整个棋盘上每一种颜色出现的次数相同，所以我们说在右下方r×s部分上，每一种颜色出现的次数也一定相同。

在右下方r×s部分上，颜色1出现多少次呢？因为已知r≤s，且我们的着色特点使得颜色1在r×s部分的每一行上出现一次，所以它在r×s部分上出 现r次。现在我们计数在r×s部分上的方格总数。一方面，它有rs个方格；另一方

本文来源：https://www.wddqxz.cn/72a663a0c8d376eeaeaa31f5.html