为什么一定会重复？

12个月是12个抽屉。每屉最多2人时，总数最多24人。因此25人一定有某个月至少3人出生。

24人可能每个月恰好2人，所以不能保证。答案是25人。

对象：人；抽屉：12个月；避开目标的总容量：12×2=24。

两只同色：3×1+1=4只足够。3只可能三种颜色各一只，所以4是最少数。

三只同色：3×2+1=7只足够。6只可能每色各两只，所以7是最少数。

“每种很多只”保证这些最坏安排确实可以出现。如果袋里每种只有1只，就不能照搬结论。

按得分分成101屉。如果每种分数最多2人，总人数最多202。203>202，所以至少有3人得分相同。

202人时，可以每种分数恰好2人。因此不能保证。

陷阱：抽屉数是101。少数一个抽屉，推理就会改变。

要同时避开三项目标，最多只能取3+2+4=9个。因此取10个时，至少一项成立。

取9个可能恰好是3红、2蓝、4绿，三项都不成立。所以最少是10个。

这里使用了德摩根律：否定“红达标或蓝达标或绿达标”，得到“红不达标且蓝不达标且绿不达标”。

把选中的11个数按上图归类。11个对象进10屉，至少一屉有两个选中的数，它们的和就是21。

只选1、2、…、10时，任意两数的和都小于21。所以10个不能保证。

关键：抽屉不是单个数，而是“能凑出21的一对数”。

把20个数分成10组：{1,2}、{3,4}、…、{19,20}。11个选中的数至少有两个来自同一组。这两个数相邻。

选1、3、5、…、19这10个奇数，就没有相邻数。因此不能把11改为10。

再走一步：相邻两个正整数的公因数只能是1。因为公因数也整除它们的差1。于是这11个数中还一定有两个互质的数；互质就是公因数只有1。

按除以5的余数分成5屉。6个数中至少有两个余数相同，设为5u+r与5v+r。差是5(u−v)，能被5整除。

数彼此不同，保证找到的是两个不同数。只取1、2、3、4、5时，余数各不相同，任何非零差都不到5，所以5个不够保证。

依余数归入上述4屉。5个数至少有两个同屉。

若两个余数相同，它们的差能被6整除；若同屉但余数不同，只可能是1与5，或2与4，余数之和是6，因此两数的和能被6整除。

余数0与3各自单独一屉，不会遗漏。四个数{1,2,3,6}的任意两数，和与差都不能被6整除，所以4个不能保证。

关键：一屉可以容纳几种余数，但必须证明“同屉”仍然能达到目标。

按“横坐标奇偶、纵坐标奇偶”分成4屉：偶偶、偶奇、奇偶、奇奇。5点至少两点同屉。

它们的横坐标之和是偶数，纵坐标之和也是偶数。所以中点坐标((x₁+x₂)/2，(y₁+y₂)/2)都是整数。

四种标签来自{偶,奇}×{偶,奇}，这里把笛卡尔积与乘法原理用在了分类上。

按提示把线段分成4个不重叠的部分，每部分长度为1/4。每点恰好归入一部分。5点进4屉，至少两点在同一部分，它们距离≤1/4。

不能改成严格小于。取0、1/4、1/2、3/4、1这5点，任意两点距离至少1/4。

另一种检查：把5点从左到右排列，相邻点产生4个间隔。如果每个间隔都大于1/4，总长就大于1，与都在线段里矛盾。

以左下角为原点。横坐标小于1的归左边，其余归右边；纵坐标小于1的归下边，其余归上边。这样分界线和角点都只有一个归属。

5点进4屉，至少两点同屉。同一小方格里，两点的水平距离和竖直距离都不超过1，因此它们的距离不超过该方格的对角线。

若已经学过勾股定理，就能进一步写成：距离的平方≤1²+1²=2，距离≤√2。还没学过时，保留“小方格的对角线长”的说法即可。

认识人数可能是0、1、2、3、4、5，但0和5不能同时出现：若有人认识其他所有5人，就不可能有人谁也不认识。

