逻辑与策略 · 染色模型

染色与覆盖论证

把“怎么铺”换成“每块必须盖哪些颜色”,用总数量的矛盾否定覆盖。

下载视频 ↗
01

只少两格,为什么铺不了?

有一张8×8单位方格棋盘,去掉左上角(1,1)与右下角(8,8)。能否用31块1×2骨牌盖住其余62格?骨牌可横放或竖放,但必须沿格线,不重叠、不越界、不留空格。

有限步演示 · 检查每块砖的限制

深浅深浅深浅深浅浅深浅深浅深浅深深浅深浅深浅深浅浅深浅深浅深浅深深浅深浅深浅深浅浅深浅深浅深浅深深浅深浅深浅深浅浅深浅深浅深浅深

步骤1/5:先看完整8×8棋盘。深浅各32格。

8×8缺对角 · 骨牌

深 32浅 32

这两个数对应左侧完整棋盘;接下来标出骨牌与移除的格子。

格内文字或数字同时标识颜色。模式切换会回到第一步,末步停止;重置可从头演示。

02

学习准备与适用条件

目标:能自行设计染色,说明一块砖的颜色结构,再把局部限制累加成整体限制。前置:奇偶性、余数、单位方格面积,以及“假设成立 → 推出矛盾”的反证思路。

覆盖指所有目标格恰好被盖一次。必须先写清砖的形状、允许方向、能否翻转、是否沿格线。条件改变后,要重新检查每块砖的颜色数。

本页按项目S班深度编排,非官方年级课纲。例题与练习为自拟教学题;研究的是格点离散覆盖,不讨论任意角度放置或切割砖。

03

为什么颜色能形成限制?

双色:每块相同,累加仍然相同

将行、列从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. 明确区域与允许的砖。
  2. 选择能约束每块砖的染色。
  3. 证明每块砖无论如何摆都符合限制。
  4. 统计区域各色数量。
  5. 数量矛盾则否定;没有矛盾则继续构造或寻找更强限制。
04

两道完整例题

例题一|8×8棋盘去掉同色对角

题意:去掉(1,1)、(8,8),是否可用1×2骨牌沿格线覆盖其余区域?允许横放、竖放,不重叠、不越界。

  1. 原棋盘每行深浅各4格,总数各8×4=32格。
  2. 两个被移除的格子行列和分别为2、16,都是偶数,故都是深格。
  3. 剩余深格32−2=30,浅格32格;面积62格,若可铺须用62÷2=31块。
  4. 31块骨牌应覆盖深浅各31格,与30、32矛盾。

答案:不可能。单有面积偶数还不够;关键是每块骨牌的配色不能变。

例题二|面积是3的倍数,仍铺不满

题意: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整除,仅通过了面积条件。

05

迁移练习

练习一|去掉异色格,就一定可铺吗?

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缺角与直三格砖

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),与实际矛盾,故不可能。

06

反例、易错与回顾

两色相等仍可能铺不了

只保留下列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块骨牌铺满。

1,22,12,23,24,24,34,45,3

必要条件:可铺 ⇒ 颜色数量符合限制。不能反推“数量符合 ⇒ 可铺”。证明可铺时,可直接展示一个完整铺法并核对覆盖条件。

回顾:区域的颜色总量,必须能由合法砖的颜色结构累加得到。用矛盾否定,用构造肯定。

07

逐章回看

点击标题可定位到视频中的相应讲解,文字稿默认展开。

八乘八棋盘去掉左上角和右下角,能用一乘二骨牌铺满吗?先给相邻格染成深浅两色。

每块骨牌只能沿格线覆盖相邻两格。无论横放还是竖放,都恰好盖住一个深格和一个浅格。

原来两色各三十二格。去掉的两个对角格都是深色,剩下深色三十格,浅色三十二格。

六十二格需要三十一块骨牌。可三十一块只能盖住深浅各三十一格,与剩余数量矛盾,所以不可能。

换成直三格砖,可以用三种颜色。行列从零编号,让每格的颜色由行号加列号除以三的余数决定。

向右或向下走一格,颜色依次轮换。因此任意横放或竖放的直三格砖,都恰好覆盖三色各一格。

四乘四棋盘去掉第一行第二列后,三色分别剩六、四、五格。五块砖却需要每色五格,因此也铺不满。

染色论证的关键是每块覆盖的颜色数量。数量矛盾能证明不可能;数量符合,还需要具体铺法或进一步证明。