韩信点兵:有兵一队,若列成五行纵队,则末行一人,成六行纵队,则末行五人,成

这个问题是韩信点兵

民间传说着一则故事——“韩信点兵”.
秦朝末年,楚汉相争.一次,韩信将1500名将士与楚王大将李锋交战.苦战一场,楚军不敌,败退回营,汉军也死伤四五百人,于是韩信整顿兵马也返回大本营.当行至一山坡,忽有后军来报,说有楚军骑兵追来.只见远方尘土飞扬,杀声震天.汉军本来已十分疲惫,这时队伍大哗.韩信兵马到坡顶,见来敌不足五百骑,便急速点兵迎敌.他命令士兵3人一排,结果多出2名；接着命令士兵5人一排,结果多出3名；他又命令士兵7人一排,结果又多出2名.韩信马上向将士们宣布：我军有1073名勇士,敌人不足五百,我们居高临下,以众击寡,一定能打败敌人.汉军本来就信服自己的统帅,这一来更相信韩信是“神仙下凡”、“神机妙算”.于是士气大振.一时间旌旗摇动,鼓声喧天,汉军步步进逼,楚军乱作一团.交战不久,楚军大败而逃.
韩信是如何凭借交换队列的方式及三个余数,快速算出了士兵的总数的呢?
其实,韩信根本不是什么“神仙下凡”,也不是有什么“神机妙算”的法术.他算得快,算得准,是因为他掌握了这一类问题的求解方法与技巧.
这类问题就是著名的“孙子算经”和“中国剩余定理”所解决的问题.
我国古代数学名著《孙子算经》中,提出了闻名于世的“物不知数”问题.原文是：
“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二.问物几何?”
书中还给出了其解法.韩信就是根据这个问题的解法推算出将士的准确数字的.
下面我们来研究这个问题的解法.
(Ⅰ)“笨”算法
原来的问题题意是：求一数,三除余二,五除余三,七除余二.这问题太容易回答了：因为以3除余2,以7除余2的数,以21除也余2,而23是以3,7除余2的最小数,它刚好又是以5除余3的数.所以心算快的人很快就能算出.
我们再来解决另一个问题吧!
“三除余二,五除余三,七除余四,求原数”.
下面先介绍解决这一问题的“笨”算法：
在算盘上先打上(或纸上写上)2,每次加3,加到以5除余 3的时候暂停下来,再在这个数上每次加15,到得出以7除余4的数的时候,就是答数.具体地说：从2加3,再加3得,即
2,2＋3=5, 5＋3=8．
它是以5除余3的最小数,然后在8上加15,再加15,第三次加15,得53,即
8,8＋15=23,23＋15=38,38＋15=53．
经过验算,53用3除余2,5除余3,7除余4,所以53就是符合要求的最小数.
这个方法的道理是什么呢?很简单：先从以3除余2的数中去找以5除余3的数,再从“3除余2,5除余3”的数中去找7除余4的数,如此而已.这方法虽然拙笨些,但这是一个步步能行的方法,是一个值得推荐的、朴素的方法.
上述问题的解答,不但53有此性质,而53＋105=158,158＋105=263都有此性质,因此,问题的确切提法应当是：求出三除余二,五除余三,七除余四的最小的正整数.
我们再介绍一个麻烦得多的问题.原文如下：
“今有数不知总.以五累减之无剩,以七百十五累减之剩十,以二百四十七累减之剩一百四十,以三百九十一累减之剩二百四十五,以一百八十七累减之剩一百零九.问总数若干.”
看来问题比较麻烦,但通过细心观察,有窍门可找.你看：第一句“以五累减之无剩”其实是多余的,因为这个数以715除余10必定是5的倍数.第三句话“以247累减之剩140”,就是说此数减去247的若干倍后还余140,140是5的倍数,此数也是5的倍数,那么减去的247的倍数也应是5的倍数.因此这句话可改为“以247×5=1235累减之剩140”.同样第四句话也可改为“以391×5=1955累减之剩245”.
现在我们可以完全仿照前面的方法进行计算,从245逐次加1955,直至得到的数用1235除余数为140止.计算过程如下：
逐次加1955 245,2200,4155,6110,8065,10020．用1235去除的余数965,450,1170,655,140．
最后得到10020满足这两项要求.经检验10020的确符合全部条件,它就是我们要求的数.
下面再看一个古算题.
“二数余一,五数余二,七数余三,九数余四,问本数.”
首句与末句条件合起来是“18除余13”,再由
13,13＋18=31,31＋18=49,49＋18=67,
67是五除余2的数,再由
67,67＋5×18=67＋90=157．
经检验,157符合全部条件：以2除余1,以5除余2,以7除余3,以9除余4,所以157就是解答了.
(Ⅱ)古代的口诀解法
程大位著的《算法统宗》,对“物不知其数”的问题(见P．44第6行)的解答方法用下面的口诀标出：
“三人同行七十稀,五树梅花廿一枝,
七子团圆正半月,除百零五便得知.”
它的意义是：
以70乘用3除的余数2,21乘用5除的余数3,15乘用7除的余数2,然后总加起来.如果它大于105,则减105,若仍大再减,……最后得出来的正整数就是答数了.
它的形式是：
2×70＋3×21＋2×15=233,
两次减去105,得23,这就是答数了.
为什么70,21,15有此妙用?这70,21,15是怎样求出来的?
先看70,21,15的性质：70是这样一个数：用3除余1,5与7都除得尽的数,所以70a是一个用3除余a而5与7除都除得尽的数.21是用5除余1,3与7除得尽的数,所以21b是用5除余b,而3与7除得尽的数.同理,15c是用7除余c而3与5除得尽的数.总起来：
70a＋21b＋15c
是一个3除余a,5除余b,7除余c的数,也就是可能的解答之一,但可能不是最小的.这数加减105后都仍然有同样的性质,所以可以多次减去105而得出解答来.
在程大位的口诀里,前三句的意义是点出3,5,7与70,15,21的关系,后一句说明为了寻求最小正整数解还须减105,或再减105等.
这个方法是很好的.但是如何找出这70,21,15三个数呢?可用凑的方法：
在算盘上先打上35,它不是用3除余1,再加上35,得70,它是用3除余1了.其它可仿此求出.
现在我们可以来揭示“韩信点兵”的秘密了：
我们容易看出：韩信在点兵布阵时,士兵3人一排多出2人,就是士兵的总数被3除余2；5人一排多出3名,就是士兵数被5除余3；7人一排多出2名,就是士兵数被7除余2．
3,5,7的最小公倍数是105,所以105,105×2,105×3,…,105×10等等,都能被 3,5,7整除.而韩信根据“物不知其数问题”知道满足条件“被3除余2,被5除余3,被7除余2”的最小正整数23,并且他还知道自己的兵力略多于1000人,于是就迅速地算出了确切的士兵数：
105×10＋23=1073(人)．
现在再将口诀解法推广一下.先回顾口诀：
“三人同行七十稀,五树梅花廿一枝,七子团圆正半月,除百零五便得知”.用现代术语翻译,其口诀实际上是：
N=70r1＋21r2＋15r3-105p,
其中ri(i=1,2,3)分别是余数,p是使N＞0的任一整数.
以上方法可以概括成更普遍的式子：
若某数N分别被称为定母的d1,d2,d3,…,dn除得的余数为r1,r2,r3,…,rn,则
N=k1r1＋k2r2＋k3r3＋…＋knrn-pq,
其中k1是d2,d3,d4,…,dn的公倍数,且被d1除余1；k2是d1,d3,d4,…,dn的公倍数,且被d2 除余1；…kn是d1,d2,d3,…,dn-1的公倍数,且被dn除余1．p是任意整数,q是d1,d2,d3,…,dn的最小公倍数.
上式实际上是一条定理,而其关键又在于“求一”,即求“一个数的多少倍除以另一数,所得余数为1”的方法,也即求出公式中的“ki”．
这个方法的研究,是由我国宋代著名数学家秦九韶(约1202～1261)在其名著《数书九章》一书中完满解决的.他把它称作“大衍求一术”.类似的理论成果,在欧洲直到18,19世纪才由著名数学家欧拉和高斯获得,最早出现在高斯1801年出版的《算术研究》一书里.而这,已是秦九韶之后500多年的事了.因而,上述成果被称为“中国剩余定理”,或“孙子定理”.
现在,让我们也来当一回韩信吧!假如让士兵1至5报数,1至7报数,1至9报数,值日军官告诉我们余数分别是3,2,2．算一算士兵有多少.
显然,问题的提法与“韩信点兵”的传说中变换队列的方法是一致的.它的定母为d1=5,d2=7,d3=9,余数为r1=3,r2=2,r3=2．因为k1是7与9的公倍数且以5除余1的数,经计算知k1=126,类似地知,k2=225,k3=280,q=315．取p=4,则
N=k1r1＋k2r2＋k3r3-pq
=126×3＋225×2＋280×2-4×315=128．
N＝128,只不过是个符合条件的最小的数.假若要学“韩信将兵,多多益善”的话,我们可以在“128×n”(n为自然数)中任意取值.
此题这样列式：1386*1+385*5+330*4+210*10-2310*p

2111人。