如果有0，则没人是5，最多5种人数；如果没有0，只有1到5，也最多5种人数。6个人进入至多5屉，至少两人同屉。

关键不只是“列出可能值”，还要检查这些值能否同时存在。这一步用到了条件之间的逻辑限制。

把五个数记为a₁、…、a₅。构造六个有编号的部分和：

按除以5的余数分成5屉，六个部分和中必有两个余数相同。设其编号i<j，则S_j−S_i能被5整除，而

这恰好是连续的一段；i<j保证它不是空段。

例如2、4、1、3、6的部分和是0、2、6、7、10、16。2与7同余，所以中间的4+1=5是一段符合要求的和。

关键：对象从“5个原数”变为“6个部分和”。漏掉S₀，就可能失去数量优势。

把1到10分成5屉：

它们不重叠，也没有漏数。6个选中的数至少有两个同屉。同屉的数都由同一个奇数反复乘2得到，所以较大数是较小数的整数倍。

只选6、7、8、9、10这5个数时，没有一个整除另一个：较小数乘2已经大于10。因此6确实是这个保证所需的最少数。

怎样发现这些屉？把每个数反复除以2，直到剩下奇数，按这个最后的奇数分类。这个奇数常叫它的“奇数部分”。

构造R₁=1、R₂=11、…、R_m，其中R_i有i个1。

如果某个R_i能被m整除，已经找到所需正整数。

否则，这m个数的余数只可能是1到m−1，只有m−1屉。于是有i<j，使R_i与R_j余数相同。因此R_j−R_i是m的正倍数。

这个差由j−i个1后接i个0组成，只有数字0和1。例如11111−111=11000。因此目标总能实现。

m=1时，第一个分支已经成功。这个证明保证存在，不保证找到的是最小的这种倍数，也不保证只用数字1就足够。

每列3个点、两种颜色，所以至少有一对同色点。每列选一对；若有多个选择，就按(1,2)、(1,3)、(2,3)的顺序选第一个同色对。这样每列只得到一个标签。

标签的行号对有3种，颜色有2种，共3×2=6种。7列进入6个标签屉，至少两列标签相同。

这两列在相同的两行上，都出现相同颜色的点。取这两行、两列的四个交点，就得到所需矩形。

这里用了两次抽屉思想：先保证每列有同色对，再保证两列得到同一个标签。

固定一个人甲。其余5人分成两类，所以至少有3人同属一类，记为乙、丙、丁。

情况一：乙、丙、丁都认识甲。若乙、丙、丁中某两人认识，这两人加上甲就是3人两两认识；若没有任意两人认识，乙、丙、丁本身就是3人两两不认识。

情况二：乙、丙、丁都不认识甲。若他们中某两人不认识，这两人加上甲就是3人两两不认识；若不存在这样的两人，他们三人就两两认识。

两种情况都得到题目的结论，证明完成。

注意：“都认识甲”不等于“彼此认识”。必须补上第二层分类讨论，不能到抽屉那一步就停止。

10个元素各有选或不选两种选择，共有2¹⁰=1024个子集，包括空集。每个子集的元素和都是0到990之间的整数，最多991种。

按总和分类，1024个子集进入最多991屉，因此有两个不同子集X、Y，总和相同。

如果它们有共同元素，把共同元素从两边都删去。剩下X∖Y与Y∖X，仍然总和相同，而且不相交。

它们都非空：X≠Y保证不会两边同时空；如果只剩一边空，另一边含正整数，其和就大于0，不可能相等。所以这两边就是需要的两组。

对象：1024个子集；抽屉：和的数值。最后还要处理“不相交”与“非空”，不能只停在两个子集不同。

本题据《Book of Proof》12.3节的子集和例题改编，并补充了不相交条件的论证。

至少一社：24+18−9=33人。

两社都不参加：40−33=7人。

恰好一社：(24−9)+(18−9)=24人，也可算24+18−2×9。

最后核对：恰好一社24人、两社都参加9人、都不参加7人，共40人。

