韓信點兵數學故事 _韓信

韓信是我國古代杰出的軍事家，是西漢的開國功臣，他的一生充滿了傳奇色彩，從一個眾人嫌棄的小混混到稱霸一方的大將軍，他完成了一次完美的蛻變。同時，他也留下了很多膾炙人口的故事，如"背水一戰"、"暗度陳倉"、"十面埋伏"等等。在這其中，"韓信點兵"這個故事包含一個著名的數學問題。

文章插圖
漢高祖劉邦曾問大將韓信："你看我能帶多少兵？"韓信斜了劉邦一眼說："你頂多能帶十萬兵吧！"漢高祖心中有三分不悅，心想：你竟敢小看我！"那你呢？"韓信傲氣十足地說："我呀，當然是多多益善啰！"劉邦心中又添了三分不高興，勉強說："將軍如此大才，我很佩服。現在，我有一個小小的問題向將軍請教，憑將軍的大才，答起來一定不費吹灰之力的。"韓信滿不在乎地說："可以可以。"劉邦狡黠地一笑，傳令叫來一小隊士兵隔墻站隊，劉邦發令："每三人站成一排。"隊站好后，小隊長進來報告："最后一排只有二人。""劉邦又傳令："每五人站成一排。"小隊長報告："最后一排只有三人。"劉邦再傳令："每七人站成一排。"小隊長報告："最后一排只有二人。"劉邦轉臉問韓信："敢問將軍，這隊士兵有多少人？"韓信脫口而出："二十三人。

文章插圖
"劉邦大驚，心中的不快已增至十分，心想："此人本事太大，我得想法找個岔子把他殺掉，免生后患。"一面則佯裝笑臉夸了幾句，并問："你是怎樣算的？"韓信說："臣幼得黃石公傳授《孫子算經》，這孫子乃鬼谷子的弟子，算經中載有此題之算法，
我們知道宋朝數學家秦九韶在《數書九章》中對這個問題做出了完整系統的解答。明朝數學家程大位在《算法統宗》中將解法編成易于上口的《孫子歌訣》，口訣是：
三人同行七十稀，五樹梅花開一枝，七子團圓正月半，除百零五便得知。"

文章插圖
劉邦出的這道題，可用現代語言這樣表述："一個正整數，被3除時余2 ，被5除時余3，被7除時余2，如果這數不超過100，求這個數。" 韓信是如何知道自己的隊伍有1073個士兵的呢？
牛氣的韓信熟知余數問題，所以快速統計出自己隊伍的人數然后迅速制定作戰策略，小伙伴們，你的數論知識現在能不能快速幫你解決些實際問題呢？我們不妨把這個問題數字化，即尋找一個符合條件的最小數，這個數除以3余2，除以5余3，除以7余2，列出除以3余2的數為：2, 5， 8，11，14，17 ， 20，23，26……再列出除以5余3 的數為：3 ， 8， 13，18，23， 28……
經觀察，這兩組數列中首先出現的公共數是8 ，而3與5的最小公倍數是15，兩個條件合并成一個，就是8＋15×整數，按照這一標準得出一串數為8 ， 23 ， 38……
接著再列出除以7余2的數，這些數為：2，9 ， 16， 23，30……就得出同時符合以上兩個條件的數：23 ， 58……滿足以上條件的最小自然數是23，而3與5和7的最小公倍數是105 。把所有標準融合在一起，就得出一個結論：被105除余23 ，韓信的兵也就是105×10＋23=1073人。

文章插圖
而另一版本的韓信點兵是這樣說得：據說秦朝末年的時候，戰火四起，楚漢相爭。在一次戰斗中，韓信率領著1500名將士同楚軍將領李鋒的軍隊交戰。
戰役非常慘烈，雙方全都拼死作戰，得知死了四五百人，在韓信的帶領下，漢軍大敗楚軍，楚軍倉惶地逃回了營地，韓信也整理了兵馬返回營地。然而當韓信率領剩下的士兵返回營地時，后軍來報說楚軍追來。這下漢軍可炸開了鍋，本來就已經身心疲憊的士兵都慌亂不已。
韓信騎馬來到坡頂，見追兵不足500人，便急速點兵迎敵。他命令士兵3人一排，結果多出2名；接著韓信又命令士兵5人一排，結果多出3名；他又命令士兵7人一排，結果又多出2名。于是韓信馬上說道："我軍有1073名兄弟，追兵不過區區500人，我們一定能打敗敵人。"聽了韓信的話，兵士們士氣大振，一鼓作氣打敗了追來的敵軍。

