科普 1051 字 约 3 分钟 15 图

2023跨年题的解答

原文链接:

【新年快乐!】一道有趣的计数问题

题目:

用由个小方格组成的L形(可旋转)和的小方格不重叠地覆盖的正方形棋盘,共有多少种覆盖方法?(旋转、对称后重合的视为不同方法)

答案:

(没错,就是这个神奇的年份数字)

主要思路:

按照第一列和第二列、第二列和第三列、第三列和第四列组成的三个矩形内L形的放置情况分类讨论.

基本图形:

首先枚举矩形内放置L形的所有情况,一共如下种:

重绘插图

但是可以发现,里面有一些图形本质上是一样的,比如考虑对称性时,第2、5、9、12个图形是一样的,这在一会的分类讨论过程中能够减少讨论次数.

我们将基本图形减少为如下种:

重绘插图

每种的个数依次为、、、、、、、、、、

再考虑单独一列被L形覆盖的格子情况,一共只有种情况:

重绘插图

例如,以下基本图形的左列和右列均为第种单列情况.重绘插图

开始计数:

从第二、三列开始,其中完整的L形共有种覆盖方式.我们考虑在每种覆盖方式下,第一、二列和第三、四列还能放入哪几种基本的图形.

(以下为无趣的枚举,读者可以先自行尝试)

(1)重绘插图左右均没有任何限制,方法数为.

(2)重绘插图左边为第四种单列情形,故第一、二列可以为第1、7、10、11、12、13种基本图形,共种;

右边为第二种单列情形,故第三、四列可以为第1、4、6、7、8、9、10、11、12、13、22、23、24、25、32、33种基本图形,共种.

此类情况方法数为.

(3)重绘插图左边为第四种单列情形(同(2)左边),故第一、二列共种;

右边为第三种单列情形,故第三、四列可以为第1、5、8、10、11、12、13、26、27、28、29种基本图形,共种.

此类情况方法数为.

(4)重绘插图左边为第五种单列情形,故第一、二列可以为第1、2、10、15种基本图形,共种;

右边为第三种单列情形(同(3)左边),故第三、四列共种.

此类情况方法数为.

(5)重绘插图左边为第十种单列情形,故第一、二列只能为第1种基本图形,共种;

右边为第六种基本图形,故第三、四列可以为第1、4、9、13、24种基本图形,共种.

此类情况方法数为.

(6)重绘插图左边为第十种单列情形,故第一、二列只能为第1种基本图形,共种;

右边为第七种基本图形,故第三、四列可以为第1、4、6、7、8、9、12、25种基本图形,共种.

此类情况方法数为.

(7)重绘插图左边为第九种单列情形,故第一、二列只能为第1、7、11种基本图形,共种;

右边为第九种单列情形,故第三、四列也共种.

此类情况方法数为.

(8)重绘插图左边为第八种单列情形,故第一、二列只能为第1、10种基本图形,共种;

右边为第九种单列情形,故第三、四列共种.

此类情况方法数为.

(9)重绘插图左边为第十种单列情形,故第一、二列只能为第1种基本图形,共种;

右边为第五种单列情形,故第三、四列只能为第1、5、13、29种基本图形,共种.

此类情况方法数为.

(10)重绘插图左边为第八种单列情形,故第一、二列共种;

右边为第八种单列情形,故第三、四列共种.

此类情况方法数为.

(11)重绘插图左边为第八种单列情形,故第一、二列共种;

右边为第八种单列情形,故第三、四列共种.

此类情况方法数为.

综上,方法总数为

注:

一般的、和的情形可以点击阅读原文查看.(的情形十分复杂)

留言

解法、疑问、勘误都可以说。公式用 LaTeX:行内 $…$,整行 $$…$$。

留言区还没开。想聊这道题,可以点上面的「在公众号查看原文」,到公众号那边留言。