数学广角——鸽巢问题

官方数学老师·14 页·入门(第一次接触这个概念)·0 次浏览·2 天前
数学广角组合原理逻辑思维入门必学

数学广角——鸽巢问题

5只鸽子进4个笼子,搞懂"至少挤一窝"背后必然发生的数学规律

按 空格/→ 演示下一步

1 / 14 页

全部页面点击任意一页,跳回舞台从这页播放

数学广角组合原理逻辑思维入门必学

数学广角——鸽巢问题

5只鸽子进4个笼子,搞懂"至少挤一窝"背后必然发生的数学规律

1第 1 页 · 数学广角——鸽巢问题

把东西放进抽屉

家里4本书要放进3层书柜。随手一放,每层真的都能只放1本吗?

问题情境
把4本书放进3个抽屉,书比抽屉多1本
无论怎么放
不管你选哪种摆法,总有一个抽屉至少装2本
反着想就懂
若每屉最多1本,3屉最多放3本,第4本无处可去
鸽巢原理
东西比抽屉多时,至少一个抽屉要装进不止一个
鸽子飞回鸽巢对应 →鸽巢原理

鸽子比巢多,必有巢挤进不止一只

43=2\left\lceil \frac{4}{3} \right\rceil = 2
2第 2 页 · 把东西放进抽屉

经典的「鸽巢问题」

上一页我们把东西塞进抽屉,今天换成鸽子飞回鸽巢——10 只鸽子,9 个鸽巢,不管怎么飞,会发生什么?

鸽子比巢多
10 只鸽子要飞进 9 个鸽巢,数量上鸽子比鸽巢多了 1 只
必有「同巢」
无论怎么分配,至少有一个鸽巢会住进 2 只或更多鸽子
无法回避
这不是碰巧,而是数学上「一定」会发生,没有例外
10 个小朋友抢 9 把椅子对应 →鸽巢问题

椅子少一把,必定有小朋友要和别人挤同一把

n+1 只鸽子进 n 个巢某巢2 只n+1 \text{ 只鸽子进 } n \text{ 个巢} \Rightarrow \exists \text{某巢} \geq 2 \text{ 只}
3第 3 页 · 经典的「鸽巢问题」

什么是抽屉原理

刚才我们看到 5 只鸽子飞进 4 个窝,至少有一窝住 2 只。把这个发现抽出来,就得到一条通用规律——抽屉原理。

数量关系
物品比抽屉多 1:n+1 个物品放进 n 个抽屉
必然结论
不管怎么放,至少一个抽屉里有 ≥2 个物品
「一定」的保证
抽屉装不下「每件单独放」,多出的必须挤一起
3 个学生抢 2 把椅子对应 →n+1 个物品放 n 个抽屉

椅子不够每人一把,必有人共用 → 抽屉同理

$$n+1 \text{ 个物品} \to n \text{ 个抽屉} \Rightarrow \exists \text{ 抽屉装有} \geq 2 \text{ 个}$$
4第 4 页 · 什么是抽屉原理

抽屉原理的图解

从左往右读:5只鸽子住进3个抽屉,无论怎么分,必有一个抽屉住进2只或更多。

图解渲染中…
res虚线代表'必然推出'——无论怎么分都成立
5第 5 页 · 抽屉原理的图解

极端思维

上页我们用图看到了「重复」是怎么发生的。但光看图还不够——有没有一种方法,不用挨个摆,就能直接断定「一定会重复」?有!它叫极端思维。

假设不重复
先想象最理想情况:每个抽屉里放的东西全都不一样
数出最大值
在这个假设下数一数,最多能放多少个「不重复」的
超出就重复
实际数量只要超过这个最大值,就一定有东西重复了
插座给手机充电对应 →极端思维

假设每个插座只充一台设备,最多同时充几台;多一台,必然两台挤同一插座

6第 6 页 · 极端思维

平均分配

上节课我们用极端思维想的是——先把多的装满一个抽屉。其实真正做题的第一步,是先「平均分」:把东西尽量均匀地塞进每个抽屉,看看每人最少拿到多少、还剩几个没分完。

平均分配
把总数尽量均匀地塞进每个抽屉,让每个抽屉的数量尽量一样多
每人至少几个
用「总数 ÷ 抽屉数」求商,商就是平均分后每人能拿到的数量
余数怎么处理
除完剩下的叫「余数」,代表还有东西没分完,得再补一遍
老师把糖平均分给小朋友对应 →把东西平均分到抽屉里

每个小朋友都尽量拿一样多,正好多出来的那几颗糖还要再补一遍

总数÷抽屉数=余数\text{总数} \div \text{抽屉数} = \text{商} \cdots \text{余数}
7第 7 页 · 平均分配

用平均分配求「至少几个」

