Math Pro 數學補給站's Archiver

順境的人生人人會走,只是速度快慢而已;
人一定要學著走逆境,而且愈年輕愈好,
因為逆境才是真正習成長的機會。

chrnsy1028 發表於 2008-9-16 14:21

請問高中有關韓信點兵的問題

韓信點兵是中國上的一個有名的問題
她的原理期時就是餘數定理
只是問題來了~
在他運算的過程中~我發現到有些地方很奇怪~不知道怎樣弄出來的
所以想請問一下,如果有以下這樣的一個題目,要怎樣才可解出來與可以跟別人說

韓信點兵,每8人一隊或7人一隊都餘1人,每5人一隊餘2,已知兵員略多於兩千人,則兵員共有多少人?

weiye 發表於 2008-9-16 15:45

利用中國餘數定理(我比較習稱作"中國剩餘定理",又名"孫子定理")來找找通解,


(下面要開始找一個特殊解)

先找 "8和7的倍數,卻滿足被5除會於二的數",找到 (8×7)×2;

再找 "8和5的倍數,卻滿足被7除會於一的數",找到 (8×5)×3;

繼續找 "5和7的倍數,卻滿足被8除會於一的數",找到 (5×7)×3;

則找到一個特殊解 m=8×7×2 + 8×5×3 + 5×7×3。



(下面要說明這個特殊解是ok滴)

當 m 被 5 除的時候,可以發現 8×5×3 跟 5×7×3 的部分分別都會 5 整除,只有 8×7×2 被 5 除會於 2;

當 m 被 7 除的時候,可以發現 8×7×2 跟 5×7×3 的部分分別都會 7 整除,只有 8×5×3 被 7 除會於 1;

當 m 被 8 除的時候,可以發現 8×7×2 跟 8×5×3 的部分分別都會 8 整除,只有 5×7×3 被 8 除會於 1;

所以可以發現 m = 8×7×2 + 8×5×3 + 5×7×3 同時滿足題目要求的這個條件,所以找到一個特殊解。



再利用  〝5,7,8 最小公倍數 [5,7,8] 的倍數〞被 5,7,8 都會整除 的特性,

可以知道,對於任意整數 t,

    8×7×2 + 8×5×3 + 5×7×3 + [5,7,8]×t 一定也會滿足題目的要求,

所以令通解為 8×7×2 + 8×5×3 + 5×7×3 + [5,7,8]×t = 337 + 280 t,其中 t 為任意整數。



(下面要解完這個題目囉)

題目有說人數大概比兩千人略多一點點而已,所以就可以知道

  337 + 280 t > 2000

  ⇒ t > (2000 - 337) / 280 = 5.93928571..........

  ⇒ t 的最小正整數值為 6

  ⇒ 兵員數為 337 + (280 × 6) = 2017 人












題外話,Note:

中國剩餘定理跟 Lagrange 插值法原理都一樣,

都是先一次解決一小部分的問題,

然後加總起來就是合乎題目條件的答案。

頁: [1]

論壇程式使用 Discuz! Archiver   © 2001-2022 Comsenz Inc.