专栏/多联骨牌:从多米诺骨牌和俄罗斯方块讲起

多联骨牌:从多米诺骨牌和俄罗斯方块讲起

2019-08-04 13:35--阅读 · --喜欢 · --评论
粉丝:1215文章:24

       大家知道现在销量最高的电子游戏是什么吗?从我们专栏的题目中来简单的二选一:俄罗斯方块。自1984年阿列克谢·帕基特诺夫从拼图中获得了灵感并将其实现在了计算机上后,这个玩法简单且休闲的小游戏就迅速的普及开来,成为现在家喻户晓的“俄罗斯方块”。

       咳,不过我今天可不是来讲历史的,关于俄罗斯方块的历史,百度一下你就知道了(ಡωಡ),而且其本名应该叫“Tetris”,由“Tetra”与“Tennis”结合而成,其中的Tetra,就是希腊语的“四”,没错,俄罗斯方块在数学中又叫做“四联骨牌,四格骨牌(Tetromino)”。那么三格骨牌呢?Tromino,而二格骨牌就是:Domino,是不是读音很耳熟?这就是多米诺骨牌。据传多米诺骨牌起源于中国的“牌九”,由意大利传教士从中国引入欧洲,不过这段起源大家还是在网上查查吧,肯定比我讲的详细。

       现在我们顾名思义,理解一下这些名词究竟是什么意思。多米诺骨牌,又称为二格骨牌,就是由两个单位正方形边对边拼接而成的图形。同理,三格骨牌,四格骨牌就是由三个或四个单位正方形边对边拼接而成的图形,同时再往上增加正方形的个数就还有五格,六格等骨牌。那么单独一个正方形也是骨牌吗?是,这个正方形叫做单倍体,英文:Haplomino,或者直接叫“cell”也行,也有称为“Monomino”,而用两个及以上的单倍体拼接成的图形有个总称:多联骨牌(Polyomino)。

       数学中对多联骨牌的研究并没有现在那些休闲玩法那般花俏,不过呢,也算是把它当作游戏看待吧。比如将一幅五联骨牌(共12个)与一个2×2的正方形拼成8×8的大正方形,专业点的叫“密铺问题”,通俗点就是“拼图游戏”。那么,我在这里提个小问题:五种四联骨牌各一块能否拼成一个5×4的矩形呢?(我觉得答案很简单,大家可以在评论区留言说说想法吧)

       大家有没有注意到我说四联骨牌有5种呢?在这儿肯定有人会说:俄罗斯方块不是7种吗?还有名字呢:I,O,T,L,J,S,Z。这个没有错,因为在俄罗斯方块中,L与J,S与Z是互为左右手性的,即两者虽然全等,但在平面上不能用翻转以外的变换达到完全重合,游戏里也会因为手性的不同而产生不同的效果,所以在游戏中才将之完全区分开,但在数学问题里,除了特别规定考虑手性,其余时候都是无视手性的区别的(拓扑学的眼光),即四联骨牌就是如下五种:

好了,本篇专栏就此水完,大家下期再见(ಥ ಥ)。什么?!太水了?我就是在水专栏啊(ಡωಡ),啊咧?掉粉警告?(っ °Д °;)っ别走别走,我还能说

      上面我们提到,四联骨牌有5种,五联骨牌有12种,而单倍体,二联,三联的骨牌种类很好列举,分别是1,1,2种,而如果零个单倍体也算一种的话,由此我们得到了这样一个数列:

1,1,1,2,5,12……

       大家可以在OEIS里查到这个数列哦,这个数列的代号为:A000105

OEIS全称为:The On-Line Encyclopedia of Integer Sequences™,是一个关于整数序列(数列)的专业型网站(全英文版,可我只认得数字QAQ)

通过这个网站,我们就可以查到这个数列的后续多项:
A000105:Number of free polyominoes (or square animals) with n cells.(渣渣英语翻译:具有n个方格(细胞)的多联骨牌(或方格生物)的数量)
1,1,1,2,5,12,35,108,369,1285,4655,17073,63600,238591,901971,3426576,13079255,50107909,192622052,742624232,2870671950,11123060678,43191857688,168047007728,654999700403,2557227044764,9999088822075,39153010938487,153511100594603…
那么由这个数列可知,六联骨牌的数量为35个,放图:

