第六章初等数学方法建模

初等数学方法建模

第二章 初等数学方法建模

现实世界中有很多问题，它的机理较简单，用静态,线性或逻辑的方法即可建立模型，使用初等的数学方法，即可求解，我们称之为初等数学模型。本章主要介绍有关自然数，比例关系，状态转移，及量刚分析等建模例子，这些问题的巧妙的分析处理方法，可使读者达到举一反三，开拓思路，提高分析, 解决实际问题的能力。

第一节 有关自然数的几个模型

1.1鸽笼原理

鸽笼原理又称为抽屉原理，把N个苹果放入n(n?N) 个抽屉里，则必有一个抽屉中至少有2个苹果。 问题1：如果有N个人，其中每个人至多认识这群人中的n(n?N)个人（不包括自己），则至少有两个人所认识的人数相等。

分析：我们按认识人的个数，将N个人分为0,1,2?,n类，其中k(0?k?n)类，表示认识k个人，这样形成 n?1 个“鸽笼”。若 n?N?1 ，则N个人分成不超过N?1 类，必有两人属于一类，也即有两个人所认识的人数相等；若n?N?1 ，此时注意到0类和N类必有一个为空集，所以不空的“鸽笼”至多为N?1个，也有结论成立

问题2：在一个边长为1的正三角形内最多能找到几个点，而使这些点彼此间的距离大于0.5.

分析：边长为1的正三角形 ?ABC，分别以A,B,C为中心，0.5为半径圆弧，将三角形分为四个部分（如图1-1 ），则四部分中任一部分内两点距离都小于0.5 ，由鸽笼原理知道，在三角形内最多能找四个点，使彼此间距离大于0.5 ，且确实可找到如A,B,C及三角形中心四个点。

图1—1

问题3：能否在8?8的方格表ABCD的各个空格中，分别填写1,2,3这三个数中的任一个，使得每行，

1

初等数学方法建模

每列及对角线AC,BD的各个数的和都不相同？为什么？

分析：若从考虑填法的种类入手，情况太复杂；这里我们注意到，方格表中行,列及对角线的总数为18

8个数的和最小为8，个；而用1,2,3填入表格，每行,列及对角线都是8个数，最大为24，共有24?8?1?17种；利用鸽笼原理，18个“鸽”放入17个“鸽笼”，必有两个在一个“鸽笼”，也即必有两个和相同。所以

题目中的要求，无法实现。

思考题：在一个边长为1的正三角形内，若要彼此间距离大于

1 ，最多能找到几个点？ n1.2 “奇偶校验”方法 所谓 “奇偶校验”，即是如果两个数都是奇数或偶数，则称这两个数具有相同的奇偶性；若一个数是奇数，另一个数是偶数，则称具有相反的奇偶性。在组合问题中，经常使用“奇偶校验”考虑配对问题。

问题1（棋盘问题）：假设你有一张普通的国际象棋盘，一组对角上的两个方格被切掉，这样棋盘上只剩下62个方格（如图1—2）。若你还有31块骨牌，每块骨牌的大小为1?2方格。试说明用互不重叠的骨牌完全覆盖住这张残缺的棋盘是不可能的。

分析：关键是对图1—2的棋盘进行黑白着色，使得相邻的两个方格有不同的颜色；用一块骨牌覆盖两个方格，必是盖住颜色不同的方格。我们计算一下黑白着色棋盘的黑格，白格个数，分别为30和32；因此不同能用31块骨牌盖住这张残缺的棋盘。用奇偶校验法，我们可以把黑色方格看成奇数方格，白色方格看成偶数方格；因为奇偶个数不同，所以不能进行奇偶配对，故题中要求的作法是不可能实现的。

图1-2

图1-3

问题2（菱形十二面体上的H路径问题）：沿一菱形十二面体各棱行走，要寻找一条这样的路径它通过各顶点恰好一次，该问题被称为Hamilton路径问题。

分析：我们注意到菱形十二面体每个顶点的度或者为3或者为4，所谓顶点的度是指通过这一顶点的棱数，如图1—3；且每3度顶点刚好与3个4度顶点相连，而每个4度顶点刚好与4个3度 顶点相连。因此一个Hamilton路径必是3度与4度顶点交错，故若存在Hamilton 路径，则3度顶点个数，与4度顶点个数要么相等，要么相差1。用奇偶校验法3度顶点为奇数顶点，4度顶点为偶数顶点，奇偶配对，最多只能余1个；而事实上菱形十二面体中，有3度顶点8个，4度顶点6个；可得结论，菱形十二面体中不存在Hamilton 路径.

思考题：1、设一所监狱有64间囚室，其排列类似8?8棋盘，看守长告诉关押在一个角落里的囚犯，

只要他能够不重复地通过每间囚室到达对角的囚室（所有相邻囚室间都有门相通）,他将获释，问囚犯能否获得自由？

2、某班有49个学生，坐成7行7列，每个坐位的前后左右的坐位叫做它的邻座，要让49个

2

初等数学方法建模

学生都换到他的邻座上去，问是否有这种调换位置的方案？ 1.3 自然数的因子个数与狱吏问题

令 d(n) 为自然数 n的因子个数，则 d(n)有的为奇数，有的为偶数，见下表: n 1 d(n) 1

我们发现这样一个规律，当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,

2也即 n?ab; 只有n为完全平方数, 才会出现 n?a的情形，d(n)才为奇数。

2 2 3 2 4 3 5 2 6 4 7 2 8 4 9 3 10 4 11 2 12 6 13 2 14 4 15 4 16 5 下面我们利用上述结论研究一个有趣的问题.