文章插圖
韓信如何快速得知自己士兵的人數呢？這個問題轉化成數學問題就是一個數除以3余2 ，除以5余3，除以7余2 ，求符合條件的數。下面提供2中解題思路：
1）篩法
1，3，5，7，9，11，13，15，17，19，21，23，25，… （用2除余1）
5 ， 11，17，23，… （用3除余2）
11， 23，… （用4除余3）
再從中挑"用5除余4"的數，… 一直篩選下去，舍得下功夫，就一定可得結果。并且看起來，解，還不是唯一的；可能有無窮多個解。
化繁為簡的思想：當問題中有很多類似的條件時，我們先只看其中兩三個條件，這就是化繁為簡。一個復雜的問題，如果在簡化時仍然保留了原來問題的特點和本質，那么簡化就"不失一般性" 。學會"簡化問題"與學會"推廣問題"一樣，是一種重要的數學能力。
尋找規律的思想：把我們的解題方法總結為篩法是重要的進步，是質的飛躍，找到規律了。
篩法是一般性方法，還可以用來解決其他類似的問題。
2）公倍數法
①化繁為簡，我們還是先看只有前兩個條件的簡化題目。
1 ， 3 ， 5，7，9，11，13 ， 15 ， 17，19，21，23 ， 25，… （用2除余1）
5，11，17 ， 23，… （用3除余2）
上述篩選過程的第一步，得到:1，3，5，7，9，11，13，15，17，19，21，23，25，…其實是列出了"用2除余1"的數組成的數列。這個數列實際上是用帶余除法的式子得到的。

文章插圖
所謂"帶余除法" ，是指整數的如下：對任意 b≠0,被除數a，除數b , 必唯一存在商 q和余數 r，使a=bq+r,0≤r＜b. 回到求"用2除余1的數"的問題。設這樣的數為 x ，則 x= 2n+1。這里x 是被除數，2是除數，n是商，1是余，且 0≤1＜2。當取 n=0,1,2,3,4,…… 時，用上式求得的x 正好組成上述數列1，3，5，7，9，11，13，15，17，19，21，23 ， 25，…
接著從中篩選出"用3除余2"的數，就是挑出符合下面"帶余除法"表達式x=3n+2
的數，這里n可取0，1，2，3，4，… 再繼續做下去. 對整個問題尋找規律，：今有物不知其數，二二數之剩1，三三數之剩2，四四數之剩3，五五數之剩4，六六數之剩5，七七數之剩6，八八數之剩7，九九數之剩8，問物幾何？
②尋找規律，設問題中，需要求的數是x，則x被2，3，4，5，6，7，8，9去除，所得的余數都是比除數少1，于是我們把被除數x再加1 ，則x+1就可被2，3 ， 4，5 ， 6，7，8，9均整除。也就是說，x+1是2,3,4,5,6,7,8,9的公倍數，從而是其最小公倍數[2,3,4,5,6,7,8,9]的倍數。X+1=2520k,k=1,2,3….
怎么解決韓信點兵問題呢？設士兵為x人，則x=3a+2,x=5b+3,x=7c+2,a、b、c為正整數，觀察可得x-2=21n,n為正整數，當n=1,2,3,…,x=23,44,65,…,23被5除余3 ，所以滿足條件的最小人數為23人，x=[3,5,7]k+23=105k+23,因為已經傷亡四五百人，所以1000＜105k+23＜1100,k=10,x=1073.
牛氣的韓信熟知余數問題，所以快速統計出自己隊伍的人數然后迅速制定作戰策略，小伙伴們，你的數論知識現在能不能快速幫你解決些實際問題呢？
1.　一個數在200與400之間，它被3除余2，被7除余3，被8除余5，求該數。
（解：112×2＋120×3＋105×5＋168k，取k＝-5得該數為269 。）
2. 一個數除以5余4，除以7余1，除以3余2，這個數不超過100 ，求這個數？
（解：（3*7）*4 + （3*5） + （5*7）= 134 。這個數小于100，134— 105= 29 。）
古代的算法在我國有許多名稱，如"韓信點兵"，"鬼谷算"，"隔墻算"，"剪管術"，"神奇妙算"等等，題目與解法都載于我國古代重要的數學著作《孫子算經》中。著作中首次提到了同余方程組問題，以及以上具體問題的解法，一般認為這是三國或晉時的著作，比劉邦生活的年代要晚近五百年，算法口訣詩則載于明朝程大位的《算法統宗》，詩中數字隱含的口訣前面已經解釋了。