至于那108个七联骨牌我就不列了(画图要时间啊),但这108个中有一个非常特殊,大家猜的出来吗?而且由于n≥7的骨牌都具有这种特殊的骨牌,于是数学家们还特别排除了这种骨牌并列出了另一组数列:A000104
Number of n-celled polyominoes without holes.
1,1,1,2,5,12,35,107,363,1248,4460,16094,58937,217117,805475,3001127,11230003,42161529,158781106,599563893,2269506062,8609442688,32725637373,124621833354,475368834568,1816103345752,6948228104703…
       讲到这儿,想必大家已经想到这种特殊的骨牌具有什么特点了:骨牌的内部有孔洞,所谓孔洞,即若骨牌将平面分成了不相通的两个或两个以上的区域中,在骨牌内部的区域(当然顾名思义大家都懂,但毕竟我要找一个数学方面的定义嘛),我还是上个图吧:

图为唯一一个具有孔洞的七联骨牌,①为孔洞,②为外部区域

至于有孔洞的八联骨牌则有6个,九联有37个,十联有195个,就是拿A000105的数列减去A000104对应项后得到的数列,数列代号为A001419,大家若感兴趣可以去查一下。既然大家已经了解了关于多联骨牌孔洞的一些小知识,我不妨再多说一点吧:之前我在孔洞的定义里提到,孔洞的个数不止一个,那么大家知道最小拥有n个孔洞的多联骨牌分别是多少呢?
n=1时,就是七联骨牌,我就直接令骨牌单元数为d,即:n=1,d=7;那么n=2呢?大家试着在草稿纸上画一画吧,此时d=11;然后就是:n=3,d=14;n=4,d=17;接下来不要认为n=5时d=20哦,事实上此时d=19,大家试着找找看这个骨牌是什么样的。再接下来就是:n=6,d=23;n=7,d=25;n=8,d=28;到此为止,后面我也不得而知,是没有找到呢?还是找到了但没记录进来?反正数列A118797从第八项就戛然而止,希望接下来的发现能够交给大家吧。

       讲了这么多多联骨牌关于数的方面的趣事,接下来我们从图的方向继续吧,别忘了多联骨牌本就是作为拼图而诞生的,所以几何的问题我不能不提,对吧?(以下内容均来源于百度(ಡωಡ)

       早些时候,我买了个拼图,名字叫“伤脑筋十三块”,这个拼图由12个不重复的五联骨牌与一个正方形的四联骨牌组成,而其整体外框是一个8×8的正方形(国际象棋的棋盘)。据估计,这个拼图或许有10000种以上的解法,大家有没有兴趣试一试啊,以下是我认为最漂亮的解法:

是不是感觉非常的对称

       大家注意到了吗?这种拼法使得那块正方形的四联骨牌的位置正好在正中间,而且左右两边既对称,也中心对称。事实上,把四联骨牌放在正中间的拼法不止这一种,以下还有两种拼法:

我觉得你们会问了:“这只是四联骨牌在正中心时的解法,那么如果其不在中心,而在8×8棋盘的任意地方,是否都有解法呢?”答案是肯定的,英国数学家道森证明:把正方形四联骨牌放在棋盘任意位置都可有解。(要不要我每个都给一种啊?算了吧,拖得够久了(ಡωಡ)
当然,在同样的棋盘里,我们拿掉那块正方形的四联骨牌,将其分解成四个小格,也会有很多的艺术图案哦,比如说将四个小格放在四个角落处:

除了把这些五联骨牌拼进8×8的棋盘中,还有其他的趣味题目:
一,将十二个五联骨牌拼成6×10,5×12,4×15,3×20的矩形。

例一

二,将十二个五联骨牌分成两份,并拼成两个全等的矩形。

例二

三,基于第二个问题,同样是将十二个五联骨牌分成数量相等的两份,不过这次的问题是:将其任意分组,都要拼成两个全等的图形。
四,三倍体问题:从十二个五联骨牌中随便选一个,再从剩下的十一个骨牌中挑出九个,拼成开始选中的骨牌三倍大的样子。

例四 三倍体的X与W

五,阶梯拼图:将十二个五联骨牌随机拿掉一个,然后用剩下的十一个骨牌拼成一个阶梯状的图案。

例五 X,T,Z阶梯

以上就是五联骨牌在平面中的拼图游戏,当然把每个小正方形换成小立方体后,就可以在空间上进行三维拼图了,立体的五联骨牌可以拼成3×4×5的长方体,不过我们这次还是来只讨论平面上的拼图吧。上面是五联骨牌,下面就讲六联骨牌吧:
六,我们之前提到了六联骨牌一共有35个,那么总共就有35×6=210个单倍体,你们一定会以为接下来的问题就是:用全部的六联骨牌拼成14×15的矩形吧?可惜这是不可能的,理由如图:

将所有的六联骨牌按上图方式染上黑白两色后,统计每块骨牌中黑白块的个数差,我们发现,其中有些骨牌的黑白块个数不等,都为2,即要么黑块比白块多两个,要么就少两个,如果仅仅是这样,还可以通过两个骨牌来消除这种个数差,但问题在于,两色块数不等的骨牌有11个,即总有一个无法通过其他的骨牌来消除这两个个数差,结果就是,由所有的六联骨牌拼出来的图案,黑白两色的块数无法相等,但14×15的矩形通过这样的交叉染色后,黑白两色是相等的,由此导出矛盾,所以不能用所有的六联骨牌拼出14×15的矩形,同理,如10×21,7×30,6×35,5×42等矩形都无法拼出来了。下图是我所找到的最接近矩形的拼法了:

例六(伪)放不进啊,逼死强迫症啊

那么有什么规整的图案可以拥有这种个数差呢?有,就基于上面这个14×15的矩形,将每一行都向右平移一个小块,形成一个台阶样的图案,就类似于由两个上面的阶梯图案拼合而成的样子:

例六(真)嗯,很完美,治愈一下上张图带来的强迫症暴击

七,咱们回到矩形的问题上来,虽然我们证明了填满矩形是不可能的,但我们可以构造特定的矩形来达成目的,比如在矩形的中心挖掉一个特定形状的空洞,比如210+5×9=255=15×17:

例七(一)十字架孔洞

当然,还有210+3×5=225=15×15:

例七(二)矩形孔洞

八,这个问题源自于上面我们提到的五联骨牌的三倍体问题,毕竟六联骨牌总共有35个,自然让我想到了1+9+25,然后我就想,是否可以从35个六联骨牌中选出一个,然后用剩下的34个骨牌拼成选出来的骨牌的三倍大与五倍大的样子?事实上我们通过之前提到的交叉染色法,可以很容易的排除掉那24个两色块数相等的骨牌,但还有11个骨牌无法排除,期待大家的解决哦。

        以上就是利用多联骨牌进行的最基础的拼图问题,为什么说是最基础的呢?因为接下来要讲一些更深更难的拼图问题了呢。 
        不过在这之前,我要先提一位博客大神:Matrix67,这位大神可是写了十年的数学博客,而且每一篇博客都是数学趣题,大家若感兴趣,可以上百度查一下,毕竟以下的问题都是从他的博客中提取的(・∀・)ノ。

九,用相同形状的多联骨牌拼接完全对称图形(这个问题由数学家Claudio Baiocchi提出
       所谓的完全对称图形,指的是同时满足三种对称性质的图形(那三种?1.轴对称 2.中心对称 3.旋转对称),由于我们的多联骨牌都算是“方方正正”的,那么我们可以简单的认为:由同一种多联骨牌拼出的图形要有四条对称轴(水平、竖直、对角线两条)。
单联骨牌(单倍体)自身就是完全对称的:

例九(一)

二联骨牌(多米诺骨牌)就用两个拼成一个正方形:

例九(二)

三联骨牌有两种,我接下来就只放图吧:

例九(三)

四联骨牌(俄罗斯方块):

例九(四)

接下来,根据已经找到的解来看,所有的五联与六联骨牌也可以拼出完全对称图形,在此我就不放图了,留给大家来拼拼看吧,有兴趣钻研的话,试试那108个七联骨牌是否也全都能拼出完全对称图形吧。
十,上面我们提到了轴对称图形,接下来我们就继续这个话题,不过这次我们要附加一些限制条件了:1.必须要用奇数个相同的多联骨牌;2.拼出来的图形必须左右对称。
由于某些骨牌自身就是左右对称的,所以这道题事实上针对的是那些不左右对称的骨牌。当然,有些骨牌是没有解的,比如六联骨牌中的“h”形骨牌,证明方法仍然可以用到上面的交叉染色法,大家就试着自己解决一下吧。
但有趣的是,这道题对所有的五联骨牌都是有解的,大家找的出来吗?

好了,以上十题就是我想与大家分享的多联骨牌几何(拼图)趣题,至于将不同的n联骨牌组合起来拼一个大型的艺术图案,恕我还达不到那种境界,下面是一位牛人用单联到七联组合拼成的钟表盘面:

12个五联骨牌正好分布在圆盘周围12个间距相当的地方,其中5和10的位置分别用罗马数字V和X表示,9和12则用英文首字母N和T表示。圆盘中间是一联、二联、三联、四联骨牌,外围是35个六联骨牌,再外面则是107个七联骨牌。第108个七联骨牌——中间有一个空洞的特殊骨牌,则被放在了整个圆盘的正中间

还有一个加强版:

相比于上面,多了369个八联骨牌
以上选自:http://www.matrix67.com/blog/archives/1163

       这里让我再提一点,我们上面所说的多联骨牌都是由正方形小方块组成的,而因为正方形具有密铺的性质,从而产生了这么多的拼图趣题。但我们知道,能够密铺的正多边形可不止正方形一种哦,还有正三角形与正六边形,而其对应的“骨牌”名称叫做“多联钻石”与“多联蜂窝”,我在这里就只特别地提一下六联钻石吧,其与五联骨牌一样拥有十二个不同的形状,可以拼出的图案种类也颇多,感兴趣的话可以试着做一副玩玩,挺有趣的哦。

六联钻石造型之一

       OK,最后的最后,让我把之前欠下来的那张“证明”补上吧,别再说我又拖又水了啊,画图要时间的啦!(  ̄3 ̄)

正方形四联骨牌在8×8棋盘的任意位置的解(非固定解)


投诉或建议
推荐文章
更多精彩内容
上海科技大学提出了个新的多传感器数据集,经过完全同步和精确标定,包括多种挑战性的
以下内容来自小六的机器人SLAM学习圈知识星球每日更新内容点击领取学习资料 机器人SLAM学习资料大礼包#论文##开源数据集# VECtor: A Versatile Event-Centric Benchmark for Multi-Sensor SLAM论文地址:https://arxiv.org/abs/2207.01404作者单位:上海科技大学数据集地址:https://star-datasets.github.io/vector/ 事件相机最近越来越受欢迎,因为它们具有强大的潜力,可以在高动态或
硬核战双93文案
塔纳托斯,是古希腊神话中的死神,罗马神话中名为Mors。他是睡神修普诺斯的孪生兄弟,其母为黑夜女神尼克斯,两兄弟一起生活于冥界。另有一说是,他是丘比特(即罗马神话中的厄洛斯)的分身。他经常拿着一个倒置的火炬(倒置地握在手中),代表一个熄灭的生命。通常在艺术作品中,比如古希腊瓶画,塔纳托斯的形象是一个长着翅膀、有着胡须的年纪大的男人,但有时也会被画成一个小孩或没有胡子的年轻男人。他有时会戴着头盔。但是也有的说他是一位银发,手持宝剑的美少年,而且有着深色的翅膀。他通常与他的弟弟一起运送死人的躯体。这种差别来自
硬核战双58文案
物理三大定律:质量守恒定律,电荷守恒定律,能量守恒定律不过因为有质能方程式((E=mc^2),所以说是质量—能量守恒会更好,因为在一些特殊且较真的情况下单考虑质量或能量时,它们是不守恒的把发掘区划分为若干相等的正方格,依方格为单位,分工发掘,这些正方格叫“探方”。探方法的分布方法是;先在选定的发掘区域,划好方格网,在每个十字线交叉点打下1根木橛。方格的大小,依遗址文化堆积的厚度而定。探方法适合于发掘整片遗址,优点较多,是最常用的发掘遗址的方法。成分:主体、隔梁、关键柱步骤:辨识、挖掘、揭露、收集、记录探方
评论