<font color="blue">射虎训练营——第二周:从韩信点兵谈起</font> - 辕门射虎


	青石 (临照轩)


	木禾侯谏议大夫 ★

组别	翰林学士
级别	征东将军
功绩	380
帖子	5724
编号	18288
注册	2004-9-25

发表于 2005-3-16 11:00 资料主页个人空间短消息看全部作者

射虎培训班——第二周

数学趣题简介第一课总第二课

从韩信点兵谈起

作者：青石

“话说当年，在楚汉相争的年代，韩信是刘邦的大将。有一天，刘邦亲临韩信的军营，而在兵场上约有二千名士兵在操练。韩信命令士兵们先后以七人一组、十一人一组及十三人一组结集成小组，并把每次余下不能组成七（或十一、十三）人小组的人数报上，然后他便可以快速地算出士兵的确切数目。例如，在组七人小组时余下3人，组十一人小组时余下4人，组十三人小组时余下8人，韩信很快便算出其确切数目是1984人；其后用一个跟着一个点的费时数法确认了人数正是1984，而且当中更包括一些由刘邦暗中吩咐混入士兵们中的数名近卫军，以防韩信事前已知道士兵数目的可能性。”（这个版本的故事由项武义先生讲。）
那么，韩信究竟是怎样快速算出士兵人数的呢？最早记载这类问题的书是《孙子算经》。但是这个孙子不是《孙子兵法》的孙子，而是公元3世纪到5世纪之间的一个数学家。这本书是中国古代《算经十书》中的一本，全书3卷，在卷上有今天仅存的中国筹算法则的记载。但是《孙子算经》中最有名的是卷下第26题。这个问题一般称之为“物不知数”问题，和鸡兔同笼、百鸡问题问题合称为中国古代数学三大名题。在《孙子算经》中“物不知数”是这样叙述的：
“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”
答曰：“二十三。”
那么《孙子算经》是怎样解决这个问题的呢？后面的解答是这样的：
术曰：“三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五。一百六以上，以一百五减之，即得。”
尽管有这样一段话，依旧不大明白究竟是怎么样算的，尤其是不明白70、21、15、105是怎么来的。不知道这四个数的来源就不会解决一般问题。为了弄清楚这个解法的实质，后来的人做了种种努力。

宋代周密在《志雅堂杂钞》中谈到“阴阳算术”时，将《孙子算经》中的方法称为“鬼谷算”并说这种方法又叫做“隔墙算”。周密为了使这种方法容易记住，做了一首诗：
三岁孩儿七十稀，五留廿一事犹奇；七度上元重相会，寒食清明便可知。
（解释一下：上元就是正月十五，隐含“15”；清明的前一天为寒食节，而每年从冬至到次年清明正好一百零五天，所以“寒食清明”隐含“105”。）
周密说：“案此法，取相乘之数也。如三则以五、七相乘数倍之，五则以三、七相乘之数，七则以三、五相乘之数，合之得百零五。”周密试图解释70、21、15、105的来源，但是并没有成功；因为他没有说明为什么对于三，是五、七相乘的二倍，而对于五、七则只是一倍。孙子的解法至此只能解决3、5、7这种情况，对于更一般的情况还是没有一般性解法。
杨辉也研究过这个问题，他在《续古摘奇算法》中称孙子的解法为剪管术（日本关孝和《括要算法》也称此法为剪管术，数学史家严敦杰先生曾这样解释：把所求数看成一根长长的管子，三寸三寸剪多二寸，五寸五寸剪多三寸……问这根管子长多少？）与秦王暗点兵。杨辉编了一些类似的题目，其中一道如下：
“拟一问：七数剩一，八数剩二，九数剩三，本题总数几何？
术曰：七余一，下二百八十八（题内余一，下二百八十八）；八余一，下四百四十一（题内余二，下八百八十二）；九余一，下二百八十（题内余三，下八百四十）。并之（二千一十），满五百四，去之（去三个五百四），余（四百九十八）合问。”
由此可见，杨辉已经明白孙子算法的实质，但是他依旧没有发现处理这类问题的一般方法。

70、21、15、105这四个数的来源直到1593年刊刻的《算法统宗》才被直接指出：“以三乘五得十五，为七数剩一之衰；又以三乘七得二十一，为五数剩一之衰，又以五乘七得三十五，倍作七十为三数剩一之衰。”其中“剩一之衰”就是“余1”的意思，程大位还在书中指出105是3、5、7连乘所得之数，并称之为“满钱数”。程大位在《算法统宗》中作了一首《孙子歌》来记述这种方法：
三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。
在这个后面的注中，程大位称这种方法为“韩信点兵”。

在我们前面的叙述中，有一个非常重要的数学家没有提到，他就是秦九韶。秦九韶是南宋数学家，1247年写成《数书九章》。这本书中最重要的成就就是“正负开方术”和“大衍总数术”，这两项伟大贡献使得宋元算书在中世纪数学史上占有突出地位。美国科学史家萨顿曾这样评价秦九韶：“秦九韶是他那个民族、他那个时代、并且确实也是所有时代最伟大的数学家之一。”
秦九韶的“大衍总数术”是孙子解法的推广（奇怪的是秦九韶在自己的书中从来没有提到过“物不知数”问题，因此前面也就没有提到他），用现代数学术语来说，他明确地系统地叙述了求解一次同余式方程组的一般方法。“大衍总数术”的核心是“大衍求一术”。而这种方法在西方经过欧拉、拉格朗日直到高斯才得以完成，比秦九韶晚了五百多年。1852年英国传教士伟烈亚力向欧洲介绍了《孙子算经》的“物不知数”题和
秦九韶的“大衍求一术”；1874年，德国人马蒂生指出，中国的这一解法与高斯《算术探究》中关于一次同余式组的解法完全一致；从此西方数学史家称一次同余式方程组的解法为“中国剩余定理”。我们中国的现代数学书称之为“孙子定理”或“中国剩余定理”。

