棋盘完全覆盖问题
基本信息
- 中文名
棋盘完全覆盖问题
- 外文名
problem of perfect cover of chessboard
- 所属学科
数学(组合学)
- 简介
一类组合问题
问题总述
考虑一个普通的棋盘，它有8行和8列，总共分成64个方格，设一个方格是1 cm2，问能否用32张长2 cm，宽1cm的纸片将棋盘覆盖住(任两片纸片不重叠且不能将纸片剪断)，这个问题称为棋盘的完全覆盖问题，显然很容易作出许多不同的完全覆盖，要计算不同的完全覆盖的个数虽然是困难的，但仍可算出来。1961年M.E.Fischer发现这个数是12988816=24×(921)2。2
m×n棋盘的完全覆盖
以上问题可推广到m行n列，mn个方格的棋盘的覆盖问题，也可以表述为：用2×1的骨牌，去覆盖一张m×n的棋盘，使得每一个骨牌占两个方格，而每个方格都有骨牌占住，而且没有两块骨牌重叠。
图1
此时完全覆盖就未必存在，如3×3棋盖就不能完全覆盖。那么对于m和n的哪些值，m×n的棋盘有完全覆盖呢?不难看到，一个m×n的棋盘有完全覆盖的充要条件是m和n至少有一个是偶数，换句话说，棋盘中的方格的个数是偶数3。
对于m×n棋盘的覆盖，最为困难的问题要算对覆盖种数的讨论。
假定我们用F(m，n)表示m×n棋盘覆盖方式的总数，显然，我们有
当n≥3时，读者不难从下图看出
F(2，n) =F(2，n-1)+F(2，n-2).
图2
由此可以推得数列{F(2，n)}如下；
1， 2， 3， 5， 8，13，21， 34， 55，．．．．．
聪明的读者想必都知道，这是著名的菲波那契数列!
至于求F(m，n)的一般公式，那是一项异常艰巨的工作。只知道公元1961年，M.E.费切尔求出8×8棋盘的覆盖方式的总数为
F(8，8)=24×(901)2=12988816.
其难度可想而知3。