北京航空航天大学软件学院
组合数学论文
论文题目： 抽屉原理及其应用 姓 名： 学 号：
专 业： 集成电路与物联网工程
Beihang College of Software 北航软件学院
目 录
摘 要 ....................................................................................................................................... 2 Abstract ................................................................................................................................... 3 1.引言 ....................................................................................................................................... 4 2.抽屉原理的形式 ................................................................................................................... 4 3.抽屉原理的构造 ................................................................................................................... 5
3.1分割图形构造抽屉 .................................................................................................... 5 3.2利用划分数组来构造抽屉 ........................................................................................ 6 3.3利用划分集合来构造抽屉 ........................................................................................ 6 3.4利用等分区间构造抽屉 ............................................................................................ 7 3.5利用奇偶性分类构造抽屉 ........................................................................................ 8 3.6利用状态制构造抽屉 ................................................................................................ 8 4.抽屉原理的应用 ................................................................................................................... 9
4.1抽屉原理在数学中的应用 ........................................................................................ 9 4.1.1解决代数问题 ........................................................................................................ 9 4.1.2解决数论问题 ...................................................................................................... 10 4.1.3解决几何问题 ...................................................................................................... 11 4.2抽屉原理在生活中的应用 ...................................................................................... 11 4.2.1手指纹和头发 ...................................................................................................... 11 4.2.2电脑算命 .............................................................................................................. 12 4.2.3招生录取 .............................................................................................................. 12 5.总结 ..................................................................................................................................... 13 参考文献 ................................................................................................................................. 13
1
Beihang College of Software 北航软件学院
摘 要
抽屉原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用。
本文简单介绍了抽屉原理的几种形式，本文主要研究抽屉原理的抽屉构造和原理的应用。构造主要研究抽屉原理经常使用的几种构造方式：分割图形构造法，整数性质构造法（同余类构造法、划分数组构造法），间接转换构造法（染色体构造法）。应用主要从数学领域的应用和现实生活中的应用两大方面进行研究，数学领域方面主要应用于代数、数论、几何等几方面的解题，现实生活中大多数用于电脑算命，预测某些存在性的结果等等。 关键词：抽屉原理；“抽屉”的构造；抽屉原理的应用
2
Beihang College of Software 北航软件学院
Abstract
Drawer principle is a mathematical combination of problem of the existence of one of the basic principles of non conventional problem solving method, is also one of the important types in number theory and combinatorics, has a wide range of applications.
This paper briefly introduces the principle of drawer in several forms, This paper mainly studies the principle of drawer drawer structure and the application of the principle. Tectonic research drawer principle often use several construction methods: segmentation graph construction method, construction method of integer properties ( congruence class construction method, construction method of dividing the array ), indirect conversion method of construction ( chromosome construction method). Application mainly from the mathematical field of application and the reality of life in the application of the two major aspects of research, mathematical fields mainly used in number theory, algebra, geometry and so on several aspects of the problem solving, in real life, most used computer fortune-telling, predict some existence results etc. Key words： Drawer Principle；\；principle application
3
Beihang College of Software 北航软件学院
1.引言
抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，抽屉原理是离散数学中的一个重要原理，它是由德国著名数学家狄利克雷(P.G.T.Dirichlet 1805-1855)首先发现的，因此也叫作狄利克雷原理。
抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法。
本文将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用。
2.抽屉原理的形式
什么是抽屉原理？先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理.或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来。
抽屉原理简单直观，很容易理解。而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来。
下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用。
我们最常用的抽屉原理只是抽屉原理的简单形式，就是将n+1个元素或者更
多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素。
除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式。 陈景林、阎满富在他们编著的《组合数学与图论》一书中将抽屉原理抽象概括成以下三种形式[1]:
原理1. 把多于n个的元素按任一确定的方式分成n个集合，则一定有一个集合中含有两个或两个以上的元素。
原理2. 把m个元素任意放到n(m?n)个集合里，则至少有一个集合里至少有k个元素，其中
?m , 当n能整除m时,??n4 k???m?? ?1 , 当n不能整除m时. ?????n?