乐读窝

程序员的数学思维修炼

乐读窝 > 科普学习 > 程序员的数学思维修炼

10.2残缺的棋盘能补上吗?

书籍名:《程序员的数学思维修炼》    作者:周颖



棋盘是我们常见的围棋、象棋、国际象棋等棋类游戏中不可或缺的基本道具,在棋盘中隐藏着许多有趣的图形构造问题。这节我们来做一个有趣的棋盘图形构造题。



10.2.1 被切割的棋盘


我们来看一个著名的问题,这个问题曾作为中国科技大学少年班的招生试题。如图10-7所示是一个残缺的国际象棋棋盘,在棋盘左上角和右下角都有一个方格被剪切了。请问,能不能用31个如图10-8所示的2×1的矩形拼出图10-7所示的残缺棋盘。

图10-7

图10-8

图10-8所示为棋盘的2格,在拼接时可以旋转,但不能重叠。例如,可拼接成图10-9所示的图形(为了方便辨识图10-8所示长方形矩形,在该长方形矩形中两个方格之间用虚线分隔标识),其中图(a)是将两个矩形放在同一行,图(b)左侧是横着放置的矩形,右侧将矩形进行了旋转,图(c)将两个矩形放在同一列,图(d)上方将矩形进行了旋转,下方横着放置矩形。

图10-9

图10-9所示两个矩形之间没有重叠,是可以的。但是,不能用图10-10所示的方式进行拼接,因为这时两个矩形有一部分重叠了。图(a)看起来是三个正方形块了,其实是将两个矩形的一半重叠在了一起;同样,图(b)也是这种情况,只是将矩形旋转成竖直放置了;图(c)则是一个水平放置的矩形与一个垂直放置的矩形进行了重叠。

图10-10



10.2.2 能拼接出残缺棋盘吗


先对图10-7所示残缺棋盘进行计算,完整的棋盘共有8行8列:

即应有64个正方形的方格。

根据题意,左上角和右下角各剪掉一个方格,则只有62个方格。而图10-8所示矩形是由两个方格组成的,因此:

正好是31。

因此,很容易得出能用31个图10-8所示矩形拼接出图10-7所示残缺棋盘的结论。

可是,这是错误的!

为什么是错误的呢?我们来验证一下。如图10-11所示,从左上角开始放置图10-8所示长方形矩形,第1、2、3个矩形都进行水平拼接,第4个矩形旋转90°后拼接。接着,在第4个矩形的左边、第3个矩形的下方拼接第5个矩形。然后向左方拼接第6、7个矩形,第8个矩形又旋转90°,第9个矩形又开始向右拼接……,这样循环进行,直到第27个都还能正常拼接,但是,准备在右下角拼接第28个时发现只剩一个方格(右下角带斜线的方格),没办法拼接了!

图10-11

因此,可知道前面的结论是错的!不能用31个图10-8所示矩形拼接出图10-7所示残缺棋盘!

采用图10-11所示的方法逐个进行拼接,最终得出一个否案的答案。可是这种方法比较麻烦,要逐个去测试。

其实,我们还可以有更快速的方法。

仔细分析,国际象棋棋盘是用颜色进行了标识的,棋盘格采用黑、白相间涂色,如图10-12所示。从图中可看到在一个白格的上、下、左、右都是黑格,同样,在一个黑格的上、下、左、右都是白格。因此,图10-8所示由两个方格组成的矩形一次能且只能拼接棋盘中的一个黑格和一个白格。

图10-12

如图10-12所示,残缺棋盘中共有62个方格,其中有黑格32个,白格30个。根据前面的分析,用图10-8所示的矩形进行拼接时,这个矩形的两个方格中有一个黑格一个白格。那么,31个矩形拼接成的图形应该有31个黑格、31个白格。而图10-12中却为32个黑格、30个白格。因此,没办法用图10-8所示矩形拼接出图10-7所示的残缺棋盘。

在这个例子中,看似简单的几何图形构造,如果不经推敲分析,很容易得出错误的结论。由此可见几何图形构造的有趣之处。