数学广角——鸽巢问题
5只鸽子进4个笼子,搞懂"至少挤一窝"背后必然发生的数学规律
按 空格/→ 演示下一步
全部页面点击任意一页,跳回舞台从这页播放
数学广角——鸽巢问题
5只鸽子进4个笼子,搞懂"至少挤一窝"背后必然发生的数学规律
把东西放进抽屉
家里4本书要放进3层书柜。随手一放,每层真的都能只放1本吗?
鸽子比巢多,必有巢挤进不止一只
经典的「鸽巢问题」
上一页我们把东西塞进抽屉,今天换成鸽子飞回鸽巢——10 只鸽子,9 个鸽巢,不管怎么飞,会发生什么?
椅子少一把,必定有小朋友要和别人挤同一把
什么是抽屉原理
刚才我们看到 5 只鸽子飞进 4 个窝,至少有一窝住 2 只。把这个发现抽出来,就得到一条通用规律——抽屉原理。
椅子不够每人一把,必有人共用 → 抽屉同理
抽屉原理的图解
从左往右读:5只鸽子住进3个抽屉,无论怎么分,必有一个抽屉住进2只或更多。
极端思维
上页我们用图看到了「重复」是怎么发生的。但光看图还不够——有没有一种方法,不用挨个摆,就能直接断定「一定会重复」?有!它叫极端思维。
假设每个插座只充一台设备,最多同时充几台;多一台,必然两台挤同一插座
平均分配
上节课我们用极端思维想的是——先把多的装满一个抽屉。其实真正做题的第一步,是先「平均分」:把东西尽量均匀地塞进每个抽屉,看看每人最少拿到多少、还剩几个没分完。
每个小朋友都尽量拿一样多,正好多出来的那几颗糖还要再补一遍
用平均分配求「至少几个」
用「平均分配」思路,把抽屉问题化成分除法。
推广形式:m个物品放进n个抽屉
上一页用「平均分配」求出「至少有⌈m/n⌉个」——这只是抽屉原理的一半。把m个物品放进n个抽屉,还有另一半:至少有一个抽屉里的物品数不超过⌊m/n⌋。
人>椅必有人挤椅≥⌈人/椅⌉;椅>人必有空椅≤⌊人/椅⌋
用字母表示一般规律
上页我们说,m 个物品放进 n 个抽屉,至少有一个抽屉里有……几个?要把这个「几个」也用字母写出来,公式才算完整。这一页,我们把答案「字母化」。
7÷3=2.3,但糖必须整颗发,至少一人拿3颗;⌈m/n⌉ 就是这个意思
简单版 vs 推广版对比
都是抽屉原理,但数字不同、结论不同。混着记就会算错。
- 物品 = n+1 个,抽屉 = n 个
- 必有一个抽屉里 ≥ 2 个
- 一眼出答案,不用算
- 物品 = m 个,抽屉 = n 个(任意正整数)
- 必有一个抽屉里 ≥ ⌈m/n⌉ 个
- m÷n,有余数就 +1(向上取整)
小试牛刀
把 11 个苹果放进 5 个盘子里,无论怎么放,至少有一个盘子里有几个苹果?
本节要点回顾
- ✓物品多于抽屉,必有抽屉装≥2个(核心思想)
- ✓两种思维:极端构造 与 平均分配
- ✓推广:m件分n抽屉,至少一抽屉装⌈m/n⌉件
- ✓解题套路:m÷n看余数,有余则答案=商+1
课后思考
先自己琢磨一会儿,再翻参考答案,看看有没有新的思路。
参考答案用平均分配反证:5÷3=1余2,余下的2个无论怎么放,都会被塞进已有的抽屉,所以总有一个抽屉至少装2个。这就是抽屉原理的核心思路。
参考答案比如一年365天,37个人里必有两人同生日——人是「物品」,日期是「抽屉」,因为物品数>抽屉数。13人里必有两人同属相也是同理。
参考答案不一定。当物品数≤抽屉数时,可能每个物品独占一个抽屉,结论就不一定成立。所以抽屉原理的关键前提:物品比抽屉多。