下面用现代的数学语言解释“大衍总数术”。
为方便叙述，我们就以三个数为例：假设一个数N除以a余数是p，除以b余数是q，除以c余数是r。其中a、b、c两两互质。那么“大衍总数术”也就是中国剩余定理的解法就是：寻找三个数k、m、n满足kbc除以a余1， mac除以b余1， nab除以c余1；那么就可以得到合适所给条件的最小的N，N就是pkbc+qmac+rnab除以abc的余数。

这个解法中最困难的就是求k、m、n这些数，如果a、b、c比较小的话很容易猜出来（杨辉自己出的那个题的解法很可能就是这种情况），但是如果a、b、c很大的话就非常困难。杨辉虽然明白了孙子解法的本质但是他没有发明一种求k、m、n这些数的方法，所以发明不了一般性解法。求k、m、n这些数，也就是求一（因为k、m、n使得kbc除以a余1， mac除以b余1， nab除以c余1）。秦九韶发明了求一的一般方法，他称之为“大衍求一术”，这个就是“大衍总数术”最核心的东西。
给两个互质的数，比如X、Y，用“大衍求一术”就能寻找一个正整数K使得KY除以X的余数是1。“大衍求一术”和辗转相除法差不多。我们举个例子说明（因为打符号太麻烦啦）：以33和7为例，我们要寻找33的倍数使得它除以7的余数是1，可以按下面的方法做。33-7*4=5，7-5=2，5-2*2=1，所以1=5-2*2=5-（7-5）*2=（33-7*4）-（7-（33-7*4））*2=33*3-7*14所以33的3倍除以7余1。

最开始讲述的韩信点兵的故事中韩信就是首先算好kbc、mac和nab这三个数。题目中a=7，b=11，c=13，那么就是143k、91m、77n。
用“大衍求一术”很容易就求出k=5、m=4、n=12，这样就得到5*11*13p+4*7*13q+12*7*11r=715p+364q+924r，它除以7*11*13=1001的余数就是满足要求的最小的那个数。所以韩信只要知道三个余数和人数的大概范围就能立即算出真实士兵数。故事中p=3、q=4、r=8，所以715p+364q+924r=715*3+364*4+924*8=10993，10993除以1001的余数是983，人数是2000左右，所以真实人数就是983+1001=1984。

出几个题大家试试算一下：
1、十一数余三，十二数余二，十三数余一，问原总数几何？

2、二数余一，五数余二，七数余三，九数余四，问原总数几何？

3、今有物，不知其数，三三数之，剩二，五五数之，剩一，七七数之，剩二，问物几何？

4、有米铺诉被盗，去米一共三箩，皆适满，不计细数。今左壁箩剩一合，中间箩剩一升四合，右壁箩剩一合。后获贼，系甲、乙、丙三名，甲称当夜摸得马勺，在左壁箩满舀入布袋；乙称踢得木履，在中箩舀入袋；丙称摸得漆碗，在右壁箩舀入袋，将归食用，日久不知数。索到三器，马勺满容一升九合，木履容一升七合，漆碗容一升二合。欲知所失米数，计赃结断，三盗各几何？（注：一升=十合）

[广告] 《精忠报国岳飞传完整版》火热发布


	青石 (临照轩)


	木禾侯谏议大夫 ★

组别	翰林学士
级别	征东将军
功绩	380
帖子	5724
编号	18288
注册	2004-9-25

发表于 2005-3-16 22:35 资料主页个人空间短消息看全部作者

QUOTE:

原帖由邓仲华于2005-03-16, 21:19:28发表
我也占个坐 PS：黄蓉给瑛姑出的题好象也是这样的吧？

黄蓉给瑛姑出的第三题就是：
“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	青石 (临照轩)


	木禾侯谏议大夫 ★

组别	翰林学士
级别	征东将军
功绩	380
帖子	5724
编号	18288
注册	2004-9-25

发表于 2005-3-16 23:02 资料主页个人空间短消息看全部作者

QUOTE:

原帖由江东小庸才于2005-03-16, 22:45:02发表
青石节度使还请见谅啊，我没看上文直接算题目了，给的答案就比较多了，抱歉

呵呵

没关系

大家可以讨论讨论
比较各种方法的优劣等等

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	青石 (临照轩)


	木禾侯谏议大夫 ★

组别	翰林学士
级别	征东将军
功绩	380
帖子	5724
编号	18288
注册	2004-9-25

发表于 2005-3-21 17:55 资料主页个人空间短消息看全部作者

QUOTE:

原帖由金圭子于2005-03-17, 9:05:55发表

QUOTE:

原帖由青石于2005-03-16, 22:35:53发表
黄蓉给瑛姑出的第三题就是：
“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”

而且后来黄蓉说答案的时候也说了“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”这句。但瑛姑听到“三人同行七十稀”就以为黄蓉嘲笑她、南帝、周伯通三个七十古稀的老人“三人行”，反而又非常不爽………………（真的很巧哦，金庸真是写的滴水不漏…………）

其实金庸这个地方有个漏洞

就是三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

这口诀是在明朝才出现的

而宋人知道的则是：
三岁孩儿七十稀，五留廿一事犹奇；七度上元重相会，寒食清明便可知。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！