2013数学建模周末培训

逻辑模型

浙江大学数学建模基地§9

逻辑模型

欧几里得在不加证明而被直接采用的一些基本概念和公理的基础上。运用逻辑推理方法得出了一系列的定理、推论，从而建立了完整的欧几里得几何学，这一辉煌成果至今仍然是人类的宝贵财富。本章介绍的一些模型采用的也是类似的方法。建模者从问题应当具有的某些基本属性出发，运用逻辑推理方法或者导出满足这些基本属性的解来，或者证明在原有观念下问题不可能有解，从而从根本上改变人们对这一问题的看法§9.1几个较为简单的问题本节将采用逻辑推理方法讨论几个颇为有趣的问题。

例1

在每一次人数不少于6人的聚会中必可找出这样的3人，他们或者彼此均认识或者彼此均不认识。

利用图的方法来描述该问题。将人看成顶点，两人彼此都认识用实线连，否则虚线。证明：

相识问题（拉姆齐问题）

问题转化为在一个6阶图中必存在实线三角形或虚线三角形。请大家一起画图证明υ2

υ1

υ3

υ4

υ6

υ5

υ1

υ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.27阶2色完全图至少含有4个3阶单色安全图。命题11.318阶2色完全图中必含有4阶单色完全图。对拉姆齐问题的认识不能仅仅停留在例11.1的水平上。利用逻辑推理方法，实际上还可获得一大批结果。命题11.2和命题11.3的证明留给大家自己去完成。例217位学者中每人都和其他人通信讨论3个方向的课题。任意两人间只讨论其中一个方向的课题，则其中必可找出3位学者，他们之间讨论的是同一方向的课题。

奇偶数校验及相关问题证明：

采用反证法，设，其中p、q互素，则有p2=2q2。因为2|p2，故2|p。记p=2p1，可得4p12=2q2

，即2p12=q2

，故又有2|q，与p、q互素矛盾。例3

证明是无理数。同样方法可以证明：若m是大于1的素数，n是大于1的整数，则必为无理数。例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小正方体的位置，故商品不可能充满包装箱。

德国著名的艺术家AlbrechtDürer(1471-1521)于1514年曾铸造了一枚名为“MelencotiaI”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题

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:在第一行中间写1Step2:每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完12345678910111213141516171819202122232425偶数阶的情况

偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法，这里不作详细介绍五阶没人知道有多少个！！！三阶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=4R=C=D=S=1的方阵构成的线性空间具有什么样的性质？类似于构造n维欧氏空间的标准基，利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。

显然，Dürer空间（简称D空间）中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，但它们能否构成D空间的一组基呢？容易看出：Q1，…，Q8这8个基本方是线性相关的，即至少存在一个Qj，可以通过其它7个基本方的线性组合得到。这8个基本方的地位是等同的，故可不妨设j=8。下面验证Q1，Q2，…，Q7是否线性相关。

令：，即=等号两边对应元素相比较，得r1=r2=…=r7=0，所以是线性无关是D空间的最小生成集。

令D

即解方程组：

=

解得

D=研究AlbrechtDürer铸造的铜币

D空间的子空间和D空间的扩展

（1）要求数字方的所有数都相等这是集合G={rE,r∈R}，

G是以βG={E}为基的一维向量空间

（2）要求列、行及每条主、付对角线上各和都相等。得到5维泛对角方的向量空间B。例如：

它的基BB为：H=N=R=C=46其中H为主对角线和，N为付对角线和。

进一步讨论

（3）要求行和，列和及两条对角线上的元素和相等得到8维向量空间Q。基向量QB={Q1，Q2，…，Q7，N0}，其中Q1，Q2，…，Q7是D的基，而

例如：R=C=D=30

（4）仅要求行和与列和相等得到10维向量空间ψ

基向量ψB={Q1，Q2，…，Q7，N1，N2，N3}

其中Q1，Q2，…，Q7是D的基，而