4的倍数有120÷4=30个；6的倍数有120÷6=20个；共同的12的倍数有120÷12=10个。

因此至少能被其中一个整除的有30+20−10=40个。两者都不能整除的有120−40=80个。

不能总把两个除数直接相乘来找交集。4×6=24不是这里的最小公倍数，会漏掉12、36等共同倍数。

至少一组：24+21+18−10−8−7+4=42人。都不参加：50−42=8人。

恰好两组：(10−4)+(8−4)+(7−4)=13人。至少两组：13+4=17人。

注意10+8+7=25不是“至少两组”的人数，因为三组都参加的人被算了3次，应只留1次，所以也可算25−2×4=17。

倒过来求：若不知道三组都参加的人数x，但知道至少参加一组的有42人，则42=24+21+18−10−8−7+x，解得x=4。容斥也能用来恢复缺失的数据。

每个“指定位置是0”的集合有100种，两两交集各10种，三重交集只有000。因此至少一个0的有3×100−3×10+1=271种。

反面计数也得到10³−9³=1000−729=271。

恰好一个0：先选0的位置，有3种；另外两位只能用1到9，各9种。所以是3×9×9=243种。

若题目改成“三位正整数”，百位不能是0，样本范围就变了，不能直接使用这里的1000。

三个位置各给一个集合。用容斥，符合要求的结果数是3×36−3×6+1=91。

也可以数反面：三枚都不是6有5³=125种，所以216−125=91。

公平、独立条件下，216种基本结果等可能，因此概率是91/216。

直接算3×36=108，会让恰有两枚是6的结果被算两次、三枚是6的结果被算三次。容斥正是在修正这种重复。

固定某1人拿对，剩余3顶自由分配，有3×2×1=6种；有4个人可固定，因此单集合计数之和是4×6=24。

固定某2人拿对，剩余2顶有2种分法。人对共有{1,2}、{1,3}、{1,4}、{2,3}、{2,4}、{3,4}六种，因此两两交集计数之和是6×2=12。

固定某3人拿对，剩下一人也只能拿对，共1种；选这3人有4种，因此三重交集计数之和是4。四人全拿对只有1种。

至少1人拿对的分法有24−12+4−1=15种。每个人都拿错的有24−15=9种。

也可合写成24−24+12−4+1=9。这里减掉的是“至少一人拿对”，不能只减“恰好一人拿对”。

和为6：(1,5)、(2,4)、(3,3)、(4,2)、(5,1)，共5种，概率5/36。

和为7有6种，概率1/6；和为8有(2,6)、(3,5)、(4,4)、(5,3)、(6,2)，共5种，概率5/36。因此和为7最常见，6与8同样常见。

和为10有3种，和为11有2种，和为12有1种，共6种。概率6/36=1/6。

三类互不重叠，所以用加法原理直接相加。不必减交集。

每枚骰子都有3个奇数面、3个偶数面。奇奇有3×3=9种，偶偶也有9种。两类不重叠，所以共18种，概率18/36=1/2。

“奇偶”与“偶奇”使和为奇数，也各有9种，可以用来核对剩余的18种。

和为偶数有18种；至少一枚是6有11种。交集是(6,2)、(6,4)、(6,6)、(2,6)、(4,6)，共5种。

所以并集有18+11−5=24种，概率24/36=2/3。

也可以检查反面：“和为奇数，且两枚都不是6”。只看1到5，每枚有3个奇数、2个偶数，异奇偶共有3×2+2×3=12种；36−12=24。

在“至少一枚是6”的条件下，仍可能的基本结果有11种。其中和为7的只有(1,6)与(6,1)，所以条件概率是2/11。

若已知“甲骰是6”，仍可能的只有(6,1)、…、(6,6)共6种；和为7只有(6,1)，概率为1/6。

条件不同，留下来的样本范围不同。计算时要保留题目给出的那一句条件，不能把“至少一枚”换成“甲骰”，或反过来。

全部基本结果有6×6×6=216种。全部不同有6×5×4=120种。

