毕业论文-鸽巢原理在数学领域的应用

[键入文字]鸽巢原理在数学领域的应用摘要组合数学是现代数学的重要分支，而鸽巢原理是组合数学中最基本最重要的概念之一，具有广泛的应用价值.本文首先介绍了鸽巢原理的定义及其相关的公式和性质.接着重点讨论了鸽巢原理的应用，包括其在几何图形、数的整除、连续时间、人的相识和染色问题等领域的应用，并给出相关的计算公式.最后，我们进一步认识了鸽巢原理并得出其在诸多数学领域中都有重要的应用.【关键词】组合数学鸽巢原理[键入文字]ApplicationofthePigeonholePrincipleinthefieldofmathematicsAbstractCombinatorialmathematicsisoneoftheimportantbranchesofmodernmathematics,andthePigeonholePrincipleisabasicandmostimportanttheoremincombinatorialmathematics.Inthispaper,wefirstintroducethedefinitionandsomepropertiesofthePigeonholePrinciple,togetherwiththerelativefunctions.ThenwemainlyfocusontheapplicationsofthePigeonholePrinciple,suchasitsapplicationsongeometricfigures,divisibleproblemsofnumbers,continuoustime,humanknowledge,coloringproblemsandsoon.Wealsoobtaintheircountingformulas.ThuswehaveafurtherstudyofthePigeonholePrincipleandfinditsapplicationsonmanybranchesofmath.[Keywords]combinatorialmathematicsPigeonholePrinciple[键入文字]目录引言..............................................................11鸽巢原理的概念......................................................11.1定义...........................................................11.2鸽巢原理的一般表现形式.........................................11.3鸽巢公式及其性质...............................................21.4带中介的鸽巢公式及其性质.......................................42鸽巢原理在多领域的应用..............................................72.1鸽巢原理在几何图形方面的应用...................................72.2鸽巢原理在数的整除关系中的应用.................................82.3鸽巢原理在“连续时间”问题上的应用.............................92.4鸽巢原理在“人的相识”问题上的应用............................102.5鸽巢原理在“染色问题”上的应用................................112.6数学竞赛中几种常见的鸽巢类型..................................123结束语.............................................................14参考文献..........................................................15第1页共15页引言课桌上有八个苹果，要把这八个苹果放进七个抽屉中，无论怎样放，我们会发现有一个抽屉里面至少有个苹果，这一现象就是“抽屉原理”.抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有1n或多于1n个元素放到n个集合中去，其中必定至少有一个集合里有两个元素”.抽屉原理也被称为“鸽巢原理”（如果有七个鸽笼，养鸽人养了八只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有两只鸽子”），它在组合数学中占据着非常重要的地位，常被用来证明一些关于存在性的数学问题.鸽巢原理不仅在组合数学的研究中起着关键作用，而且在求解几何图形、数的整除、连续时间、人的相识和染色问题等数学领域中都有着重要作用.1鸽巢原理的概念1.1定义一般的鸽巢原理：n个鸽巢，若有1n只鸽子在里面，则至少有一个鸽巢里至少有两只鸽子.推论1m只鸽子，n个鸽巢，则至少有一个鸽巢里有不少于11mn只鸽子.推论2若有1nm只鸽子飞进n个鸽巢，则至少有一个鸽巢里有m只鸽子.推论3如果有n个整数12,,nmmm…,的平均数大于1r，即12)1nmmmnr…，则12,,nmmm…,中至少有一个整数不小于r.1.2鸽巢原理的一般表现形式抽屉原理是由数学家狄利克雷首先提出，并用于证明一些数论中的问题，因此，也被称为狄利克雷原则.把鸽巢原理推广到一般情形有以下几种表现形式：形式一把1n个元素划分到n个集合中12,,,nAAA…，用12,,,naaa…分别表示这n个集合对应包含的元素个数，则至少存在某个集合iA，其包含的元素个数2ia.第2页共15页证（用反证法）假设结论不成立，即对每一个ia都有2ia，则因为ia是整数，应有1ia，于是121111naaann……，这与题设矛盾.所以，至少有一个2ia，即必有一个集合中含有两个或两个以上的元素.形式二把1nm个元素划分到n个集合中12,,,nAAA…，用12,,,naaa…表示这n个集合对应包含的元素个数，则至少存在某个集合iA，其包含的元素个数1iam.证（用反证法）假设结论不成立，即对每一个ia都有1iam，则因为ia是整数，应有iam，于是121naaammnmnm……m，这与题设矛盾.所以，至少存在一个1iam.形式三设把n个元素分为k个集合12,,,kAAA…，用12,,,kaaa…表示这k个集合里相应的元素个数，则：至少存在某个ia都有iank.证（用反证法）设结论不成立，即对每一个ia都有iank，于是12**kaaanknknkknkknkn……，这与题设相矛产生矛盾.所以，必有一个集合中元素nk.形式四设把121kqqqn…个元素分为n个集合12,,,nAAA…，用12,,,naaa…表示这n个集合里相应的元素个数，则：至少存在某个ia，使得iiaq.证（用反证法）设结论不成立，即对任意的ia都有iiaq，因为ia为整数，应有1iiaq，1212121nnnaaaqqqnqqqn………，这与题设发生矛盾.所以，假设不成立，故必有一个i，在第i个集合中元素iiaq.形式五令无穷多个元素分成有穷多个集合，则至少存在一个集合，它含有无穷多个元素.证（用反证法）将无限多个元素划分至有限个集合，先假设这有限个集合中元素的个数全是有限个，那么有限个有限数相加之和必是有限数，这就与题设发生矛盾，因此假设不成立，故必有一个集合含有无穷多个元素.1.3鸽巢公式及其性质第3页共15页在组合学和人工智能中，很多原理和问题可以用命题公式表示.这些公式在适当变形其结构后，就会出现很多有趣的性质，比如极小不可满足性、对称性、子结构同构性、消解难例等等.著名的鸽巢公式就来自于组合学中的鸽巢原理.鸽巢原理是指：1n只鸽子进入n个巢穴，必有一个巢穴至少有2只鸽子.我们引入变元,ijx指i只鸽子进入j号巢穴，那么鸽巢原理就能表示为''11,1,2,1,11,()(())iniiinjnijiinijxxxxx….改写鸽巢原理的表示公式得到鸽巢公式：''111,1,2,1,11,:()(())nniniiinjnijiinijPHxxxxx….在本公式中，符号是指任意一只鸽子，而是指全部所有的巢穴，是指否定，也就是不允许的意思.于是11,1,2,()iniiinxxx…表示的是所有的1n只鸽子都要飞进这n个巢穴，中间的表示同时满足，右边''1,11,(())jnijiinijxx则表示不允许两只鸽子进同一个巢穴.性质1nnPH是一个极小不可满足公式.证（1）证明1nnPH不可满足.假设公式''111,1,2,1,11,:()(())nniniiinjnijiinijPHxxxxx….可满足，则存在变元集合,|11,1ijxinjn上的一个真值指派，使得（1.1）对每个,1,2,11,()1iiininxxx….（1.2）对每对'11iin以及每个',,1,()1ijijjnxx由（1.1），对每个11in，存在某个1jn，使得,()1ijx.由鸽巢原理：存在某对'',(11)iiiin以及某个''(1)jjn，使得''',,()()1ijijxx.这与情形（1.2）矛盾.（2）证明1nnPH极小不可满足.即证明：从1nnPH中删去一个子句C后，得到的公式可满足.分两种情形讨论：第4页共15页情形1对某个,1,2,(11),()iiininCxxx….从1nnPH中删去子句C后，得到公式：''111,1,2,1,11,()(())iniiinjnijiinijFxxxxx…取一个真值指派1如下：1,11,21,11,12,2,,0,,,,()1,,,,0,|1nnnnnnijxxxxxxxxxxxijn…….我们有11()1F.直观上，删子句1,11,()nnnCxx…后，1n号鸽子可以不进巢，于是，可以让i号鸽子进i号巢，1in.情形2对某对'(11)iin及某个',,(1),()ijijjnCxx.不失一般性，假定,1,()nnnnCxx.从1nnPH中删去子句C后，得到公式：''211,1,11,11,()(())iniinjnijiinijFxxxx…''11,1,,1,()()ininnniniininxxxx.取一个真值指派2如下：,1,21,11,1,1,11,21,11,,()1,,,0,|1,,,nnnnnnijnnnnxxxxxxxxxijnxxx…….我们有22()1F.直观上，删去子句,1,()nnnnCxx后，允许,1nn号鸽子同时进入n号巢.于是，可以让i号鸽子进i号巢，11in.综上所述，1nnPH是极小不可满足公式.1.4带中介的鸽巢公式及其性质鸽巢公式的一个真值指派可以用一个边带标记的完全二分图表示.现插入一中介结点集合于完全二分图中，即可将鸽巢公式推广到带中介的情形,继而形成了一种新的消解难例公式，也就是带中介的鸽巢公式.第5页共15