数学大学
看得见摸得着的鸽巢
组合数学 · 容斥原理和鸽巢原理
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
看得见摸得着的鸽巢
组合数学 · 容斥原理和鸽巢原理
鸽巢原理的应用（2）
鸽巢原理的强化版：n 个鸽子 n−1 个巢，必有双鸽同巢——保证「存在性」。
简单形式
n+1 个物体放进 n 个巢，必有两物同巢
构造巢
难题的关键是把物件按规则「造巢」
韩信点兵
韩信点兵数士兵：按 3、5、7 报数的余数反推总人数。
余数定数
三个除数的余数足以锁定模 105 的解
口诀
「三人同行七十稀」歌诀即系数记忆法
中国剩余定理
中国剩余定理（CRT）：两两互质的模数下，同余方程组必有唯一解。
定理内容
模两两互质时解在模 M 下唯一存在
构造
各模数贡献一项，线性组合出解
本节要点
- ✓鸽巢保证存在性，造巢是关键
- ✓韩信点兵：余数反推人数
- ✓CRT：互质模下同余方程组唯一解
延伸主题：解一个二元 CRT 方程组用鸽巢证一个整除结论
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1鸽巢原理证明了「存在」，为什么还这么有用？
参考答案许多问题的难点只是「有没有」，例如「存在两人生日相同」。鸽巢以最朴素的不等式给出确定性结论，且通过精心设计「巢」（如按余数分类），能把看似无关的命题一举证出。
2中国剩余定理「唯一」到什么程度？
参考答案唯一是模 M = 各模数乘积意义下的唯一：在 0 到 M−1 之间恰有一个解，所有解都是它模 M 的同余类。互质性是保证各余数信息互不冲突的关键。
3韩信点兵与 CRT 的关系是什么？
参考答案韩信点兵正是 CRT 的历史原型与特例：模 3、5、7 两两互质，三个报数余数确定模 105 的唯一人数。CRT 把这类「除数余数」问题的可解性与解法一般化。