文章插圖
《孫子算經》中是這樣給出這類問題的解法："三三數之剩二，則置一百四十；五五數之剩三，置六十三；七七數之剩二，置三十；并之得二百三十三，以二百一十減之，即得。凡三三數之剩一，則置七十；五五數之剩一，則置二十一；七七數之剩一，則置十五，一百六以上，以一百五減之，即得。
1247年南宋的數學家秦九韶把《孫子算經》中"物不知其數"一題的方法推廣到一般的情況，得到稱之為"大衍求一術"的方法，在《數書九章》中發表。這個結論在歐洲要到十八世紀才由數學家高斯和歐拉發現。所以世界公認這個定理是中國人最早發現的，被稱為"孫子定理"或"中國剩余定理" 。
對于我國古代數學名著《孫子算經》中有"物不知數":今有物不知其數，三三數之剩2，五五數之剩3，七七數之剩2 ，問物幾何？如何解析？
首先使用單因子構件湊成法，我們作兩個方面的簡化：一方面是每次只考慮"一個除式"有余數的情況（即另兩個除式都是整除的情況）；另一方面是把余數都簡化為最簡單的1 。這樣得到三組方程：
1 x=3a+1,x=5b,x=7c,
2 y=3a,y=5b+1,y=7c,
3 z=3a,z=5b,z=7c+1, (a、b、c為正整數)，
①式意味著，在5和7的公倍數中（35，70 ， 105 ， …）尋找被3除余1的數；②式意味著，在3和7的公倍數中（21，42 ， 63，…）尋找被5除余1的數；③式意味著，在3和5的公倍數中（15，30 ， 45，…）尋找被7除余1的數。對①式而言，這個數可以取70，對②式而言，這個數可以取21，對③式而言，這個數可以取15 。于是①式兩邊同減70變為這樣：第二式右邊仍是5的倍數，第三式右邊仍是7的倍數，而第一式右邊因為減的70是"用3除余1"的數，正好原來也多一個1，減沒了;第一式右邊也成為了倍數，是3的倍數。由①得x-70=3( a-23),x-70=5(b-14),x-70=7(c-10)；x-70= [3,5,7 ]k=105k,k為正整數，x=105k1+70;由②式兩邊同減21變得y-21=3 ( a-7 ),y-21=5 ( b-4 ),y-21=7 ( c-3), y=105k2+21; ③式兩邊同減15變得z=105k3+15;現在重復一下：所得的x是被3除余1，被5和7除余0的數；y是被5除余1，被3和7除余0的數；z是被7除余1，被3和5除余0的數。那么，湊出s=2x+3y+2z ， s不就是我們需要求的數嗎？
s=140+63+30+105 (2k1+3k2+2k3 )=233+105k;k=-2,-1,0,1,2,3….
這就是《孫子算經》中"物不知其數"一題的解，有無窮多解，最小的正整數解是23（k=-2 時）。
所以，上述方法叫"單因子構件湊成法"解決"由幾個平行條件表述的問題"的方法最大優點是可以任意改變余數加以推廣：題：有物不知其數，三三數之剩a ，五五數之剩b，七七數之剩c ，問物幾何？答：解為s=70a+21b+15c+105k,k為整數應該使s為正。
要注意的是，前面的問題中，3，5 ， 7是兩兩互素的，所以"三三數，五五數，七七數"得余數后可用此公式。但"四四數，六六數，九九數"得余數后就不能用此公式，因為4、6、9并不是兩兩互素的。
有趣的應用:某單位有100把鎖，分別編號為1 ， 2，3，…，100 。現在要對鑰匙編號，使外單位的人看不懂，而本單位的人一看見鎖的號碼就知道該用哪一把鑰匙。
能采用的方法很多，其中一種就是利用中國剩余定理，把鎖的號碼被3，5，7去除所得的三個余數來作鑰匙的號碼（首位余數是0時，也不能省略）。這樣每把鑰匙都有一個三位數編號。例如23號鎖的鑰匙編號是232號，52號鎖的鑰匙編號是123號。8號鎖——231 19號鎖——145 ， 45號鎖——003 ，52號鎖——123 因為只有100把鎖，不超過105，所以鎖的號與鑰匙的號是一一對應的。如果希望保密性再強一點兒，則可以把剛才所說的鑰匙編號加上一個固定的常數作為新的鑰匙編號系統。甚至可以每過一個月更換一次這個常數。這樣，仍不破壞鎖的號與鑰匙的號之間的一一對應，而外人則更難知道了。

