例题一|8×8棋盘去掉同色对角
题意:去掉(1,1)、(8,8),是否可用1×2骨牌沿格线覆盖其余区域?允许横放、竖放,不重叠、不越界。
- 原棋盘每行深浅各4格,总数各8×4=32格。
- 两个被移除的格子行列和分别为2、16,都是偶数,故都是深格。
- 剩余深格32−2=30,浅格32格;面积62格,若可铺须用62÷2=31块。
- 31块骨牌应覆盖深浅各31格,与30、32矛盾。
答案:不可能。单有面积偶数还不够;关键是每块骨牌的配色不能变。
逻辑与策略 · 染色模型
把“怎么铺”换成“每块必须盖哪些颜色”,用总数量的矛盾否定覆盖。
视频加载失败,请确认assets文件夹完整,或直接打开MP4。正文仍可阅读。
有一张8×8单位方格棋盘,去掉左上角(1,1)与右下角(8,8)。能否用31块1×2骨牌盖住其余62格?骨牌可横放或竖放,但必须沿格线,不重叠、不越界、不留空格。
有限步演示 · 检查每块砖的限制
步骤1/5:先看完整8×8棋盘。深浅各32格。
这两个数对应左侧完整棋盘;接下来标出骨牌与移除的格子。
格内文字或数字同时标识颜色。模式切换会回到第一步,末步停止;重置可从头演示。
目标:能自行设计染色,说明一块砖的颜色结构,再把局部限制累加成整体限制。前置:奇偶性、余数、单位方格面积,以及“假设成立 → 推出矛盾”的反证思路。
覆盖指所有目标格恰好被盖一次。必须先写清砖的形状、允许方向、能否翻转、是否沿格线。条件改变后,要重新检查每块砖的颜色数。
本页按项目S班深度编排,非官方年级课纲。例题与练习为自拟教学题;研究的是格点离散覆盖,不讨论任意角度放置或切割砖。
将行、列从1开始编号。r+c为偶数染深色,奇数染浅色。相邻格的r+c恰好相差1,因此颜色相反。任何骨牌盖两格,所以必定是“一深一浅”。
若铺了k块骨牌,则深格数D=k,浅格数L=k,因此D−L=0。
这是对所有可能铺法的限制。无需枚举骨牌怎么摆。区域若D≠L,就不可能被这些骨牌完整覆盖。
三色染色单独将行、列从0开始编号(题目坐标仍从1开始)。把r+c除以3的余数0、1、2作为三种颜色的编号。横向或纵向连续三格的编号依次轮换,恰好各出现一次。注意:不是任意三格砖都成立,例如L形三格砖可能有两个相同余数。
若用k块直三格砖铺满,则N₀=N₁=N₂=k。
更一般地,若每块允许的砖在颜色j上固定覆盖aⱼ格,k块砖就必须覆盖k×aⱼ格。若允许多种颜色结构,要分析它们能否组合出目标数量,不能直接要求各色相等。
题意:去掉(1,1)、(8,8),是否可用1×2骨牌沿格线覆盖其余区域?允许横放、竖放,不重叠、不越界。
答案:不可能。单有面积偶数还不够;关键是每块骨牌的配色不能变。
题意:4×4棋盘去掉第一行第二列(1,2),其余15格能否用5块1×3直三格砖铺满?砖只可沿格线横放或竖放,不能切割、重叠或越界。
按从0开始的行列编号之和除以3取余,四行颜色编号依次为:0 1 2 0、1 2 0 1、2 0 1 2、0 1 2 0。原有N₀=6、N₁=5、N₂=5。题目中的(1,2)对应0起始编号(0,1),颜色为1;移除后剩余N₀=6、N₁=4、N₂=5。
5块直三格砖每色必须各覆盖5格,但实际是6、4、5,矛盾。答案:不可能。面积15可以被3整除,仅通过了面积条件。
6×6棋盘去掉相邻两格(1,1)、(1,2),其余34格能否用1×2骨牌横竖铺满?请给出铺法,而非只检查颜色。
原来深浅各18格,去掉一深一浅,剩余各17格,颜色条件符合,但这一步还没有证明能铺。
给出构造:第一行剩下第3至第6列,用两块横骨牌覆盖(1,3)-(1,4)、(1,5)-(1,6)。其余五行各用三块横骨牌,分别覆盖第1-2、3-4、5-6列。总数2+5×3=17块,不重叠、无遗漏,因此本题可铺。
5×5棋盘去掉(1,1),剩余24格能否用8块1×3直三格砖沿格线横竖铺满?使用从0开始的行列编号之和除以3的余数染色。
逐行统计,原棋盘(N₀,N₁,N₂)=(8,9,8)。去掉题目坐标(1,1),即0起始编号(0,0)这一余数0格,变为(7,9,8),总数24。每块直三格砖恰好各色一格,8块应为(8,8,8),与实际矛盾,故不可能。
只保留下列8格:(1,2)、(2,1)、(2,2)、(3,2)、(4,2)、(4,3)、(4,4)、(5,3)。其余格不存在。这个区域连通,深浅各4格,但(1,2)与(2,1)在区域内都只有一个邻格(2,2)。要覆盖它们,各自的骨牌都必须占据(2,2),必然重叠。因此无法用4块骨牌铺满。
必要条件:可铺 ⇒ 颜色数量符合限制。不能反推“数量符合 ⇒ 可铺”。证明可铺时,可直接展示一个完整铺法并核对覆盖条件。
回顾:区域的颜色总量,必须能由合法砖的颜色结构累加得到。用矛盾否定,用构造肯定。
点击标题可定位到视频中的相应讲解,文字稿默认展开。
八乘八棋盘去掉左上角和右下角,能用一乘二骨牌铺满吗?先给相邻格染成深浅两色。
每块骨牌只能沿格线覆盖相邻两格。无论横放还是竖放,都恰好盖住一个深格和一个浅格。
原来两色各三十二格。去掉的两个对角格都是深色,剩下深色三十格,浅色三十二格。
六十二格需要三十一块骨牌。可三十一块只能盖住深浅各三十一格,与剩余数量矛盾,所以不可能。
换成直三格砖,可以用三种颜色。行列从零编号,让每格的颜色由行号加列号除以三的余数决定。
向右或向下走一格,颜色依次轮换。因此任意横放或竖放的直三格砖,都恰好覆盖三色各一格。
四乘四棋盘去掉第一行第二列后,三色分别剩六、四、五格。五块砖却需要每色五格,因此也铺不满。
染色论证的关键是每块覆盖的颜色数量。数量矛盾能证明不可能;数量符合,还需要具体铺法或进一步证明。