韩信点兵问题的初等解法.doc

“韩信点兵”问题的初等解法研究王晓东 河北省卢龙县燕河营镇中学 066407韩信，是我国汉代刘邦手下的一员能征善战，智勇双全的大将。历史上流传着一个关于他运用奇特方法点兵的传说。有一天，韩信来到操练场，检阅士兵操练。他问部将，今天有多少士兵操练，部将回答：“大约两千三百人。”韩信走上点兵台，他先命全体士兵排成7路纵队，问最后一排剩几人，部将说，剩2人；他又命全体士兵排成5路纵队，问最后一排剩几人，部将说，剩3人；最后，他又让全体士兵排成3路纵队，问最后一排剩几人，部将说，剩2人。韩信告诉部将，今天参加操练的士兵有2333人。 从现代数学的观点来看，解决韩信点兵问题，可以这样思考：设操练士兵的总数为M，则M=3x+2=5y+3=7z+2其中，x，y，z分别表示排成3路纵队，5路纵队，7路纵队的纵队数目。求出了x，y，z以后，M也求求出来了。而求x，y，z可以看成求方程组3x+2=5y+3 3x+2=7z+2的正整数解。在上面的方程组中，未知数的个数多于方程的个数，则把这种方程（组）叫做不定方程（组）。不定方程（组）的解是不确定的，一般不定方程总有无穷多个组解，但若加上整数（或正整数）解的特定限制，则不定方程（组）的解有三种可能：有无限组解，有限组解，或无解。我国古代人民对于不定方程（组）这类问题解法的探讨有着悠久的历史，在中国古代的孙子算经中曾作为一个典型问题进行论述。其中的一个经典例题是：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物有几何？答曰：二十三。术曰：三三数之剩二，则置一百四十；五五数之剩三，则置六十三；七七数之剩二，则置三十；并之得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五。一百（零）六以上，以一百（零）五减之，即得。在中国民间还广为流传着一个口诀：三人同行七十稀，五树梅花二十一。七子团圆正半月，除百零五便得知。就是对这个问题解法的情境化的解释与说明。歌谣中隐含着70、21、15、105这4个数字，只要记住了这4个数，物不知其数问题就可以迎刃而解了。尤其可贵的是这种解法具有普遍意义。这个口诀意思是：凡是每3个一数最后剩1个，就取70；凡是每5个一数最后剩1个，就取21；凡是每7个一数最后剩1个，就取15。在物不知其数问题中，每3个一数最后剩2个，应该取2个70；每5个一数最后剩3个，应该取3个21；每7个一数最后剩2个，应该取2个15，相加所得到的和，如果大于105，再减去105，仍大于105就再减去105，所得到数字就是问题的所有答案中最小的结果。这种解法对许多人来说都会感到迷惑不解，不能理解这种解法的来龙去脉，记住了结论，题目出现变形或者进行扩展，就会束手无策。下面我们探索用引入新的未知数换元的思想解决这种问题。设物体的总数为M，则M=3x+2=5y+3=7z+2其中，x，y，z分别表示M除以3，除以5，除以7的商。求出了x，y，z以后，M也求出来了。而求x，y，z可以看成求方程组3x+2=5y+3 3x+2=7z+2 的正整数解。化简方程组得 3x-5y=1 3x-7z=0 由的，7z-5y=1 y=即y= 根据等式，因为y，z都是正整数， 所以一定也是一个整数，所以设z=5t+3(t是非负整数)。（注意：这里引入未知量的关键是设z=et+f的形式，z应该是分母5的倍数并加一个常数项f,常数项确定的原则是：常数项f与z的系数相乘加上分子中的常数项-1的和是分母5的倍数，即2f-1是分母5的倍数。例如，所以应设x=4t+3）所以把z=5t+3(t是非负整数)代入得，=7t+4 把y=7t+4(t是非负整数)代入得， 把 (t是非负整数)代入得， 所以不定方程的通解为： 观察通解公式，t的系数出现分数，为保证x，y，z都是整数，再次引入变量m,使t=3m(m是非负整数)，则通解公式变形为, 物体的总数 M=3x+2=3(35m+7)+2=105m+21+2=105m+23当引入的变量m分别取不同的值m012345M23128233338443548现在我们用这种方法来解决本文开头提出的“韩信点兵”问题，细心的读者会发现，“韩信点兵”问题与孙子算经中“物不知其数”是同一个问题，实际上，韩信运用了“物不知其数”的原理计算出操练士兵的人数。通过上题的计算已知M=105m+23，又知道操练的士兵有2300多人，所以当m=22时，M=2333，即参加操练的士兵有2333人。下面我们用这种方法来解决类似的两个问题。例1 现有1角，5角，1元硬币各10枚，从中取出15枚，共7元。1角，5角，1元硬币各取了多少枚？设取出1角硬币x枚，5角硬币y枚，1元硬币z枚。本题的实质是求下面这个不定方程的正整数解x+y+z=15 0.1x+0.5y+z=7 且0x15，0y15，0z15。10得 x+5y+10z=70 得 4y+9z=55 由得，使（t是非负整数） 把代入得， 把、代入得， 则不定方程的通解为： 有因为0x15，0y15，0z15，当t=0， 所以x=5， y=7， z=3。即需要取出1角硬币5枚，5角硬币7枚，1元硬币3枚，由于条件的限制，这个不定方程只有一组符合条件的解。例2 一个盒子里装有不多于200粒棋子，如果每次2粒，3粒，4粒或6粒地取出，最终盒内都剩一粒棋子；如果每次11粒地取出，那么正好取完，盒子里共有多少粒棋子？ 设盒子里棋子总数为M，则M=2a+1=3b+1=4c+1=6d+1=11e 其中，a，b，c、d、e分别表示每次取出2粒，3粒，4粒、6粒或11粒的次数。根据等式可得 ，观察这四个等式，5个未知量的关系简单，很难用加、减消元法消去其中的三个未知数。观察这四个等式的特点，e应该是2、3、4、6的最小公倍数12的倍数加一个常数k，即e=12t+k，并且要求11k-1是2、3、4、6的倍数，经过试算k=11，所以令e=12t+11，分别代入上面四个等式得， a=66t+60 b=44t+40c=33t+30d=22t+20e=12t+11将通解代入，等式恒成立。则M=2a