当前课程知识点:组合数学 > 容斥原理和鸽巢原理 > 鸽子抢巢 > 鸽巢原理的应用(1)
大家刚才做了
刚才的quiz了吧
这个问题是说我有10双蓝袜子
12双白袜子
请问你最多抽多少次
随机的抽
最多多少回
就能凑成一对
那个时候就是在应用鸽巢原理
但是问题是哪个是鸽子
什么是巢
这里虽然说10双 12双
其实这个数字就是个虚数
真正在这个问题里面
我们会看到
实际上对应的颜色就是鸽巢
所以我们会看到
鸽巢原理虽然非常直观
真正想应用好
就一定要构造好鸽子
构造好鸽巢
下面我们来看这样一道经典的题目
已知我们有n加1个正整数
而它们的范围呢是小于
或者等于2n的
2n范围内随便取了正整数中
我们证明当中一定有
两个数是互质的
大家对这个问题有什么思路吗
其实这个问题也有典故的
当初在匈牙利的时候
有一位神童他叫波沙
有一位数学家听说了波沙非常牛
于是他亲自到波沙家拜访
他为了验证说波沙确实与众不同
他就给他出了这道题
当年波沙只有11岁
他仅仅思考了不到半分钟
就给了正确答案
要么这里我也给大家
留出半分钟的时间
让大家仔细地思考一下
不知道大家有没有答案呢
你是怎么设计的鸽子
怎么设计的巢呢
我们现在就来说一下波沙的解答吧
波沙是这样做的
他确实一共有n个盒子
每个盒子他放两个球
这个数字这么安排
1和2放在第一个盒子中
3和4放在第二个盒子中
5和6
相邻的数字我们把它都放进去了
然后这时候我们会发现
我们确实有了n个盒子
之后我们要从
这n个盒子里面往外取数
我们要取多少个呢
我们要取n加1个
因此总会有至少
两个数字来自于同一个盒子
而同一个盒子装的是
相邻的两个互质的数
因此不管怎么样
无论我怎么去选
这时候我这n加1个正整数中
必然能够抽到两个数字
它们是互质的
所以可以看到大波沙确实非常聪明
设计了精巧的鸽巢
设计了精巧的鸽子解决了这个问题
但我们再看另外一道题
那么同样还是从1到2n
我们也是从中间取n加1个数
还有什么样的结论呢
在这n加1个数中
至少有一对数
其中一个数是另外一个数的倍数
这该如何构造鸽子和鸽巢呢
实际上我们在想
要求倍数
我们是不是可以先提因子呢
任何一个数字我都可以
不停地提取2这个因子
最后剩下的数字肯定是
2的多少k次方乘以一个奇数
每个数字我都可以这样进行处理
之后呢
它们就会产生一个对应的奇数序列
假如说我每一个数字
去掉所有的2的因子
之后剩下的奇数序列
变成了R1 R2
一直到rn加1
这时候我们会发现这n加1个数字
要落在1到2n之间的奇数范围内
而1到2n中有多少个奇数呢
只有n个呀
但现在我有n加1个数
飞向n个奇数鸽巢
这时候我们就可以
利用鸽巢原理了
必然有2个数字在
这个r序列中是相等的
而比如说假设Ri等于Rj
等于小r的话
那就意味着原来这个数字Ai和Aj
Ai表示的是
2的某次方乘以小r
而Aj它可以是
2的kj次方乘以小r
因为它们数字如果不相等的话
意味着它们只是2的幂次不同
而可以直接整除
这样就构造出了鸽巢和鸽子
证明了Ai和Aj之间有倍数关系
下面我们来讲一个
看起来非常奇妙的一个题目
我们有这样一个序列
A1 A2一直到A100
每个数字呢
都是由1或者2组成的
那这样一个序列中我们知道
从某一个数字开始
它的顺序的相邻的
这10个数字和不超过16
也就是说从Ai开始
Ai加Ai加1
一直加到Ai加9
它们是小于等于16的
我有一个这样的结论
如果上面的条件都满足的话
则至少存在一个h和k
那么h和k作为下标
从Ah一直到Ak之间
它们这个序列之和的话
他们的数字和恰好等于39
他现在有点觉得非常奇怪
怎么就是这样一个序列
最后中间子串Ah Ah加1
一直加到Ak
最后它们的和恰好会等于39呢
我们来看这样一道题目
它最终实际上是要
得到一些序列的和的
那我们是不是可以去
构造一些序列和呢
假如我们就用Sj表示
从A1一直到累加到Aj
那j的取值当然就是从1到100了
那这时候这些序列S构成了一些串
对应的S1肯定是最小的
S1小于S2
一直小于S100
那S100它等于多少呢
S100是不是就相当于从
A1一直加A2
一直累加到A100
中间有100个数字
而有一个条件是说
任意的10个相邻数字之和
不超过16
那这里我对于S100
是不是可以前10个是一组
小于等于16
中间A11到A20是一组
依次往后
我一共可以把它分成10组
每一组都是小于等于16的
那意味着S100就应该小于
等于10乘以16
也就是S100是小于160的
而对应着39这个数字
和160有什么玄妙之处呢
我们会发现160加上
39恰好等于199
我们是不是看到
一点n减1这样的东西呢
那我们就去构造一下
比如说我可以对应于每一个S
我都累加上39
会得到什么
S1加39
S2加39
一直累加到S100加39
这时候对应的我们
一开始有S序列S1到100
接下来我们还有S1加39
S2加39
一直累加到S100加39
这两项一共有多少个序列呢
它们一共有200项
而它的最大值是多少呢
对应于我们算得出来
S100的界是160
那么最大值就
应该是S100加上39
应该等于199
这里我看到了一共有200项
而最大的数字是199
这意味着它们其中
会有两项是相等的
那谁和谁会相等呢
在S1到S100之间
我们刚才已经说了
是个递增关系
而S1加39
一直到S100加39
也是个递增关系
它们自己内部是不会相等的
要想相等无非就是在
S1到S100中有一项拿出来
刚好等于后面的SJ加上39
那必然我们就找到了
第一项Sk要等于后面的某一项
我们用Sh来表示
Sk等于Sh加上39
这里面我可以假设k大于h
那得到了什么
是不是Sk减去Sh就等于39呢
Sk减去Sh不恰巧
就是从Ah加Ah加1
一直累加到Ak
恰好等于39
这就证明了我们说到了中间的
一个子串之和恰巧等于39
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验