狱吏问题：某王国对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次按所定规则转动门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的？

问题分析： 牢房的锁最后是打开的，则该牢房的锁要被转动奇数次；如果把n间牢房用1,2,?,n编号，则第k间牢房被转动的次数，取决于k是否为1,2,?,n整除，也即k的因子个数，利用自然数因子个数定理，我们得到结论：只有编号为完全平方数的牢房门仍是开着的。 1．4 相识问题

问题：在6人的集会上，总会有3人互相认识或互相不认识。

分析：设6人为A1,A2,?,A6;下面分二种情形，1.A1至多只和两个人相识，不妨设A1不认识A2,A3,A4；若A2,A3,A4互相都认识，则结论成立，若A2,A3,A4中有两人不认识，则加上A1，有三人互不相识. 2．A1 至少和三人相识，不妨设A1 认识A2,A3,A4；若A2,A3,A4互不相识结论成立，若A2,A3,A4有两人相识，加上A1 则有三人互相认识 。这样，我们就证明了结论成立,这个问题的讨论，我们也可以采用几何模似的方法，如图1—4

图1-4

在平面上画出六个点，表示6个人，两点间存在连线，表示两人相识；只需说明，图中必有三点组成三角形（有三人相识），或有三点之间设有一条连线（三人互不相识）即可，

3

初等数学方法建模

思考题：

1． 9个人的集会中一定有3个人互相认识或4个人互相不认识 2． 14个人的集会中一定有3个人互相认识或者5个人互相不认识

3． 17个科学家中,每个科学家都和其他科学家通信，他们之间讨论3个题目，且任意两个科学家之间只讨

论1个题目，证明其中至少有3名科学家，他们互相通信中讨论的是同一题目

第二节 状态转移问题

本节介绍两种状态转移问题，解决这种问题的方法,有状态转移法，图解法及用图的邻接距阵等。 2．1 人、狗、鸡、米问题

人、狗、鸡、米均要过河，船上除1人划船外，最多还能运载一物，而人不在场时，狗要吃鸡，鸡要吃米，问人，狗、鸡、米应如和过河？

分析：假设人、狗、鸡、米要从河的南岸到河的北岸，由题意，在过河的过程中， 两岸的状态要满足一定条件，所以该问题为有条件的状态转移问题。

1. 允许状态集合 我们用（w, x, y, z），w, x, y, z=0或1，表示南岸的状态，例如（1，1，1，1）表示它们都在南岸，（0，1，1，0）表示狗，鸡在南岸，人，米在北岸；很显然有些状态是允许的，有些状态是不允许的，用穷举法可列出全部10个允许状态向量，

(1, 1, 1, 1) (1, 1, 1, 0) (1, 1, 0, 1) (1, 0, 1, 1) (1, 0, 1, 0) (0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (0, 1, 0, 1) 我们将上述10个可取状态向量组成的集合记为S，称S为允许状态集合 2、状态转移方程

对于一次过河，可以看成一次状态转移，我们用向量来表示决策，例（1，0，0，1）表示人，米过河。令D为允许决策集合，

D={ (1, x, y, z) : x+y+z=0 或 1}

另外，我们注意到过河有两种，奇数次的为从南岸到北岸，而偶数次的为北岸回到南岸，因此得到下述转移方程，

Sk?1?Sk?(?1)kdk ------------------------(2.1)

Sk?(wk,xk,yk,zk)表示第k次状态，dk?D 为决策向量.

图2-1

4

初等数学方法建模

2. 人、狗、鸡、米过河问题，即要找到d1,d2,?,dm?1?D，S0,S1,?,Sm?SS0?(0,0,0,0)

Sm?(1,1,1,1) 且满足（2.1）式。

下面用状态转移图求解

将10个允许状态用10个点表示，并且仅当某个允许状态经过一个允许决策仍为允许状态，则这两个允许状态间存在连线，而构成一个图, 如图2—1 , 在其中寻找一条从（1，1，1，1）到（0，0，0，0）的路径，这样的路径就是一个解, 可得下述路径图,

图2-2

由图2—2，有两个解都是经过7次运算完成，均为最优解 2．2 商人过河问题

三名商人各带一个随从乘船渡河，现有一只小船只能容纳两个人，由他们自己划行，若在河的任一岸的随从人数多于商人，他们就可能抢劫财物。但如何乘船渡河由商人决定，试给出一个商人安全渡河的方案。

首先介绍图论中的一个定理

G是一个图，V（G）为G的顶点集，E(G)为G的边集。 设G中有n个顶点v1,v2,?,vn;

A?(aij)n?n为G的邻接距阵，其中

aij???1?0vivj?E(G)vivj?E(G)i,j?1,2,?,n

k定理1：设A(G)为图G的邻接距阵，则G中从顶点vi到顶点vj，长度为k的道路的条数为A中的i行

j列元素.

证： 对k用数学归纳法

k?1 时，显然结论成立; 假设k时，定理成立， 考虑 k?1的情形.

ll?1(l) 记A的i行j列元素为 aijl?2 , 因为 A?A?A, 所以

l

aij(l?1)l?ail1a1j?ail2a2j???ainanj (2.2)

而从 vi到 vj长k?1的道路无非是从vi经k步到某顶vl1?l?n,再从vl 走一步到vj；由归纳

k假设从vi到vl长为k的道路共计ail条，而从vl到vj长为1的道路为alj条，所以长为k?1的从vi经kn步到vl再一步到vj的道路共有a下面分析及求解

(k)ilalj条，故从vi经k?1步到vj的路径共有a(k?1)ij(k)??ailalj条. l?1

5

本文来源：https://www.bwwdw.com/article/ydmt.html