所以至少两枚相同有216−120=96种，概率96/216=4/9。取反面自动把“恰好两枚相同”和“三枚全相同”都包括进来，避免重复相加。

和为9共有25种有序结果，概率25/216；和为10共有27种，概率27/216=1/8。所以和为10更可能。

三个不同数有3×2×1=6种排序；恰有两个相同，选择那个不同数所在的位置，只有3种；全相同只剩1种。

原来的错误是：把大小不同的几组基本结果，当成了等可能的组。“有六种组合”本身并不能决定概率。

6次共有6⁶=46656种等可能的有序结果。全部不同有6×5×4×3×2×1=720种。

这个概率已经很高，但仍然小于1；例如1、2、3、4、5、6就没有重复。

掷7次时，7次投掷是对象，6种点数是抽屉。7个对象进6屉，必有两次点数相同。在这里的有限模型中，重复事件就是全部样本空间，概率为1。

保证7次有重复，只需要“每次结果是1到6之一”；即使骰子不公平，抽屉原理的结论也不变。

编号n取1到30，2n−1恰好遍历1、3、…、59。反过来，奇数a对应编号(a+1)/2，恰好在1到30之间。

两个规则互相还原，因此这批正奇数与30个编号一一对应，共30个。

每个两人小组S对应“其余四人”组成的集合U∖S。每个四人小组也能取补集，回到唯一的两人小组。因此这是一个双射。

选两人：先选第一人有6种，再选另一人有5种；每个不分先后的小组计了2次，所以有6×5÷2=15种。选四人也有15种。

这个对应不涉及选取的先后；如果两人分别担任正、副组长，就不能把交换两人的方案合并。

每条路线对应一个含4个R、3个U的七位串，也对应{1,…,7}中的一个三元素子集，记录U的位置。

选定这些位置后，另外4个位置只能填R，因此路线唯一。任何这样的三元素子集也都能生成一条合法路线。

所以路线数为C(7,3)=7×6×5÷(3×2×1)=35。每一组位置都被6种选择顺序重复计算，除以6才得到不分先后的选择数。

每盒非空：写下5个球，在4个内部空隙中选择2个放隔板。例如“●｜●●｜●●”表示(1,2,2)。读出三段球数可得到唯一分法，反向也唯一。因此共有C(4,2)=4×3÷2=6种。

允许空盒：改用含5个球符号和2个隔板符号的七位串。例如“｜●●｜●●●”表示(0,2,3)，“●●●●●｜｜”表示(5,0,0)。从7个位置中选2个放隔板，其余放球，共C(7,2)=21种。

相邻隔板、开头隔板与末尾隔板分别记录相应的空段。按盒号读出三段长度，仍然可以双向还原。三个盒子有编号，所以(1,2,2)与(2,1,2)是不同分法。

按人统计参与记录，有8×7=56条。按握手统计，每次产生2条参与记录，若握手H次，就有2H条。因此2H=56，得到H=28。

除以2是因为每次握手恰好有两名参与者，而不是因为题目中出现了“两人”就机械地除以2。

按学生统计，共有12×2=24条报名记录。设每个社团有x人，按社团统计就是4x条。因此4x=24，x=6。

社团允许成员重叠，所以不能把12直接除以4。容斥会用于求不重复的人数；这里的目标是各社团的人数，数报名记录即可。

不可能。每一对相互认识的人都贡献2，因此全部认识人数之和是偶数。

如果恰好3人的认识人数是奇数，其余都是偶数，这个总和就会是奇数，产生矛盾。

同样的理由说明：认识人数为奇数的人，人数一定是偶数。这把双重计数得到的等式，与奇偶性结合起来。

先选k人小组，有C(n,k)种；再从组内选组长，有k种，共k C(n,k)种。

先选组长，有n种；再从剩下n−1人中选k−1名普通组员，有C(n−1,k−1)种，共n C(n−1,k−1)种。

每个“小组及其组长”在两种方法中都恰好出现一次，因此两个结果相等。

k=1时，组长选好后不再选其他人。C(n−1,0)=1，因为空集是唯一的零人选择。