逻辑模型
浙江大学数学建模基地
§ 9 逻辑模型
欧几里得在不加证明而被直接采用的一些基本概念和
公理的基础上。运用逻辑推理方法得出了一系列的定理、
推论，从而建立了完整的欧几里得几何学，这一辉煌成果
至今仍然是人类的宝贵财富。
本章介绍的一些模型采用的也是类似的方法。建模者
从问题应当具有的某些基本属性出发，运用逻辑推理方法
或者导出满足这些基本属性的解来，或者证明在原有观念
下问题不可能有解，从而从根本上改变人们对这一问题的
看法
§ 9.1 几个较为简单的问题
本节将采用逻辑推理方法讨论几个颇为有趣的问题。
例 1 在每一次人数不少于 6人的聚会中必可找出
这样的 3人，他们或者彼此均认识或者彼此均不
认识 。
利用 图的方法 来描述该问题。将人看成顶
点，两人彼此都认识用实线连，否则虚线。
证明：
相识问题 （ 拉姆齐问题 ）?
问题转化为在一个 6阶图中必存在实线三角
形或虚线三角形。
请大家一起画图证明
υ2 υ1
υ3
υ4
υ6
υ5
2
3
4
任取一顶点，不妨 υ 1
考察 υ2υ3,υ2υ4和 υ3υ4
υ2υ3,υ2υ4和 υ3υ4只能是虚线,否则得证
但这样三角形 υ2υ3υ4的三边均为虚线
不妨取 υ1υ2, υ1 υ3, υ1 υ4 实线
与 υ 1相连的边必然有：
实线条数不小于 3或虚线条数不小于 3
拉姆齐问题也可这样叙述,6
阶 2色完全图中必含有 3阶单色
完全图。
其他类似可推出的结果,
命题 11.1 任一 6阶 2色完全图中至少含有两个 3阶单色完全图。
证明,前面证明必存在 3阶单色完全图，不妨设 υ 1υ 2υ 3
为红色完全图
υ1υ5,υ2υ5,υ3υ5中至少有两条黑色、故 υ1υ5
与 υ2υ5中至少有一条是黑色
若 υ4υ5υ6也是红色三角形，命题已得证
故至少一边与 υ1υ2υ3的边异色，不妨设 υ4υ5黑色
υ1υ4,υ2υ4,υ3υ4至少应有两条黑色，不妨设
υ1υ4, υ2υ4 黑色
所以存在第二个 3阶单色完全图。
υ2 υ1
υ3
υ4
υ6
υ5
命题 11.2 7阶 2色完全图至少含有 4个 3阶单色安全图 。
命题 11.3 18阶 2色完全图中必含有 4阶单色完全图。
对拉姆齐问题的认识不能仅仅停留在
例 11.1的水平上。利用逻辑推理方法，
实际上还可获得一大批结果。命题 11.2
和命题 11.3的证明留给大家自己去完成。
例 2 17位学者中每人都和其他人通信讨论 3个方向的课题。
任意两人间只讨论其中一个方向的课题，则其中必可找出 3
位学者，他们之间讨论的是同一方向的课题。
证明
将每一学者看成一个顶点，作一个 17 阶完
全图。 按讨论课题的方向对边染色，相同方向染
成同一颜色，得到一个 17 阶 3 色完全图。
任取一顶点 A,与它相关联的有 16 条边，
其中必能找出 6 条相同颜色的边，不妨设 A 与
υ
1
，…,υ
6
的连线有相同颜色。 连接 A 和 6 个
顶点υ
1
，…，υ
6
。如果这 6 个顶点间也有这种
颜色的边，则已找到讨论同一方向课题的三位学
者；否则，υ
1
，…，υ
6
及连接它们的边构成一
个 6 阶 2 色完全图，由例 1,必可从中找到一个
3 阶单色完全图，即找出三位讨论同一方向课题
的学者 。
奇偶数校验及相关问题?
q
p2 ?
证明,
采用反证法, 设, 其中 p,q互素, 则有
p2=2q2。 因为 2|p2,故 2|p。 记 p=2p1,可得 4p12=2q2,即
2p12=q2, 故又有 2|q,与 p,q互素矛盾 。
例 3 证明 是无理数。2
同样方法可以证明：若 m是大
于 1的素数,n是大于 1的整数，
则 必为无理数。n m
例 4 拟用 40块方形瓷砖铺设如下图所示的地面，但商店只
有长方形瓷砖，其大小为方形的两块。问购买 20块长方形瓷
砖后，是否可能不裁开而直接铺好地面？
解 将图 11.4中的 (a) (b)黑白相间染色。
显然，如长方形瓷砖不裁开，只能用来复盖相
邻的两格，故复盖的两格必为一白一黑。
下图 (a)中共有 21个黑格和 19个白格，故不可能
直接铺好，下图 (b)中黑白格各为 20个，大家很
容易找到直接铺设的方法。
图 (a) 图 (b)
例 5 设一块 m× n的棋盘被若干个形如 的板块恰好
盖满，试证明 m× n必能被 8整除。
证明,
显然有 4|m× n，故 m,n中至少有一个为偶数，不妨
设 n为偶数，将棋盘按列黑白相间染色，如下图 (a )
所示，由于 n为偶数，黑、白列的数目相同，故黑白
格数相同，设各为 2k个。
图 (a)
板块可以有许多种拼凑法，但容易看出，每一板块放
置的方向（称之为定向）只有八种可能的选择，如下
图 (b)所示。
图 (b)
容易看出，不论按什么方向放置板块，每一板块均盖住
奇数个黑格（ 1格或 3格），故盖住棋盘的板块必有偶数
个，从而,m× n的棋盘必能被 8整除。
图 (a)
例 6 拟将一批尺寸为 1× 2× 4的的商品装入尺寸为 6× 6× 6
的正方体包装箱中，问是否存在一种装法，使装入的该商品
正好充满包装箱。
解 将正方体剖分成 27个 2× 2× 2的小正方体，并
按下图所示黑白相间地染色。
再将每一 2× 2× 2的小正方体剖分成 1× 1× 1的
小正方体。
易见,27个 2× 2× 2的正方体中，有 14个是黑的，
13个是白的（或 13黑 14白），故经两次剖分，
共计有 112个 1× 1× 1的黑色小正方体和 104个
1× 1× 1的白色小正方体。
虽然包装箱的体积恰好是商品体积的 27倍，但
容易看到，不论将商品放置在何处，它都将占
据 4个黑色和 4个白色的 1× 1× 1小正方体的位置，
故商品不可能充满包装箱。
德国著名的艺术家 Albrecht Dürer(1471-1521)
于 1514年曾铸造了一枚名为,Melencotia I”的铜
币。令人奇怪的是在这枚铜币的画面上充满了数
学符号、数字及几何图形。这里，我们仅研究铜
币右上角的数字问题
Dürer魔方 （ 或幻方 ） 问题?
所谓的魔方是指由 1~n2这 n2个正整
数按一定规则排列成的一个 n行 n列
的正方形 。 n称为此魔方的阶 。
Dürer魔方, 4阶，每一行之和为
34，每一列之和为 34，对角线
（或反对角线）之和是 34，每个
小方块中的数字之和是 34，四个
角上的数字加起来也是 34
什么是 Dürer魔方
多么奇妙的
魔方！
铜币铸造时间,1514年
构造魔方是一个古老的数学游戏，起初它
还和神灵联系在一起，带有深厚的迷信色彩。
传说三千二百多年前（公元前 2200年），因治
水出名皇帝大禹就构造了三阶魔方（被人们称
“洛书”），至今还有人把它当作符咒用于某
些迷信活动，大约在十五世纪时，魔方传到了
西方，著名的科尼利厄斯 ·阿格里帕（ 1486-1535）
先后构造出了 3~9阶的魔方 。
如何构造魔方
奇数（不妨 n=5）阶的情况
Step1,在第一行中间写 1
Step2,每次向右上方移一格依次填按由小到大排列的下
一个数，向上移出界时填下一列最后一行的小方格；向
右移出界时填第一列上一行的小方格。若下面想填的格
已填过数或已达到魔方的右上角时，改填刚才填的格子
正下方的小方格，继续 Step2直到填完
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
偶数阶的情况
偶数阶的魔方可以利用奇数
阶魔方拼接而成，拉尔夫 ·斯特雷
奇给出了一种拼接的方法,这里
不作详细介绍
五阶 没人知道有多少个！！！
三阶 1个 反射和中心旋转生成 8个
四阶 880个 反射和中心旋转生成 7040个
魔方数量随阶数 n增长
的速度实在是太惊人了！
同阶魔方的个数
允许构成魔方的数取任意实数
允许取实数
n阶魔方 A,B，任意实数 α, β
αA+βB 是 n阶魔方
具有指定性质的魔方全体构成一个线性空间
问题已发生了实质性变化
注：刻画一个线性空间只需指出它的维数并求出
此线性空间的一组基底
松驰问题的讨论
1在第一行中共有 4种取法，为保持上述
性质的成立，第二行中的 1还有两种取法。当
第二行的 1也取定后，第三行与第四行的 1就完
全定位了，故一共可作出 8个不同的最简方阵，
称之为基本魔方并记之为 Q1,…, Q8
仍以 4阶方阵为例 。
令 R为行和, C为列和, D为对角线和, S为小方块和
定义 0-方,R=C=D=S=0
定义 1-方,R=C=D=S=4
R=C=D=S=1的方阵构成的线性空间具有什么样的性质？
类似于构造 n维欧氏空间
的标准基，利用 0和 1我们
来构造一些 R=C=D=S=1
的最简单的方阵。
?
?
?
?
?
?
?
?
?
?
?
?
?
0010
1000
0100
0001
1
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0100
0010
1000
0001
2
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0010
0100
0001
1000
3
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0100
0001
0010
1000
4
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
1000
0010
0001
0100
5
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
1000
0001
0100
0010
6
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0010
0100
7
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
0100
1000
0010
8
Q
显然,Dürer空间（简称 D空间）中任何一个元素都
可以用 Q1,Q2,…, Q8来线性表示，但它们能否构
成 D空间的一组基呢？
是否线性无关？821,,,QQQ ?
容易看出：
076328541 ???????? QQQQQQQQ
Q1,…, Q8这 8个基本方是线性相关的，即至少存在一个 Qj，可
以通过其它 7个基本方的线性组合得到。这 8个基本方的地位是等
同的，故可不妨设 j=8。下面验证 Q1,Q2,…, Q7是否线性相关。
0
7
1
??
?i
iiQr
令：,即
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
???
6542317
7135264
2617453
4375621
rrrrrrr
rrrrrrr
rrrrrrr
rrrrrrr
?
?
?
?
?
?
?
?
?
?
?
?
0000
0000
0000
0000
=
等号两边对应元素相比较,得 r1=r2=…=r 7=0，
所以 是 线性无关
721,,,QQQ ?
721,,,QQQ ?
是 D空间的最小生成集。
令 D
即解方程组：
772211 QdQdQd ??? ????
?
?
?
?
?
?
?
?
?
?
?
?
114155
12769
811105
132316
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
???
6542317
7135264
2617453
4375621
ddddddd
ddddddd
ddddddd
ddddddd
=
解得
D=
7654321 5336788 QQQQQQQ ??????
研究 Albrecht Dürer铸造的铜币
D空间的子空间和 D空间的扩展
（ 1） 要求数字方的所有数都相等
这是集合 G={rE,r∈ R}，
G是以 βG={E}为基的一维向量空间
（ 2） 要求列, 行及每条主, 付对角线上各和都相等 。
得到 5维泛对角方的向量空间 B。 例如：
它的基 BB为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
127261
216712
3221116
1611217
P
H=N=R=C=46
其中 H为主对角线和，
N为付对角线和。
进一步讨论
?
?
?
?
?
?
?
?
?
?
?
?
?
1010
1010
0101
0101
1
P
?
?
?
?
?
?
?
?
?
?
?
?
?
0110
1001
0110
1001
2
P
?
?
?
?
?
?
?
?
?
?
?
?
?
1001
0110
1001
0110
3
P
?
?
?
?
?
?
?
?
?
?
?
?
?
1010
0101
0101
1010
4
P
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0011
1100
0011
5
P
（ 3） 要求行和，列和及两条对角线上的元素和相等
得到 8维向量空间 Q。
基向量 QB={Q1,Q2,…, Q7,N0}，
其中 Q1,Q2,…, Q7是 D的基，而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0110
0000
0000
0110
0N 例如,R=C=D=30
?
?
?
?
?
?
?
?
?
?
?
?
?
9777
69105
75612
8976
T
（ 4） 仅要求行和与列和相等
得到 10维向量空间 ψ
基向量 ψB={Q1,Q2,…, Q7,N1,N2,N3}
其中 Q1,Q2,…, Q7是 D的基，而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
1001
1001
0000
1N
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0110
1001
0101
1010
2N
?
?
?
?
?
?
?
?
?
?
?
?
?
0100
1000
0001
0010
3N
（ 5） 对数字没任何要求
所有 4× 4数字方组成 16维向量空间 M
基向量 MB的元素应是标准基（即仅有一个
元素为 1，其余元素均为 0的阵）。
Botsch（ 1976年）证明了对于
1与 16之间的每一个数 K，都
存在 K维的 4× 4方的向量空间
由上可知，有下式成立,
（向量空间）
（维数） 0 1 5 7 8 10 16
? ? MQDBG ??????? 0
什么是拼方问题
在 H.E.Dudeney所写的, Cantebury
难题, 一书中有一个正方形的图案, 这
个正方形图案是由一个小长方形和若干
个边长各异的小正方形组成的 。 小长方
形的长为, 宽为, 要求求出所有正
方形的边长和拼接方法 。 这种拼接过程
称为拼方, 而这种类型的问题称为拼方
问题 。
4
110 41
拼方问题?
12
8
532
721/4
11/45/2
31/4
1
受上一问题的启示，加拿大数学家 W.T.Tutte,A.Stone
等人考虑了如下问题：
怎样的长方形可以剖分成若干个边长各异的小正方形？
正方形能否剖分成边长各异的小正方形？
称具有上述性质的长方形为 完美长方形,正方形
为 完美正方形 。
波兰数学家 Z.Moron 的工作
Z.Moron 在 W.T.Tutte等之前已经作出了
一个 9阶完美长方形，见右图 18
14
4
10
15
7
9
8
1Z.Moron的完美长方
形很接近完美正方形
Tutte等人用来分析 Moron给出例子的 奇特方法：
用点表示水平边，用边表示小正方形。边长即小正方
形之边长，方向规定由上到下。于是一个剖分好的完美长
方形被十分巧妙地转化成了一个有向图网络，见下图
1 x 2 x
3 x 4 x 5 x
6 x
7 x
8 x 9 x
除表示上、下两底边的顶点以外，
其余顶点处指入边边长之和应等
于指出边边长之和
A
B
C
D
E
F
1 x 2 x
3 x 4 x 5 x
6 x
7 x 8 x
9 x
1 x
7 x
3 x
由上面说明：假如我们把得
到的有向图网络看作电网络，
则所述性质恰好就是电学中
的基尔霍夫定律。
若将每边看成一个单位电阻，在给出正
极 A与负极 F之间的电势差后（相当于给
出长方形的高），即可求出每条边上的
电流强度（等于两顶点间的电势差），
而这些数恰好就是小正方形的边长。
此外还可看出，解应当是唯
一的，因为在给定 A,F间的
电势差后，各边上的电流强
度是唯一确定的。
分析 Moron给出的完美长方形，取高为 32，则相应电网络中
的电流强度 xi(i=1,…,9)应满足：
其解为：
（ x1,x2,x3,x4,x5,x6,x7,x8,x9)=(18,15,4,7,8,1,14,10,9)，
恰为相应小正方形的边长。此外，由 x1+x2=33可知，长方形
的宽应为 33。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
??
????
??
???
??
??
32
32
32
32
842
831
952
71
98721
965
8643
542
731
xxx
xxx
xxx
xx
xxxxx
xxx
xxxx
xxx
xxx
可以不管长方形的剖
分，直接根据图的各
种情况利用计算机来
搜查
前面分析是在对完美
长方形作了剖分的前
提下作出的，不知道
剖分情况怎么办？
几种最简单的情况及寻查过程的简要说明
有向图只有三条边的图见图 1。
由 x1= x3可知不存在 3阶完美长方形。
由四条边组成的有向图可以有两种形式，
见图 2中的（ a）,(b)，它们均不可能对
应完美长方形。
1 x
2 x
3 x
图 11 x
2 x
3 x
4 x
图 2（ b）
2 x1 x
3 x 4 x
图 2（ a）
逐阶寻查下去可发现，完美长方形对应的电网络必有以下性质
(性质 1) 除两端顶点外，其余各项点的进出边之和至少为 3。
(性质 2) 电网络不具有对称性。
根据这两条性质，可以发现
完美长方形的最小阶数为 9，
进而可作出各种 9阶,10阶、
11阶 … 完美长方形。
当然，随着阶数增大，计算
量将按指数增长，因为相应
电网络的数目是按指数增长
的。
几点说明,
对一个指定的有向图求相应的完美长方形时，高可以先随意
选取一个整数。求出所有小正方形的边长后再将所有数据同
乘一个适当的数，使所有有数据均化为整数。显然，变动长
方形的高所得到的剖分是相似的，在将相似看作等同的意义
下，这种剖分是唯一的。
Tutte等人将他们用人工方法得到的完美长方形列成了一个
表，其中包括有二百多个完美长方形。 1960年，人们用电
子计算机求得了 9至 15阶的全部完美长方形，可其中没有
一个是完美正方形！
是否存在完美正方形？
当求得的完美长方形的长恰好等于宽的十分巧合的情况下，
我们才能得到一个正方形的剖分。由于计算量过大，在计算机
上寻查并未获得成功，最早作出的正方形的剖分是基于非常复
杂的图形并用对称性人工凑出来的，它具有 69阶。后来又作出
了 39阶和 38阶的完美正方形。接着 Tutte等人利用他们获得的完
美长方形表又拼凑出一个 26阶的完美正方形，它是由一个边长
为 231的正方形和两个完美长方形拼合而成的，如图所示。
完美长方形
正方形 完美长方形
在此之前, 人们对图论还没有多少研究 。 Tutte等人在引入
网络图方法后, 十分自然地将兴趣转向了对图论的研究, 并
因此而获得了许多具有重大意义的开创性结果, 直接促进了
图论的发展 。
对偶理论?
对一个完美长方形也可用垂直线代替水平线，用类似方法
作出另一个有向图。所以对一个确定的完美长方形，我们
可以获得的两个不同的有向图。
1 x 2 x
3 x 4 x 5 x
6 x
7 x
8 x 9 x
c
a
b
d
e f
D
E
1 x 2 x
3 x 4 x 5 x
6 x
7 x
8 x 9 x
A
B
C
F
两个有向图是由同一个完美长方形得出的，它们之间必
然存在着某种密切的关系，这种关系被称为对偶关系。
在 A,F和 a,f之间各添加一条线段，对偶关系就显示出
来，添线后的网络称为拼方完美长方形的完全网或 C-网。
每一个 C-网将平面分割成若干个区域（称为面），而两
个互为对偶的 C-网是指具有如下性质的两个 C-网：可以
把它们画在平面上使任一个 C-网的每一面中有且仅有另
一个 C-网的一个顶点，见图。
A
B
C
D
E
F
a
b
c
d
e f
添加
添加
3-连通理论?
前面我们已经看到，由几个完美长方形可以拼出一个新的完美
长方形。相应地，新网络图与原有的完美长方形的网络之间存
在着十分密切的联系。应当看到这种拼合而成的完美长方形是
比较特殊的，它们与那些非拼合而成的（基本）完美长方形有
着重大的区别，这些区别必然会在图论中反映出来。例如，考
察由两个完美长方形拼接成的完美长方形，可以导出下述定义：
定义 11.1 一个连通图如可分成两部分，这两部分只有一个公
共顶点，且每一部分均含有另一部分所没有的顶点，则称此图
为可分离的。不可分离的图称为 2-连通图。
定义 11.2 一个 2-连通图若可被分成两部分，这两部分恰有两
个公共顶点，且每一部分均含有另一部分所没有的顶点，则称
此图为 2-可分离的,2-连通但非 2-可分离的图称为 3-连通图。
可分离图
2-可分离图
Tutte等人从着迷于一个数学游戏开始，而最终却成了研究
图论问题的专家创建了图的对偶理论,3-连通理论等。在他们
取得的极其丰硕的研究成果中，人们可以清晰地看到 丰富的想
象力, 敏锐的洞察力 和 严密的逻辑推理能力 得到了巧妙的结合。
浙江大学数学建模基地
§ 9 逻辑模型
欧几里得在不加证明而被直接采用的一些基本概念和
公理的基础上。运用逻辑推理方法得出了一系列的定理、
推论，从而建立了完整的欧几里得几何学，这一辉煌成果
至今仍然是人类的宝贵财富。
本章介绍的一些模型采用的也是类似的方法。建模者
从问题应当具有的某些基本属性出发，运用逻辑推理方法
或者导出满足这些基本属性的解来，或者证明在原有观念
下问题不可能有解，从而从根本上改变人们对这一问题的
看法
§ 9.1 几个较为简单的问题
本节将采用逻辑推理方法讨论几个颇为有趣的问题。
例 1 在每一次人数不少于 6人的聚会中必可找出
这样的 3人，他们或者彼此均认识或者彼此均不
认识 。
利用 图的方法 来描述该问题。将人看成顶
点，两人彼此都认识用实线连，否则虚线。
证明：
相识问题 （ 拉姆齐问题 ）?
问题转化为在一个 6阶图中必存在实线三角
形或虚线三角形。
请大家一起画图证明
υ2 υ1
υ3
υ4
υ6
υ5
2
3
4
任取一顶点，不妨 υ 1
考察 υ2υ3,υ2υ4和 υ3υ4
υ2υ3,υ2υ4和 υ3υ4只能是虚线,否则得证
但这样三角形 υ2υ3υ4的三边均为虚线
不妨取 υ1υ2, υ1 υ3, υ1 υ4 实线
与 υ 1相连的边必然有：
实线条数不小于 3或虚线条数不小于 3
拉姆齐问题也可这样叙述,6
阶 2色完全图中必含有 3阶单色
完全图。
其他类似可推出的结果,
命题 11.1 任一 6阶 2色完全图中至少含有两个 3阶单色完全图。
证明,前面证明必存在 3阶单色完全图，不妨设 υ 1υ 2υ 3
为红色完全图
υ1υ5,υ2υ5,υ3υ5中至少有两条黑色、故 υ1υ5
与 υ2υ5中至少有一条是黑色
若 υ4υ5υ6也是红色三角形，命题已得证
故至少一边与 υ1υ2υ3的边异色，不妨设 υ4υ5黑色
υ1υ4,υ2υ4,υ3υ4至少应有两条黑色，不妨设
υ1υ4, υ2υ4 黑色
所以存在第二个 3阶单色完全图。
υ2 υ1
υ3
υ4
υ6
υ5
命题 11.2 7阶 2色完全图至少含有 4个 3阶单色安全图 。
命题 11.3 18阶 2色完全图中必含有 4阶单色完全图。
对拉姆齐问题的认识不能仅仅停留在
例 11.1的水平上。利用逻辑推理方法，
实际上还可获得一大批结果。命题 11.2
和命题 11.3的证明留给大家自己去完成。
例 2 17位学者中每人都和其他人通信讨论 3个方向的课题。
任意两人间只讨论其中一个方向的课题，则其中必可找出 3
位学者，他们之间讨论的是同一方向的课题。
证明
将每一学者看成一个顶点，作一个 17 阶完
全图。 按讨论课题的方向对边染色，相同方向染
成同一颜色，得到一个 17 阶 3 色完全图。
任取一顶点 A,与它相关联的有 16 条边，
其中必能找出 6 条相同颜色的边，不妨设 A 与
υ
1
，…,υ
6
的连线有相同颜色。 连接 A 和 6 个
顶点υ
1
，…，υ
6
。如果这 6 个顶点间也有这种
颜色的边，则已找到讨论同一方向课题的三位学
者；否则，υ
1
，…，υ
6
及连接它们的边构成一
个 6 阶 2 色完全图，由例 1,必可从中找到一个
3 阶单色完全图，即找出三位讨论同一方向课题
的学者 。
奇偶数校验及相关问题?
q
p2 ?
证明,
采用反证法, 设, 其中 p,q互素, 则有
p2=2q2。 因为 2|p2,故 2|p。 记 p=2p1,可得 4p12=2q2,即
2p12=q2, 故又有 2|q,与 p,q互素矛盾 。
例 3 证明 是无理数。2
同样方法可以证明：若 m是大
于 1的素数,n是大于 1的整数，
则 必为无理数。n m
例 4 拟用 40块方形瓷砖铺设如下图所示的地面，但商店只
有长方形瓷砖，其大小为方形的两块。问购买 20块长方形瓷
砖后，是否可能不裁开而直接铺好地面？
解 将图 11.4中的 (a) (b)黑白相间染色。
显然，如长方形瓷砖不裁开，只能用来复盖相
邻的两格，故复盖的两格必为一白一黑。
下图 (a)中共有 21个黑格和 19个白格，故不可能
直接铺好，下图 (b)中黑白格各为 20个，大家很
容易找到直接铺设的方法。
图 (a) 图 (b)
例 5 设一块 m× n的棋盘被若干个形如 的板块恰好
盖满，试证明 m× n必能被 8整除。
证明,
显然有 4|m× n，故 m,n中至少有一个为偶数，不妨
设 n为偶数，将棋盘按列黑白相间染色，如下图 (a )
所示，由于 n为偶数，黑、白列的数目相同，故黑白
格数相同，设各为 2k个。
图 (a)
板块可以有许多种拼凑法，但容易看出，每一板块放
置的方向（称之为定向）只有八种可能的选择，如下
图 (b)所示。
图 (b)
容易看出，不论按什么方向放置板块，每一板块均盖住
奇数个黑格（ 1格或 3格），故盖住棋盘的板块必有偶数
个，从而,m× n的棋盘必能被 8整除。
图 (a)
例 6 拟将一批尺寸为 1× 2× 4的的商品装入尺寸为 6× 6× 6
的正方体包装箱中，问是否存在一种装法，使装入的该商品
正好充满包装箱。
解 将正方体剖分成 27个 2× 2× 2的小正方体，并
按下图所示黑白相间地染色。
再将每一 2× 2× 2的小正方体剖分成 1× 1× 1的
小正方体。
易见,27个 2× 2× 2的正方体中，有 14个是黑的，
13个是白的（或 13黑 14白），故经两次剖分，
共计有 112个 1× 1× 1的黑色小正方体和 104个
1× 1× 1的白色小正方体。
虽然包装箱的体积恰好是商品体积的 27倍，但
容易看到，不论将商品放置在何处，它都将占
据 4个黑色和 4个白色的 1× 1× 1小正方体的位置，
故商品不可能充满包装箱。
德国著名的艺术家 Albrecht Dürer(1471-1521)
于 1514年曾铸造了一枚名为,Melencotia I”的铜
币。令人奇怪的是在这枚铜币的画面上充满了数
学符号、数字及几何图形。这里，我们仅研究铜
币右上角的数字问题
Dürer魔方 （ 或幻方 ） 问题?
所谓的魔方是指由 1~n2这 n2个正整
数按一定规则排列成的一个 n行 n列
的正方形 。 n称为此魔方的阶 。
Dürer魔方, 4阶，每一行之和为
34，每一列之和为 34，对角线
（或反对角线）之和是 34，每个
小方块中的数字之和是 34，四个
角上的数字加起来也是 34
什么是 Dürer魔方
多么奇妙的
魔方！
铜币铸造时间,1514年
构造魔方是一个古老的数学游戏，起初它
还和神灵联系在一起，带有深厚的迷信色彩。
传说三千二百多年前（公元前 2200年），因治
水出名皇帝大禹就构造了三阶魔方（被人们称
“洛书”），至今还有人把它当作符咒用于某
些迷信活动，大约在十五世纪时，魔方传到了
西方，著名的科尼利厄斯 ·阿格里帕（ 1486-1535）
先后构造出了 3~9阶的魔方 。
如何构造魔方
奇数（不妨 n=5）阶的情况
Step1,在第一行中间写 1
Step2,每次向右上方移一格依次填按由小到大排列的下
一个数，向上移出界时填下一列最后一行的小方格；向
右移出界时填第一列上一行的小方格。若下面想填的格
已填过数或已达到魔方的右上角时，改填刚才填的格子
正下方的小方格，继续 Step2直到填完
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
偶数阶的情况
偶数阶的魔方可以利用奇数
阶魔方拼接而成，拉尔夫 ·斯特雷
奇给出了一种拼接的方法,这里
不作详细介绍
五阶 没人知道有多少个！！！
三阶 1个 反射和中心旋转生成 8个
四阶 880个 反射和中心旋转生成 7040个
魔方数量随阶数 n增长
的速度实在是太惊人了！
同阶魔方的个数
允许构成魔方的数取任意实数
允许取实数
n阶魔方 A,B，任意实数 α, β
αA+βB 是 n阶魔方
具有指定性质的魔方全体构成一个线性空间
问题已发生了实质性变化
注：刻画一个线性空间只需指出它的维数并求出
此线性空间的一组基底
松驰问题的讨论
1在第一行中共有 4种取法，为保持上述
性质的成立，第二行中的 1还有两种取法。当
第二行的 1也取定后，第三行与第四行的 1就完
全定位了，故一共可作出 8个不同的最简方阵，
称之为基本魔方并记之为 Q1,…, Q8
仍以 4阶方阵为例 。
令 R为行和, C为列和, D为对角线和, S为小方块和
定义 0-方,R=C=D=S=0
定义 1-方,R=C=D=S=4
R=C=D=S=1的方阵构成的线性空间具有什么样的性质？
类似于构造 n维欧氏空间
的标准基，利用 0和 1我们
来构造一些 R=C=D=S=1
的最简单的方阵。
?
?
?
?
?
?
?
?
?
?
?
?
?
0010
1000
0100
0001
1
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0100
0010
1000
0001
2
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0010
0100
0001
1000
3
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0100
0001
0010
1000
4
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
1000
0010
0001
0100
5
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
1000
0001
0100
0010
6
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0010
0100
7
Q
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
0100
1000
0010
8
Q
显然,Dürer空间（简称 D空间）中任何一个元素都
可以用 Q1,Q2,…, Q8来线性表示，但它们能否构
成 D空间的一组基呢？
是否线性无关？821,,,QQQ ?
容易看出：
076328541 ???????? QQQQQQQQ
Q1,…, Q8这 8个基本方是线性相关的，即至少存在一个 Qj，可
以通过其它 7个基本方的线性组合得到。这 8个基本方的地位是等
同的，故可不妨设 j=8。下面验证 Q1,Q2,…, Q7是否线性相关。
0
7
1
??
?i
iiQr
令：,即
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
???
6542317
7135264
2617453
4375621
rrrrrrr
rrrrrrr
rrrrrrr
rrrrrrr
?
?
?
?
?
?
?
?
?
?
?
?
0000
0000
0000
0000
=
等号两边对应元素相比较,得 r1=r2=…=r 7=0，
所以 是 线性无关
721,,,QQQ ?
721,,,QQQ ?
是 D空间的最小生成集。
令 D
即解方程组：
772211 QdQdQd ??? ????
?
?
?
?
?
?
?
?
?
?
?
?
114155
12769
811105
132316
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
???
6542317
7135264
2617453
4375621
ddddddd
ddddddd
ddddddd
ddddddd
=
解得
D=
7654321 5336788 QQQQQQQ ??????
研究 Albrecht Dürer铸造的铜币
D空间的子空间和 D空间的扩展
（ 1） 要求数字方的所有数都相等
这是集合 G={rE,r∈ R}，
G是以 βG={E}为基的一维向量空间
（ 2） 要求列, 行及每条主, 付对角线上各和都相等 。
得到 5维泛对角方的向量空间 B。 例如：
它的基 BB为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
127261
216712
3221116
1611217
P
H=N=R=C=46
其中 H为主对角线和，
N为付对角线和。
进一步讨论
?
?
?
?
?
?
?
?
?
?
?
?
?
1010
1010
0101
0101
1
P
?
?
?
?
?
?
?
?
?
?
?
?
?
0110
1001
0110
1001
2
P
?
?
?
?
?
?
?
?
?
?
?
?
?
1001
0110
1001
0110
3
P
?
?
?
?
?
?
?
?
?
?
?
?
?
1010
0101
0101
1010
4
P
?
?
?
?
?
?
?
?
?
?
?
?
?
1100
0011
1100
0011
5
P
（ 3） 要求行和，列和及两条对角线上的元素和相等
得到 8维向量空间 Q。
基向量 QB={Q1,Q2,…, Q7,N0}，
其中 Q1,Q2,…, Q7是 D的基，而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0110
0000
0000
0110
0N 例如,R=C=D=30
?
?
?
?
?
?
?
?
?
?
?
?
?
9777
69105
75612
8976
T
（ 4） 仅要求行和与列和相等
得到 10维向量空间 ψ
基向量 ψB={Q1,Q2,…, Q7,N1,N2,N3}
其中 Q1,Q2,…, Q7是 D的基，而
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
1001
1001
0000
1N
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0110
1001
0101
1010
2N
?
?
?
?
?
?
?
?
?
?
?
?
?
0100
1000
0001
0010
3N
（ 5） 对数字没任何要求
所有 4× 4数字方组成 16维向量空间 M
基向量 MB的元素应是标准基（即仅有一个
元素为 1，其余元素均为 0的阵）。
Botsch（ 1976年）证明了对于
1与 16之间的每一个数 K，都
存在 K维的 4× 4方的向量空间
由上可知，有下式成立,
（向量空间）
（维数） 0 1 5 7 8 10 16
? ? MQDBG ??????? 0
什么是拼方问题
在 H.E.Dudeney所写的, Cantebury
难题, 一书中有一个正方形的图案, 这
个正方形图案是由一个小长方形和若干
个边长各异的小正方形组成的 。 小长方
形的长为, 宽为, 要求求出所有正
方形的边长和拼接方法 。 这种拼接过程
称为拼方, 而这种类型的问题称为拼方
问题 。
4
110 41
拼方问题?
12
8
532
721/4
11/45/2
31/4
1
受上一问题的启示，加拿大数学家 W.T.Tutte,A.Stone
等人考虑了如下问题：
怎样的长方形可以剖分成若干个边长各异的小正方形？
正方形能否剖分成边长各异的小正方形？
称具有上述性质的长方形为 完美长方形,正方形
为 完美正方形 。
波兰数学家 Z.Moron 的工作
Z.Moron 在 W.T.Tutte等之前已经作出了
一个 9阶完美长方形，见右图 18
14
4
10
15
7
9
8
1Z.Moron的完美长方
形很接近完美正方形
Tutte等人用来分析 Moron给出例子的 奇特方法：
用点表示水平边，用边表示小正方形。边长即小正方
形之边长，方向规定由上到下。于是一个剖分好的完美长
方形被十分巧妙地转化成了一个有向图网络，见下图
1 x 2 x
3 x 4 x 5 x
6 x
7 x
8 x 9 x
除表示上、下两底边的顶点以外，
其余顶点处指入边边长之和应等
于指出边边长之和
A
B
C
D
E
F
1 x 2 x
3 x 4 x 5 x
6 x
7 x 8 x
9 x
1 x
7 x
3 x
由上面说明：假如我们把得
到的有向图网络看作电网络，
则所述性质恰好就是电学中
的基尔霍夫定律。
若将每边看成一个单位电阻，在给出正
极 A与负极 F之间的电势差后（相当于给
出长方形的高），即可求出每条边上的
电流强度（等于两顶点间的电势差），
而这些数恰好就是小正方形的边长。
此外还可看出，解应当是唯
一的，因为在给定 A,F间的
电势差后，各边上的电流强
度是唯一确定的。
分析 Moron给出的完美长方形，取高为 32，则相应电网络中
的电流强度 xi(i=1,…,9)应满足：
其解为：
（ x1,x2,x3,x4,x5,x6,x7,x8,x9)=(18,15,4,7,8,1,14,10,9)，
恰为相应小正方形的边长。此外，由 x1+x2=33可知，长方形
的宽应为 33。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
??
????
??
???
??
??
32
32
32
32
842
831
952
71
98721
965
8643
542
731
xxx
xxx
xxx
xx
xxxxx
xxx
xxxx
xxx
xxx
可以不管长方形的剖
分，直接根据图的各
种情况利用计算机来
搜查
前面分析是在对完美
长方形作了剖分的前
提下作出的，不知道
剖分情况怎么办？
几种最简单的情况及寻查过程的简要说明
有向图只有三条边的图见图 1。
由 x1= x3可知不存在 3阶完美长方形。
由四条边组成的有向图可以有两种形式，
见图 2中的（ a）,(b)，它们均不可能对
应完美长方形。
1 x
2 x
3 x
图 11 x
2 x
3 x
4 x
图 2（ b）
2 x1 x
3 x 4 x
图 2（ a）
逐阶寻查下去可发现，完美长方形对应的电网络必有以下性质
(性质 1) 除两端顶点外，其余各项点的进出边之和至少为 3。
(性质 2) 电网络不具有对称性。
根据这两条性质，可以发现
完美长方形的最小阶数为 9，
进而可作出各种 9阶,10阶、
11阶 … 完美长方形。
当然，随着阶数增大，计算
量将按指数增长，因为相应
电网络的数目是按指数增长
的。
几点说明,
对一个指定的有向图求相应的完美长方形时，高可以先随意
选取一个整数。求出所有小正方形的边长后再将所有数据同
乘一个适当的数，使所有有数据均化为整数。显然，变动长
方形的高所得到的剖分是相似的，在将相似看作等同的意义
下，这种剖分是唯一的。
Tutte等人将他们用人工方法得到的完美长方形列成了一个
表，其中包括有二百多个完美长方形。 1960年，人们用电
子计算机求得了 9至 15阶的全部完美长方形，可其中没有
一个是完美正方形！
是否存在完美正方形？
当求得的完美长方形的长恰好等于宽的十分巧合的情况下，
我们才能得到一个正方形的剖分。由于计算量过大，在计算机
上寻查并未获得成功，最早作出的正方形的剖分是基于非常复
杂的图形并用对称性人工凑出来的，它具有 69阶。后来又作出
了 39阶和 38阶的完美正方形。接着 Tutte等人利用他们获得的完
美长方形表又拼凑出一个 26阶的完美正方形，它是由一个边长
为 231的正方形和两个完美长方形拼合而成的，如图所示。
完美长方形
正方形 完美长方形
在此之前, 人们对图论还没有多少研究 。 Tutte等人在引入
网络图方法后, 十分自然地将兴趣转向了对图论的研究, 并
因此而获得了许多具有重大意义的开创性结果, 直接促进了
图论的发展 。
对偶理论?
对一个完美长方形也可用垂直线代替水平线，用类似方法
作出另一个有向图。所以对一个确定的完美长方形，我们
可以获得的两个不同的有向图。
1 x 2 x
3 x 4 x 5 x
6 x
7 x
8 x 9 x
c
a
b
d
e f
D
E
1 x 2 x
3 x 4 x 5 x
6 x
7 x
8 x 9 x
A
B
C
F
两个有向图是由同一个完美长方形得出的，它们之间必
然存在着某种密切的关系，这种关系被称为对偶关系。
在 A,F和 a,f之间各添加一条线段，对偶关系就显示出
来，添线后的网络称为拼方完美长方形的完全网或 C-网。
每一个 C-网将平面分割成若干个区域（称为面），而两
个互为对偶的 C-网是指具有如下性质的两个 C-网：可以
把它们画在平面上使任一个 C-网的每一面中有且仅有另
一个 C-网的一个顶点，见图。
A
B
C
D
E
F
a
b
c
d
e f
添加
添加
3-连通理论?
前面我们已经看到，由几个完美长方形可以拼出一个新的完美
长方形。相应地，新网络图与原有的完美长方形的网络之间存
在着十分密切的联系。应当看到这种拼合而成的完美长方形是
比较特殊的，它们与那些非拼合而成的（基本）完美长方形有
着重大的区别，这些区别必然会在图论中反映出来。例如，考
察由两个完美长方形拼接成的完美长方形，可以导出下述定义：
定义 11.1 一个连通图如可分成两部分，这两部分只有一个公
共顶点，且每一部分均含有另一部分所没有的顶点，则称此图
为可分离的。不可分离的图称为 2-连通图。
定义 11.2 一个 2-连通图若可被分成两部分，这两部分恰有两
个公共顶点，且每一部分均含有另一部分所没有的顶点，则称
此图为 2-可分离的,2-连通但非 2-可分离的图称为 3-连通图。
可分离图
2-可分离图
Tutte等人从着迷于一个数学游戏开始，而最终却成了研究
图论问题的专家创建了图的对偶理论,3-连通理论等。在他们
取得的极其丰硕的研究成果中，人们可以清晰地看到 丰富的想
象力, 敏锐的洞察力 和 严密的逻辑推理能力 得到了巧妙的结合。
