3.2-鸽巢原理

3.2鸽巢原理3.2.1有20只鸽子要飞往19个鸽巢栖息，这些鸽巢中至少有1个鸽巢里最少栖息着2只鸽子。如果k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体。鸽巢原理3.2.1例.在一组367个人中至少有2个人有相同的生日，因为只有366个可能的生日。例.27个英文单词中至少有2个单词以同一个字母开始，因为英文字母表中只有26个字母。例.如果考试分数从0到100，班上必须有多少个学生才能保证在这次期末考试中至少有2个学生得到相同的分数？有101个分数，所以根据鸽巢原理需要有102个学生才能保证至少有2个学生有相同的分数。3.2.2广义鸽巢原理当物体数超过盒子数的倍数时可以得出更多结果。比如21个十进制数中一定有3个是相同的。因为21个物体被分配到10个盒子里，那么某个盒子的物体一定多于2个。如果N个物体放入k个盒子，那么至少有一个盒子包含了至少𝑵/𝒌个物体。广义鸽巢原理例.在100个人中至少有𝟏𝟎𝟎/𝟏𝟐=9个人生在同一个月。3.2.2广义鸽巢原理例.如果有5个可能的成绩A、B、C、D、F，那么在一个班里至少要多少个学生才能保证至少6个学生得到相同的分数？解：所需的最少学生数是N，即N个成绩分数放入5个盒子里，有一个盒子中至少要有6个分数。𝑵/𝟓=6，从而得N=26练习P14515918N/50=100，N=99×50+1=4951在一个大学里每个学生来自50个州中的一个州，那么必须有多少个学生注册才能保证至少有100个学生来自同一个州？𝟔𝟕𝟕/𝟑𝟖=18一个公司在仓库中存储产品。仓库中的存储柜由它们的通道、在通道中的位置和货架来指定。整个仓库有50个通道，每个通道有85个水平位置，每个位置有5个货架。公司产品数至少是多少才能使得在同一个存储柜中至少有2个产品？50×85×5=21250根据鸽巢原理至少21251个产品例.从一副标准的52张牌中，必须选多少张牌才能保证选出的牌中至少有3张是同样的花色？解：花色为“盒子”，所以有4个盒子，需要1个盒子中至少有3个物体。𝑵/𝟒=3，所以N=93.2.2广义鸽巢原理例.从一副标准的52张牌中，必须选多少张牌才能保证选出的牌中至少有3张是红心？解：此题不使用广义鸽巢原理，因为要保证的不是同花色的牌，而是3张红心。考虑最坏的情况：在选1张红心之前，可能把所有黑桃、方块、梅花都选完了，共39张，之后再选的3张才是红心。所以需要选42张牌。练习P1452N/𝟐=2，N=3143.2.2广义鸽巢原理例.假设实验室有15台工作站和10台服务器。可以用一条电缆直接把工作站连到服务器。同一时刻只有一条到服务器的直接连接是有效的。如果想确保在任何时刻一组不超过10个的工作站可以通过直接连接同时访问不同的服务器，那么需要的最少直接连接数是多少？解：工作站𝐖𝟏𝐖𝟐…𝐖𝟏𝟎服务器𝐒𝟏𝐒𝟐…𝐒𝟏𝟎10条线𝐖𝟏𝟏𝐖𝟏𝟐𝐖𝟏𝟑𝐖𝟏𝟒𝐖𝟏𝟓每台连接到所有10个服务器10×5=50条线60条线3.2.2广义鸽巢原理解：工作站𝐖𝟏𝐖𝟐…𝐖𝟏𝟎服务器𝐒𝟏𝐒𝟐…𝐒𝟏𝟎𝐖𝟏𝟏𝐖𝟏𝟐𝐖𝟏𝟑𝐖𝟏𝟒𝐖𝟏𝟓每台连接到所有10个服务器如果𝐖𝟏—𝐖𝟏𝟎为一组工作站，那么满足在任何时刻10个工作站可以通过直连访问服务器。如果𝐖𝟏—𝐖𝟏𝟎中有1台不在组里，那么必定有𝐖𝟏𝟏—𝐖𝟏𝟓中的1台在组里，所以𝐖𝟏𝟏—𝐖𝟏𝟓的每台都连接到10台服务器，才可满足题意。证明至少60条连线：假设连线少于60，则某服务器至多连接𝟓𝟗/𝟏𝟎=5个工作站。这样剩下9台服务器和10个工作站，不能满足10个工作站同时访问不同的服务器。练习P1461920题目中的“盒子”是什么？“每台计算机连接其它计算机的台数”。那么“盒子”有几个？每台计算机连接其它计算机的台数的种类：连0台连1台连2台连3台连4台连5台盒子数是6吗？No！因为连0台的情况和连5台的情况不能并存，只存其一，所以盒子数目为5。所以与一台计算机连接的计算机数目至多有5种情况，𝟔/𝟓=2，即至少有2台计算机连接相同数目的其它计算机。将计算机标号为𝑪𝟏到𝑪𝟏𝟎𝟎，打印机标号为𝑷𝟏到𝑷𝟐𝟎。如果对于k=1,2,…，20，把𝑪𝑲连接到𝑷𝑲,并把𝑪𝟐𝟏到𝑪𝟏𝟎𝟎的每台计算机连接到每台打印机，那么共用了20+80×20=1620条线。现证明1619条线不够：1619条线连接20台打印机，那么每台打印机平均连接的计算机数为1619/20=80.9581台∴某台打印机连接的计算机数一定少于81台，即它连接到80台或者更少的计算机，∴有20台计算机没有与这1台打印机连接。共有20台打印机，这意味着剩下19台打印机需与20台计算机连接。如果恰是这20台计算机需要与20台不同的打印机连接，则数目不够。3.2.2广义鸽巢原理例.在30天的一个月里，某棒球队一天至少打一场比赛，但至多打45场。证明一定有连续的若干天内这个队恰好打了14场。解：令𝒂𝒋是这个月第j天或第j天之前所打的场数，则有1≤𝒂𝒋≤45(j=1,2,…,30),∴14≤𝒂𝒋+14≤59.所以有60个整数𝒂𝟏,𝒂𝟐,…,𝒂𝟑𝟎,𝒂𝟏+14,𝒂𝟐+14,…，𝒂𝟑𝟎+14都小于等于59。据鸽巢原理，这60个整数中有2个整数相等。而𝒂𝟏,𝒂𝟐,…,𝒂𝟑𝟎互不相等，所以𝒂𝟏+14,𝒂𝟐+14,…，𝒂𝟑𝟎+14也互不相等。则一定存在𝒂𝒊=𝒂𝒋+14，即第j+1天到第i天恰好打了14场比赛。练习P14621设𝒂𝒊是到第i小时为止所完成的比赛数。那么1≤𝒂𝟏𝒂𝟐⋯𝒂𝟕𝟓≤125,进而有25≤𝒂𝟏+24𝒂𝟐+𝟐𝟒⋯𝒂𝟕𝟓+24≤149有150个正整数都小于149，根据鸽巢原理至少有2个整数相等。由于所有的𝒂𝒊不相等，所有的𝒂𝒊+24也不相等，所以对某个ij,有𝒂𝒊=𝒂𝒋+24,∴在第j+1到第i小时之间恰有24场比赛。一个摔跤选手是75小时之内的冠军。该选手一小时至少赛一场，但总共不超过125场。证明：存在着连续的若干小时使得该选手恰好进行了24场比赛。