文章插圖
余數問題是一個重要的數學問題，是計算機密碼學的基石之一。世界著名的數學家歐拉、高斯等人，都曾經研究過這個問題。歐拉重新發現了這個定理（歐拉定理），給出了證明并定義了歐拉函數。對正整數n，歐拉函數φ (n)是小于或等于n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為φ函數（由高斯所命名）或是歐拉總計函數（totient function，由西爾維斯特所命名）。例如φ(8)=4 ，因為1,3,5,7均和8互質。
在數論中，歐拉函數是最重要也是最基礎的一個函數，這個函數的很多性質及其證明雖然基礎，但也"燒腦" ，家里沒有要搞奧數的牛娃，就不要折磨腦細胞，咱們背背詩輕松解決好了。
除了用于點兵，歐拉定理更是非對稱加密（RSA）算法的核心。歐拉關于數論的大部分工作也是在柏林完成的，他的數論著作在他的《全集》中占了整整四大卷，占全部著作的40%，僅這四卷數論著作就足以使歐拉位列歷史上最偉大的數學家之一。

文章插圖
普魯士的腓特列大帝曾想組成這樣一支儀仗隊，儀仗隊共有36名軍官，來自6支部隊，每支部隊中，上校、中校、少校、上尉、中尉、少尉各一名。他希望這36名軍官排成6×6的方陣，方陣的每一行，每一列的6名軍官來自不同的部隊并且軍銜各不相同。
令他惱火的是，這些軍官怎么絞盡腦汁也排不成。都說三個臭皮匠，賽過諸葛亮，但是在數學問題上，幾千幾萬個臭皮匠都不頂用。沒法，腓特列大帝只能向數學大牛牛歐拉求救。
歐拉先從最簡單問題入手，當n=3 (即有3種部隊、3種級別)的方陣，他很輕松排出來，然后是n=4，n=5. 都很輕松就解出，得出的方陣叫歐拉方陣（又叫做正交拉丁方陣）。但是當n=6 時，歐拉發現這是一個不可能完成的任務。

文章插圖
1782年，歐拉總結道:"我已經試驗研究了很多次，我確信不可能作出兩個六階的，并且對于10、14，…以及奇數2倍的階數都是不可能的。"歐拉認為:4n + 2階歐拉方陣不存在，這被后人稱為"歐拉方陣猜想" 。
在沒有計算機的年代，歐拉方陣猜想的證明非常困難。一直到了1910年，一對兄弟倆，法國數學家加斯頓?塔里和赫伯特?塔里用了最笨的方法，（不知道他們哪里來的耐心），窮舉出了全部六階拉丁方，從而證實了n=6時歐拉猜想是正確的：n=6 時，儀仗隊是一個不可能完成的任務。看到沒？最笨的方法也可以在數學史上留名啊，真是世上無難事，只怕有心人。（現在用計算機已經知道，除了n=2,6以外，其余的正交拉丁方陣都存在，而且有多種構造的方法。這個否定的結果是人們在180年的努力中未曾想到的。）

文章插圖
歐拉恒等式，歐拉常數，歐拉示性數等
歐拉方陣體現著數學的美：整齊、對稱、有規律、簡單、自然… ，歐拉方陣在工農業生產，統計、組合設計、模擬、數值積分中均具有廣泛的應用；另一方面，歐拉方陣在數學的發展中也有著重要的作用.但是，最要緊好玩。歐拉沒料到，后人居然把歐拉方陣能玩出花來，成為一種從9-99歲的人都無法抗拒的經典數字游戲。歐拉方陣從瑞士起源，接著在日本推廣，后來在英國發揚光大，最終風靡全世界，有了另一個簡單好聽的名字，數獨。其實歐拉方陣就是沒有宮的標準數獨，而數獨其實正是一種特殊的歐拉方陣。
2012 年，三位愛爾蘭數學家證明了數獨至少需要 17 個初始數字才有唯一解。他們的計算機花了 700 萬小時的 CPU 時間才搞定了這道數獨題。
【韓信點兵數學故事】可以說中國古代的先賢在這方面取得了豐碩的成果。"韓信點兵"問題只是一個例子，這樣的問題有更加普遍和系統化的表示方法。而這個方法是我國為數不多的獲得世界公認的古代數學成就之一。