用「平均分配」思路,把抽屉问题化成分除法。

1
数清物品抽屉
明确要分的东西有几个、分进几个抽屉
2
做平均分配
把物品尽可能均匀地摊到每个抽屉里
3
商是底线
每个抽屉至少拿到「商」这么多,再少就分不开
4
余数逼多一个
剩下的「余数」必须塞进去,至少一个抽屉再加1
8第 8 页 · 用平均分配求「至少几个」

推广形式:m个物品放进n个抽屉

上一页用「平均分配」求出「至少有⌈m/n⌉个」——这只是抽屉原理的一半。把m个物品放进n个抽屉,还有另一半:至少有一个抽屉里的物品数不超过⌊m/n⌋。

向上取整⌈⌉向下取整⌊⌋
7÷3=2.33,⌈⌉进上去取3,⌊⌋砍掉取2,不是四舍五入
形式一·上界
至少一个抽屉里有 ≥⌈m/n⌉ 个物品
形式二·下界
至少一个抽屉里有 ≤⌊m/n⌋ 个物品
教室里的椅子和人对应 →抽屉原理推广形式

人>椅必有人挤椅≥⌈人/椅⌉;椅>人必有空椅≤⌊人/椅⌋

m/nm/nm/n\lfloor m/n \rfloor \leq m/n \leq \lceil m/n \rceil
9第 9 页 · 推广形式:m个物品放进n个抽屉

用字母表示一般规律

上页我们说,m 个物品放进 n 个抽屉,至少有一个抽屉里有……几个?要把这个「几个」也用字母写出来,公式才算完整。这一页,我们把答案「字母化」。

「至少几个」怎么写
答案是 ⌈m/n⌉,符号 ⌈ ⌉ 念作「向上取整」
什么叫向上取整
除法除不尽时,结果往上凑成整数,如 ⌈2.3⌉=3、⌈5⌉=5
验证经典形式
经典问题里 m=n+1,代入得 ⌈(n+1)/n⌉=2,刚好对上「至少2个」
7颗糖分给3人对应 →m÷n 不够整就向上取整

7÷3=2.3,但糖必须整颗发,至少一人拿3颗;⌈m/n⌉ 就是这个意思

至少一个抽屉里的物品数m/n\text{至少一个抽屉里的物品数} \geq \lceil m/n \rceil
10第 10 页 · 用字母表示一般规律

简单版 vs 推广版对比

都是抽屉原理,但数字不同、结论不同。混着记就会算错。

简单版(n+1 和 n)
  • 物品 = n+1 个,抽屉 = n 个
  • 必有一个抽屉里 ≥ 2 个
  • 一眼出答案,不用算
推广版(m 和 n)
  • 物品 = m 个,抽屉 = n 个(任意正整数)
  • 必有一个抽屉里 ≥ ⌈m/n⌉ 个
  • m÷n,有余数就 +1(向上取整)
简单版只是推广版在 m = n+1 时的特例。做题只看一条公式:m÷n 向上取整,简单版自动成立,不用分两条背。
11第 11 页 · 简单版 vs 推广版对比

小试牛刀

点击作答

把 11 个苹果放进 5 个盘子里,无论怎么放,至少有一个盘子里有几个苹果?

12第 12 页 · 小试牛刀

本节要点回顾

  • 物品多于抽屉,必有抽屉装≥2个(核心思想)
  • 两种思维:极端构造 与 平均分配
  • 推广:m件分n抽屉,至少一抽屉装⌈m/n⌉件
  • 解题套路:m÷n看余数,有余则答案=商+1
延伸主题:抽屉原理的生活实例用鸽巢原理解释握手问题鸽巢原理在竞赛中的应用
13第 13 页 · 本节要点回顾

课后思考

先自己琢磨一会儿,再翻参考答案,看看有没有新的思路。

1把 5 个苹果放进 3 个抽屉,为什么总有一个抽屉至少有 2 个苹果?

参考答案用平均分配反证:5÷3=1余2,余下的2个无论怎么放,都会被塞进已有的抽屉,所以总有一个抽屉至少装2个。这就是抽屉原理的核心思路。

2你能再举一个生活中的「鸽巢」现象吗?说说物品和抽屉分别是什么。

参考答案比如一年365天,37个人里必有两人同生日——人是「物品」,日期是「抽屉」,因为物品数>抽屉数。13人里必有两人同属相也是同理。

3反过来——物品比抽屉少,比如3个苹果放进5个抽屉,「至少一个抽屉有2个」还成立吗?什么时候会不灵?

参考答案不一定。当物品数≤抽屉数时,可能每个物品独占一个抽屉,结论就不一定成立。所以抽屉原理的关键前提:物品比抽屉多。

14第 14 页 · 课后思考