扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口抽屉原理在数学中的运用_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
抽屉原理在数学中的运用
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢71数学建模-图论
上亿文档资料，等你来发现
71数学建模-图论
初等数学方法建模；现实世界中有很多问题，它的机理较简单，用静态,线；第一节有关自然数的几个模型；1.1鸽笼原理；鸽笼原理又称为抽屉原理，把N个苹果放入n(n?N；分析：我们按认识人的个数，将N个人分为0,1,2；问题2：在一个边长为1的正三角形内最多能找到几个；分析：边长为1的正三角形?ABC，分别以A,B,；图1―1；问题3：能否在8?8的方格表ABCD的
初等数学方法建模现实世界中有很多问题，它的机理较简单，用静态,线性或逻辑的方法即可建立模型，使用初等的数学方法，即可求解，我们称之为初等数学模型。本章主要介绍有关自然数，比例关系，状态转移，及量刚分析等建模例子，这些问题的巧妙的分析处理方法，可使读者达到举一反三，开拓思路，提高分析, 解决实际问题的能力。第一节
有关自然数的几个模型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这三个数中的任一个，使得每行，每列及对角线AC,BD的各个数的和都不相同？为什么？分析：若从考虑填法的种类入手，情况太复杂；这里我们注意到，方格表中行,列及对角线的总数为188个数的和最小为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个学生都换到他的邻座上去，问是否有这种调换位置的方案？1.3 自然数的因子个数与狱吏问题令 d(n) 为自然数 n的因子个数，则 d(n)有的为奇数，有的为偶数，见下表:我们发现这样一个规律，当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,2也即 n? 只有n为完全平方数, 才会出现 n?a的情形，d(n)才为奇数。下面我们利用上述结论研究一个有趣的问题.狱吏问题：某王国对囚犯进行大赦，让一狱吏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个人，两点间存在连线，表示两人相识；只需说明，图中必有三点组成三角形（有三人相识），或有三点之间设有一条连线（三人互不相识）即可，第二节 状态转移问题本节介绍两种状态转移问题，解决这种问题的方法,有状态转移法，图解法及用图的邻接距阵等。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 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,?,A?(aij)n?n为G的邻接距阵，其中?1
aij???0vivj?E(G)vivj?E(G)i,j?1,2,?,nk定理1：设A(G)为图G的邻接距阵，则G中从顶点vi到顶点vj，长度为k的道路的条数为A中的i行j列元素.证： 对k用数学归纳法k?1 时，显然结论成立; 假设k时，定理成立， 考虑 k?1的情形.(l)ll?1
记A的i行j列元素为 aijl?2
, 因为 A?A?A, 所以 laij(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下面分析及求解假设渡河是从南岸到北岸，（m，n）表示南岸有m个商人，n个随从，全部的允许状态共有10个v1?(3,3)v6?(1,1)v2?(3,2)v7?(0,3)v3?(3,1)v8?(0,2)v4?(3,0)v9?(0,1)v5?(2,2) v10?(0,0)以V??v1,v2,??v10?为顶点集，考虑到奇数次渡河及偶数次渡河的不同，我们建立两个邻接距阵包含各类专业文献、应用写作文书、中学教育、幼儿教育、小学教育、文学作品欣赏、外语学习资料、71数学建模-图论等内容。　
　数学建模中的图论方法_理学_高等教育_教育专区。数学建模中的图论方法 一、引言我们知道,数学建模竞赛中有问题 A 和问题 B。一般而言,问题 A 是连续系统中 的问... 　数学数学隐藏&& 第五章 图与网络模型及方法 §1 概论 图论起源于 18 世纪。第一篇图论论文是瑞士数学家 欧拉于 1736 年发表的“哥尼斯堡的七座桥” 。1847... 　《数学建模》讲座: 数学建模中的图论方法图论是离散数学的重要组成部分,它对于自然科学、工程技术、经济管理和社 会现象等诸多问题,能够提供有力的数学模型加以解决... 　数学建模作业图论_数学_自然科学_专业资料。数学建模作业 第十三组: 组长:王周闯() 组员:王亚东() 林李健() 岩() 2012 年... 　数学模型第六次作业 6.1 实验目的与要求 图论(组合优化)实验 ? 学会用图论(组合优化)的方法或思想建模 ? 学会用 LINGO 软件求解组合优化问题 ? 简历相应的数学... 　北京工业大学-数学建模6-图论(组合优化)实验201311_数学_自然科学_专业资料。图论(组合优化)实验作业一、 基本实验 1.设备更新问题 某公司需要对一台已经使用了 2... 　数学建模图论例题_工学_高等教育_教育专区。图论例题例 某公司在六个城市 c1 , c2 , , c6 中有分公司,从 ci 到 c j 的直接航程票价记在下述矩阵的 (i,... 　数学建模作业 (实验 6 图论(组合优化)实验) 基本实验 1.设备更新问题某公司需要对一台已经使用了 2 年的机器确定今后 4 年(n=4)的最优更新策略.公司要求, ... 　数学建模 图论模型 图论 隐藏&& 图论算法 §1 最小生成树 1.1 生成树的概念 . 设图 G=(V,E)是一个连通图,当从图中任一顶点出发遍历图 G 时,将边集...抽屉原理在数学解题中的应用_吕松涛_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
抽屉原理在数学解题中的应用_吕松涛
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢2012抽屉原理在初等数学中的运用_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
2012抽屉原理在初等数学中的运用
阅读已结束，如果下载本文需要使用
想免费下载本文？
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