鸽巢原理-与-双重计数

《鸽巢原理-与-双重计数》由会员分享，可在线阅读，更多相关《鸽巢原理-与-双重计数（28页珍藏版）》请在金锄头文库上搜索。

1、 鸽巢原理 与 双重计数 Pigeon-hole and double counting福州大学数学与计算机科学学院常安2014年10月16日 鸽巢原理(Pigeon-hole principle)鸽巢原理是组合数学中最简单也是最基本 的原理，也叫抽屉原理。即 “若有n个鸽子巢，n+1个鸽子，则至少有 一个巢内有至少有两个鸽子。”例 367人中至少有人的生日相同。 例 10双手套中任取11只，其中至少有 两只是完整配对的。 例 参加一会议的人中至少有人认识 的其他参加者的人数相等。例 从1到2n的正整数中任取n+1个，则这n+1 个数中，至少有一对数，其中一个是另一个的倍 数。证：设n+1个数

2、是 a1 , a2 , , an+1。每个数去 掉一切2的因子，直至剩下一个奇数为止。 组成序列 r1 , r2, , , rn+1。这n+1个数仍在 1 , 2n中，且都是奇数。而1 , 2n中只有n个 奇数 . 故必有 ri = rj = r , 则 ai = 2i r, aj = 2j r 若ij ，则 ai 是 aj 的倍数。鸽巢原理(Pigeon-hole principle)例 设 a1 , a2 , , am是正整数序列，则至少存在k和 l , 1k l m，使得和ak + ak+1 + + al 是m的倍数。证 设Sk = ai , Sh rh (mod m), 0rhm-1

3、h = 1 , 2 , , m . 若存在 l , Sl0 (mod m), 则 命题成立否则，1rhm-1但h = 1 , 2 , , m由鸽巢原理，故存在 rk = rh , 即 Sk Sh (mod m) ，不妨设 h k则ShSk = ak+1 + ak+2 + + ah 0 (mod m) i=1h鸽巢原理(Pigeon-hole principle)例 设 a1 , a2 , a3为任意个整数，b1b2b3 为a1 , a2 , a3的任一排列，则 a1b1 , a2b2 ,a3b3中至少有一个是偶数证 由鸽巢原理， a1 , a2 , a3必有两个同奇 偶设这个数被除的余数为 x

4、xy，于 是b1 , b2 , b3中被除的余数有个x，一个 y这样a1b1 , a2b2 , a3b3被除的余 数必有一个为鸽巢原理(Pigeon-hole principle)例 设a1 , a2 , , a100是由 1和组成的序 列 , 已知从其任一数开始的顺序10个数的和 不超过16即ai + ai+1 + + ai+9 16，1 i 91 则至少存在 h 和 k ，k h，使得ah + ah+1 + + ak = 39 证 令 Sj = ai，j =1 , 2 , ,100 显然 S1h SkSh =39 即ah + ah+1 + + ak = 39 鸽巢原理(Pigeon-hol

5、e principle)鸽巢原理推广 设m1 , m2 , , mn都是正整数， 并有m1 + m2 + +mnn + 1个鸽子住进n个 鸽巢，则至少对某个 i 有第 i 个巢中至少有 mi个鸽子，i = 1 , 2 , , n前面的鸽巢原理一是这一原理的特殊 情况，即m1 = m2 = = mn= 2，m1 + m2 + +mnn + 1 = n + 1 如若不然，则对任一 i， 都有第 i 个巢中的 鸽子数mi1 则鸽巢原理(Pigeon-hole principle)鸽子总数 m1 + m2 + +mnn ， 与假设相矛盾 推论 m只鸽子进n个巢，至少有一个巢 里有 |只鸽子nm推论 n

6、(m1) + 1只鸽子进n个巢，至少 有一个巢内至少有m只鸽子 推论 若m1 , m2 , , mn是正整数，且 r1,则 m1, , mn至少有一个 不小于rm1 + +mnn鸽巢原理(Pigeon-hole principle)例 将 1 , 65 划分为个子集，必有一个 子集中有一数是同子集中的两数之差证 用反证法设此命题不真即 存在划分P1 P2 P3P4 1，65 ，Pi 中不存在一个数是Pi中两数之差，i=1,2,3,4 因 = 17，故有一子集，其中至少有17 个数，设这17个数从小到大为a1 , , a17 不妨设 A=a1 , , a17 P1。 令bi1= aia1，i =

