5-抽屉原理.ppt

第四讲抽屉原理巩胆亨乾鳃敷轧官莱劣秽烯湃襄蹲瘁忻狈示脊粥垫察万灯蛀爷芍睛棚玉证5-抽屉原理5-抽屉原理抽屉原理又称鸽巢原理,是组合数学中两大基本原理之一,,,-抽屉原理5-,,从中任取11只,则至少有两只是一双。-抽屉原理5-抽屉原理抽屉原理的简单形式;如果将n+1个物体放入n个盒子中,那么至少有一个盒子包含两个或更多的物体。等价形式:(Ⅰ)如果将n个物体放入个n盒子中,并且没有一个盒子是空的,那么每个盒子恰好包含一个物体。(Ⅱ)如果将n个物体放入个n盒子中,并且没有盒子放入多于一个的物体,那么每个盒子恰好包含一个物体。-抽屉原理5-(抽屉原理的推广形式)若将多于n件物品任意放入n个盒子,,必须找到所对应的物品和盒子,-抽屉原理5-抽屉原理例任意三个整数,必有两个之和为偶数(其差也是偶数)。证明:制造两个抽屉:“奇数”和“偶数”,3个数放入两个抽屉中,必有一个抽屉中至少有两个数,由整数求和的奇、偶性质即知此二数之和必为偶数。同理可知,二者之差也为偶数。-抽屉原理5-抽屉原理例证明:在边长为2的正方形中,任意给定5个点,必有两点其距离不超过证明:把边长为2的正方形分成4个边长为1的小正方形,则每个小正方形的对角线长为如果把每个小正方形当作盒子,由抽屉原理知,把5个点放到4个盒子中,必有一个盒子中放入了两个点,即必有一个小正方形中有两个点。而小正方形的对角线长为也就是说,-抽屉原理5-抽屉原理例任取11个整数,求证其中至少有两个数,他们的差是10的倍数。证明:设这11个数为,它们被10除后其余数为0~9之间的整数。由抽屉原理知,必有两个数,,它们的余数相等,从而即它们两者的差是10的倍数。-抽屉原理5-抽屉原理例试证明任意给定的52个整数,它们之间必有两个数,:设为这52个整数的集合,记,则构成了51个抽屉,从而存在一个抽屉,使得设则除以100,其余数要么相同,要么其和为100。如果余数相同,则这两数之差是100的倍数;如果余数其和为100,则这两数之和是100的倍数。-抽屉原理5-抽屉原理例有n位代表参加会议,若每位代表至少认识另外一个代表,则会议至少有两人认识的人数相同。证明:设某位代表认识的人数为个,则(视为n-1个抽屉),而会议上有n个代表,故每位代表认识的人数共有n个数(视为n个物品),那么由基本定理,结论成立。-抽屉原理5-抽屉原理