（5）对数字没任何要求所有4×4数字方组成16维向量空间M

基向量MB的元素应是标准基（即仅有一个元素为1，其余元素均为0的阵）。

Botsch（1976年）证明了对于1与16之间的每一个数K，都存在K维的4×4方的向量空间由上可知，有下式成立：（向量空间）（维数）015781016

什么是拼方问题

在H.E.Dudeney所写的《Cantebury难题》一书中有一个正方形的图案，这个正方形图案是由一个小长方形和若干个边长各异的小正方形组成的。小长方形的长为，宽为，要求求出所有正方形的边长和拼接方法。这种拼接过程称为拼方，而这种类型的问题称为拼方问题。

拼方问题128532721/411/45/231/41受上一问题的启示，加拿大数学家W.T.Tutte,A.Stone等人考虑了如下问题：

怎样的长方形可以剖分成若干个边长各异的小正方形？正方形能否剖分成边长各异的小正方形？称具有上述性质的长方形为完美长方形，正方形为完美正方形。波兰数学家Z.Moron的工作Z.Moron在W.T.Tutte等之前已经作出了一个9阶完美长方形，见右图1814410157981Z.Moron的完美长方形很接近完美正方形Tutte等人用来分析Moron给出例子的奇特方法：

用点表示水平边，用边表示小正方形。边长即小正方形之边长，方向规定由上到下。于是一个剖分好的完美长方形被十分巧妙地转化成了一个有向图网络，见下图除表示上、下两底边的顶点以外，其余顶点处指入边边长之和应等于指出边边长之和ABCDEF由上面说明：假如我们把得到的有向图网络看作电网络，则所述性质恰好就是电学中的基尔霍夫定律。若将每边看成一个单位电阻，在给出正极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。可以不管长方形的剖分，直接根据图的各种情况利用计算机来搜查前面分析是在对完美长方形作了剖分的前提下作出的，不知道剖分情况怎么办？

几种最简单的情况及寻查过程的简要说明

有向图只有三条边的图见图1。由x1=x3可知不存在3阶完美长方形。由四条边组成的有向图可以有两种形式，见图2中的（a）、(b)，它们均不可能对应完美长方形。图1图2（b）图2（a）逐阶寻查下去可发现，完美长方形对应的电网络必有以下性质

(性质1)

除两端顶点外，其余各项点的进出边之和至少为3。

(性质2)电网络不具有对称性。根据这两条性质，可以发现完美长方形的最小阶数为9，进而可作出各种9阶、10阶、11阶…完美长方形。当然，随着阶数增大，计算量将按指数增长，因为相应电网络的数目是按指数增长的。几点说明：对一个指定的有向图求相应的完美长方形时，高可以先随意选取一个整数。求出所有小正方形的边长后再将所有数据同乘一个适当的数，使所有有数据均化为整数。显然，变动长方形的高所得到的剖分是相似的，在将相似看作等同的意义下，这种剖分是唯一的。

Tutte等人将他们用人工方法得到的完美长方形列成了一个表，其中包括有二百多个完美长方形。1960年，人们用电子计算机求得了9至15阶的全部完美长方形，可其中没有一个是完美正方形！

是否存在完美正方形？

当求得的完美长方形的长恰好等于宽的十分巧合的情况下，我们才能得到一个正方形的剖分。由于计算量过大，在计算机上寻查并未获得成功，最早作出的正方形的剖分是基于非常复杂的图形并用对称性人工凑出来的，它具有69阶。后来又作出了39阶和38阶的完美正方形。接着Tutte等人利用他们获得的完美长方形表又拼凑出一个26阶的完美正方形，它是由一个边长为231的正方形和两个完美长方形拼合而成的，如图所示。完美长方形正方形完美长方形

在此之前，人们对图论还没有多少研究。Tutte等人在引入网络图方法后，十分自然地将兴趣转向了对图论的研究，并因此而获得了许多具有重大意义的开创性结果，直接促进了图论的发展。

对偶理论