《鸽巢原理在数学领域的应用》由会员分享，可在线阅读，更多相关《鸽巢原理在数学领域的应用（18页珍藏版）》请在金锄头文库上搜索。
1、鸽巢原理在数学领域的应用摘摘 要要组合数学是现代数学的重要分支，而鸽巢原理是组合数学中最基本最重要的概念之一，具有广泛的应用价值. 本文首先介绍了鸽巢原理的定义及其相关的公式和性质.接着重点讨论了鸽巢原理的应用，包括其在几何图形、数的整除、连续时间、人的相识和染色问题等领域的应用，并给出相关的计算公式.最后，我们进一步认识了鸽巢原理并得出其在诸多数学领域中都有重要的应用.【关关 键键 词词】 组合数学 鸽巢原理 Application of the Pigeonhole Principle in the field of mathematics AbstractCombinatorial ma
2、thematics is one of the important branches of modern mathematics, and the Pigeonhole Principle is a basic and most important theorem in combinatorial mathematics. In this paper, we first introduce the definition and some properties of the Pigeonhole Principle, together with the relative functions. T
3、hen we mainly focus on the applications of the Pigeonhole Principle, such as its applications on geometric figures, divisible problems of numbers, continuous time, human knowledge, coloring problems and so on. We also obtain their counting formulas. Thus we have a further study of the Pigeonhole Pri
4、nciple and find its applications on many branches of math.Key words combinatorial mathematics Pigeonhole Principle 目目 录录引 言 .1 1 鸽巢原理的概念 .1 1.1 定义 .1 1.2 鸽巢原理的一般表现形式.1 1.3 鸽巢公式及其性质.2 1.4 带中介的鸽巢公式及其性质.4 2 鸽巢原理在多领域的应用 .7 2.1 鸽巢原理在几何图形方面的应用.7 2.2 鸽巢原理在数的整除关系中的应用.8 2.3 鸽巢原理在“连续时间”问题上的应用.9 2.4 鸽巢原理在“人的相识
5、”问题上的应用.10 2.5 鸽巢原理在“染色问题”上的应用.11 2.6 数学竞赛中几种常见的鸽巢类型 .12 3 结束语 .14 参 考 文 献 .15盐城师范学院毕业论文第 1 页共 15 页引引 言言课桌上有八个苹果，要把这八个苹果放进七个抽屉中，无论怎样放，我们会发现有一个抽屉里面至少有个苹果，这一现象就是 “抽屉原理”. 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有或多于个元素放到个集合中去，其中必定至少有一个集1n1nn合里有两个元素”.抽屉原理也被称为“鸽巢原理” （如果有七个鸽笼，养鸽人养了八只鸽子，那么当鸽子飞回笼中后，至少有一个笼
6、子中装有两只鸽子” ） ，它在组合数学中占据着非常重要的地位，常被用来证明一些关于存在性的数学问题.鸽巢原理不仅在组合数学的研究中起着关键作用，而且在求解几何图形、数的整除、连续时间、人的相识和染色问题等数学领域中都有着重要作用.1 鸽巢原理的概念1.1 定义一般的鸽巢原理：个鸽巢，若有只鸽子在里面，则至少有一个鸽巢n1n里至少有两只鸽子.推论 1 只鸽子，个鸽巢，则至少有一个鸽巢里有不少于只mn11mn鸽子.推论 2 若有只鸽子飞进个鸽巢，则至少有一个鸽巢里有只鸽1n mnm子.推论 3 如果有个整数的平均数大于，n12,nm mm ,1r 即，则中至少有一个整数不小于 .12)1nmmmn
7、r12,nm mm ,r1.2 鸽巢原理的一般表现形式抽屉原理是由数学家狄利克雷首先提出，并用于证明一些数论中的问题，因此，也被称为狄利克雷原则.把鸽巢原理推广到一般情形有以下几种表现形式：形式一 把个元素划分到个集合中，用分别1nn12,nA AA12,na aa表示这个集合对应包含的元素个数，则至少存在某个集合，其包含的元素niA盐城师范学院毕业论文第 2 页共 15 页个数.2ia 证证（用反证法）假设结论不成立，即对每一个都有，则因为是整ia2ia ia数，应有，于是，这与题设矛盾.所以，1ia 121 111naaann 至少有一个，即必有一个集合中含有两个或两个以上的元素.2ia
8、形式二 把个元素划分到个集合中，用表示1nmn12,nA AA12,na aa这个集合对应包含的元素个数，则至少存在某个集合，其包含的元素个数niA.1iam证证（用反证法）假设结论不成立，即对每一个都有，则因为ia1iam是整数，应有，于是，这与题iaiam121naaammnmnm m设矛盾.所以，至少存在一个.1iam形式三 设把个元素分为个集合，用表示这个nk12,kA AA12,ka aak集合里相应的元素个数，则：至少存在某个都有.iaian k证证（用反证法）设结论不成立，即对每一个都有，于是iaian k，这与题设相矛 12*kaaan kn kn kkn kkn kn产生矛盾
9、.所以，必有一个集合中元素.n k形式四 设把个元素分为个集合，用121kqqqnn12,nA AA表示这个集合里相应的元素个数，则：至少存在某个，使得12,na aania.iiaq证证（用反证法） 设结论不成立，即对任意的都有，因为为整数，iaiiaqia应有，1iiaq1212121nnnaaaqqqnqqqn这与题设发生矛盾.所以，假设不成立，故必有一个 ，在第 个集合中元ii素.iiaq形式五 令无穷多个元素分成有穷多个集合，则至少存在一个集合，它含有无穷多个元素.证证 （用反证法）将无限多个元素划分至有限个集合，先假设这有限个集合中元素的个数全是有限个，那么有限个有限数相加之和必是
10、有限数，这就与题盐城师范学院毕业论文第 3 页共 15 页设发生矛盾，因此假设不成立，故必有一个集合含有无穷多个元素.1.3 鸽巢公式及其性质在组合学和人工智能中，很多原理和问题可以用命题公式表示.这些公式在适当变形其结构后，就会出现很多有趣的性质，比如极小不可满足性、对称性、子结构同构性、消解难例等等.著名的鸽巢公式就来自于组合学中的鸽巢原理.鸽巢原理是指：只鸽子进入个巢穴，必有一个巢穴至少有 2 只鸽子.我们1nn引入变元指 只鸽子进入号巢穴，那么鸽巢原理就能表示为 , i jxij.11,1,2,1,11,()()i niii nj ni ji ini jxxxxx 改写鸽巢原理的表示公
11、式得到鸽巢公式：.1 11,1,2,1,11,:()()n ni niii nj ni ji ini jPHxxxxx 在本公式中，符号是指任意一只鸽子，而是指全部所有的巢穴，是指否定，也就是不允许的意思.于是表示的是所有的11,1,2,()i niii nxxx 只鸽子都要飞进这个巢穴，中间的表示同时满足，右边1nn则表示不允许两只鸽子进同一个巢穴.1,11,()j ni ji ini jxx 性质 是一个极小不可满足公式.1n nPH证 （1）证明不可满足.假设公式1n nPH.1 11,1,2,1,11,:()()n ni niii nj ni ji ini jPHxxxxx 可满足，则
12、存在变元集合上的一个真值指派，,|11,1i jxinjn 使得（1.1）对每个.,1,2,11, ()1iii ninxxx （1.2）对每对以及每个11iin ,1, ()1i ji jjnxx由（1.1） ，对每个，存在某个，使得.由鸽11in 1jn,()1i jx巢原理：存在某对以及某个，使得, (11)i iiin (1)jjn.这与情形（1.2）矛盾.,()()1i ji jxx盐城师范学院毕业论文第 4 页共 15 页（2）证明极小不可满足.即证明：从中删去一个子句后，1n nPH1n nPHC得到的公式可满足.分两种情形讨论：情形 1 对某个.从中删去子句,1,2,(11),()iii ninCxxx 1n nPH后，得到公式：取一C111,1,2,1,11,()()i niii nj ni ji ini jFxxxxx 个真值指派如下：1. 1,11,21,11,12,2,0,( ) 1,0,|1nnnnn ni jxxxxxxxxxxxijn 我们有.直观上，删子句后，号鸽子可11()1F1,11,()nnnCxx1n以不进巢，于是，可以让 号鸽子进 号巢，.ii1in 情形 2 对某对及某个.(11)iin ,(1),()i ji jjn Cxx 不失一般性，假定.从中删去子句后，得到公式：,1,()n nn
