第六章初等数学方法建模.docx

本文格式为Word版，下载可任意编辑第六章初等数学方法建模 初等数学方法建模 其次章 初等数学方法建模 现实世界中有好多问题，它的机理较简朴，用静态,线性或规律的方法即可建立模型，使用初等的数学方法，即可求解，我们称之为初等数学模型本章主要介绍有关自然数，比例关系，状态转移，及量刚分析等建模例子，这些问题的高明的分析处理方法，可使读者达成举一反三，开拓思路，提高分析, 解决实际问题的才能 第一节 有关自然数的几个模型 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中。