当前课程知识点:组合数学 > 容斥原理和鸽巢原理 > 看得见摸得着的鸽巢 > 韩信点兵
我给大家来讲一个历史上典故
大家都知道韩信吧
韩信实际上有一个典故非常有名
也就是韩信点兵
他的故事是这样的
当初楚汉相争
有一次韩信带着兵
正走在一个狭窄的道路上
这时候楚军追来
情况非常危机
当时韩信并不知道自己有多少将士
而且地方非常狭窄
追兵在后
没有时间来整理队伍
看一共有多少人了
这时候韩信出了一个
非常奇妙的方法
他说将士们你们不要慌张
你们3人一排
看余多少人
然后再5人一排余多少人
然后7人一排余多少人
最后3人一排余2人
5人一排余3人
而7人一排最后余2人
当时他的副官就报告
说韩将军我们的人数一共是1052人
韩信当时摇头说不对
你数错了
我们的军事一共是1073名
敌人一看不足500
而我们超过了1000人
而且我们居高临下
一定能够打败敌人
这时候将士们士气大涨
于是直接击破了楚军
这个故事大家觉得很奇怪
怎么就排了一下队伍
算了一下余多少人
韩信就能够知道
他一共有多少个将士吗
其实同样的问题我们在孙子算经中
也有类似的一道题目
孙子算经中有这样一段话
他说 今有物不知其数
三三数之余二
五五数之余三
而七七数之余二
问物几何
翻译起来什么意思啊
他说我有这么一个数字
它除以3以后余2
除以5余数是3
除以7余数是2
请问这个数字是多少
这实际上就是在求初等数论中的
同余式
我们把它可能用方程写x等于
3a加2
x等于5b加3
x等于7c加2
韩信就是非常迅速地
可以计算出来x等于多少
就马上得出他一共有多少士兵
而孙子算经也是怎么去
求解这样一个同余式呢
我们可以从简单的问题开始
就看孙子算经的问题
我们先用枚举的方法来做
比如说他不是要求除以3余2吗
我把所有的除以3余2的数
列在这里
同时我也可以列出
所有除以5余3的列在这里
最后我可以把除以7余2的数字
全部列在这里
最后我们发现
确实它们中间存在一些共同的数字
而最小的共同数字恰好是23
但是我想韩信肯定不能靠这种方法
来得到答案吧
我们是不是有
另外一个更巧妙的方法呢
比如说我们可不可以用构造的方法
来找到这样一个数字呢
我们会发现其实在这里面
我们有一些是可以考虑5的倍数
7的倍数
再加上某一些余数
那这里比如说我可以设5和7的
公倍数是S
那么5和7的公倍数要除3余1
能有多少个数字呢
5和7的公倍数除3余1的数字
恰好是70
那么意味着这样一个数字
我如果乘以2的话
它就必然能被5和7整除
但是除以3余2
它就满足了第一个式子
而对应于对应于第二个5b加3
和7c加2
它对余数没有贡献
那我们就可以依次按照这样的思想
比如说用t来表示是3和7的公倍数
但是它除以5余1
这个数字恰巧如果t乘以3等于63
它的标志着它是3和7的倍数
但是它如果它除以5余3
它就恰好满足第二个式子
接着我还可以算
h是3和5的倍数
但是它却除7余1
这时候h乘以2算出来是30
这个数字恰好是3和5的倍数
但是它去除7满足第三个式子
也就是7c加2
那这时候我想构造一个对于除3余2
除5余3
除7余2的式子
我直接可以用2s加上3t加上2h
它恰好等于233
由于我们的设计能够保证
对应于除以3的时候
它的余数是出现在第一个部分
除以5的时候
它的余数出现在3t部分
而除以7的时候
它的余数出现在2h部分
它必然就会满足右边的这个同余式
而当然233是满足的一个数字
如果我们想要求最小的一个呢
因为3 5 7的公倍数恰好是105
那么我可以用233不停地减105
最后我得到了一个比较小的数字
也就是和刚才枚举出来的
结果是一样的
233减去105
再减去105
恰巧等于23
这时候我再回答孙子算经的问题
今有物不知其数
三三数之余二
五五数之余三
七七数之剩二
问物几何
答曰23
这时候回头再看韩信怎么做呢
韩信实际上确实记住了这些公倍数
然后利用简单的乘法
它就可以直接找到
相应的规模的答案
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验