7、 2，17。654鸽巢原理(Pigeon-hole principle)设 Bb1 , , b16，B 1 , 65 。 由反证法假设BP1 = 。因而B( P2 P3 P4 )。因为 6，不妨设b1 , , b6P2 ，令Ci1=bib1，I = 2， ，6 设C C1 , , C5 ，C 1 , 65 由反证法假设C( P1P2 ) =，故有 C(P3P4 ) 因为 3，不妨设C1 , C2 , C3 P31635 2鸽巢原理(Pigeon-hole principle)令 di1= CiC1，I = 2 , 3 设 D d1 , d2 , D 1 , 65。 由反证法假设 D( P1P2

8、P3 )=，因而D P4 。 由反证法假设d2d1 P1P2P3 且d2d1 P4 ， 故 d2d1 1 , 65 ，但显然d2d1 1 , 65 ， 矛盾。鸽巢原理(Pigeon-hole principle)Ramsey 问题Ramsey问题可以看成是鸽巢原理的推 广下面举例说明Ramsey问题例 6 个人中至少存在人相互认识或者 相互不认识证 这个问题与K6的边着色存在同色三 角形等价假定用红蓝着色Ramsey 问题设K6的顶点集为v1 , v2 , , v6 ，dr(v)表 示与顶点 v 关联的红色边的条数，db(v)表 示与 v 关联的蓝色边的条数在K6 中，有 dr(v) db(v

9、)，由鸽巢原理可知，至少 有条边同色现将证明过程用判断树表示如下：Ramsey 问题dr(v1)3?db(v1)3设(v1v2) (v1v3) (v1v4)为红边设(v1v2) (v1v3) (v1v4)为蓝边v2v3v4是红 ?v2v3v4是蓝 ?设( v2v3 )是蓝边设( v2v3 )是红边v1v2v3是蓝v1v2v3是红YNNNYYRamsey数问题的一般化：给定一对正整数a、b，存 在一个最小的正整数 r ,对 r 个顶点的完全 图的边任意红、蓝着色，存在 a 个顶点 的红边完全图或 b 个顶点的蓝边完全图。 这个最小正整数称Ramsey数，为记为r ( a , b )。 比如：r

10、( 3 , 3 )6，r ( 3 , 4 )9，r ( 4 , 4 )18a3 3 3 3 3 3 3 4 4b3 4 5 6 7 8 9 4 5 r(a, b)6 9 14 18 23 28 36 18 25目前已知的Ramsey数Ramsey数双重计数（Double counting ） 双重计数（double counting）也称 为双向计数（ counting in two ways）计数原理：设R和C是两个有限集， 且SRC. 当(p, q)RC, 称p与q是相 关联的. 如果rp表示与p相关联的元素 个数，Cq表示与q相关联的元素个数， 则有集合的关联矩阵：A=(apq) 其中双

11、重计数（Double counting ） 双重计数（Double counting ） 例 1 设G=(V, E)是一个简单图，其中V是 顶点集，E是边集. 则有 证明可以通过考虑集合SVE, 即所有 序对(v, e)的集合，这里vV是边eE的一 个端点. 例2 An extremal problem on graphs双重计数（Double counting ） 双重计数（Double counting ） 双重计数（Double counting ） 双重计数（Double counting ） 双重计数（Double counting ） P. Erdos(1913-1996)是一位匈牙利的数学家。1984年 获得“沃尔夫奖”（Wolf Prize），当年就是由他和 华裔美籍的陈省身教授平分。Erdos是当代发表最多 数学论文的数学家，也是全世界和各种各样不同国 籍的数学家合作发表论文最多的人。他发表了近 1000篇的论文，平均一年要写和回答1500多封有关 于数学问题的信。To those who believe in The BOOK谢谢同学们！