|
韩
信 点 兵
韩信点兵是一个有趣的游戏，如果你随便拿一把棋子（数目在100粒左右），先3粒3粒数，不满3粒的记下余数；再5粒5粒数，不满5粒的记下余数；最后7粒7粒地数，也把余数记下来。然后根据每次的余数，就可以知道你原来拿的棋子总共有多少。
如：3个一数余1粒，5个一数余2粒，7个一数余2粒，那么原有棋子是多少呢？
它的算法很简单，而且在我国古代就有。宋朝周密叫它“鬼谷算”或“隔墙算”；杨辉叫它“剪管术”；而“韩信点兵”是较通行的名称。至于它的算法，在《孙子算经》上早有说明，后来在宋朝经过数学家秦九韶的推广，又发现了一种算法，叫“大衍一术”。这就是外国人所称的“中国剩余定理”，是数学史上极有名的问题。
那么到底怎样来计算呢？
A×70＋b×21＋c×15－105
其中a、b、c分别为3个、5个、7个一数的余数。如果得出数还是比105大，就再减去105，一直到得数比105小为止。
因此你可以很容易地知道，前面问题的答案了
1×70＋2×21＋2×15－105＝37（粒）。
那么“韩信点兵”里为什么要3个一数，5个一数，7个一数呢？周其它的数可以吗？我们先研究一下“韩信点兵”的解法
“70a＋21b＋15c－105”。
我们先来看一下70、21、15、105这4个数和3、5、7之间的关系：
（1）70＝2×5×7，70＝3×23＋1，所以70是5和7的一个公倍数，它被
3除后余数是1.
（2）同理，21是3与7的一个公倍数，它被5除后余数是1.
（3）15是3与5的一个公倍数，它被7除后余数是1.
（4）105＝3×5×7，是3、5、7的最小公倍数。
根据上面的这些关系，“70a＋21b＋15c－105”确实是所求的得数。
所以，70a＋21b＋15c－105被3除的余数是1。据同样的道理，这个数被5除后的余数是2，被7除后余数是2.
那么，“韩信点兵”里为什么要用3、5、7这三个数呢？
我们知道，3、5、7中任意两个数的最大公约数都是1，也就是说是两两互素。
于是就可以找到这样一个数，是3、5、7其中两个数的公倍数，而被另一个数除后余数是1，类似70、21、15。这也就是“韩信点兵”中的三个数的要求。
那么不是两两互素的数，是不是就一定找不到类似70、21、15的数呢？
如4、6、7这三个数，4与6不是互素，它们的最大公约数是2，而6与7的任何一个公倍数都是偶数，被偶数4除后的余数也一定是偶数，而不可能是1，所以是找到与70、21、15相当的三个数的。因此在“韩信点兵”里就不能用。
我们也可以不用3、5、7这三个数，而换成其它两两互素的数，如2、3、11.这时的计算式是“33a＋22b＋12c－66”。不信的话，你可以用上文中的例子试一试，看是不是37粒。
中国剩余定理（Chinese Remainder
Theorem）在近代抽象代数学中占有一席非常重要的地位。 我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按1～3报数，第二次按1～5报数，第三次按1～7报数，每次报数后都要求最后一个人报告他报的数是几，这样韩信就知道一共到了多少人。他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。到了明代，数学家程大位把这个问题的算法编成了四句歌诀：
三人同行七十稀，
五树梅花廿一枝，
七子团圆正半月，
除百零五便得知。
这就是韩信点兵的计算方法，它的意思是：凡是用3个一数剩下的余数，将它用70去乘（因为70是5与7的倍数，而又是以3去除余1的数）；5个一数剩下的余数，将它用21去乘（因为21是3与7的倍数，又是以5去除余1的数）；7个一数剩下的余数，将它用15去乘（因为15是3与5的倍数，又是以7去除余 1的数），将这些数加起来，若超过105，就减掉105，如果剩下来的数目还是比105大，就再减去105，直到得数比105小为止。这样，所得的数就是原来的数了。
|
