Re: [解題] 高一數學餘數韓信點兵

看板tutor作者Cactuss16 (Cake & Toast)時間16年前 (2008/08/25 02:27)推噓2(2推 0噓 7→)

留言9則, 3人參與討論串7/7 (看更多)

※ 引述《Cactuss16 (Cake & Toast)》之銘言： : 1.年級：高一 : 2.科目：數學 : 3.章節：整數、餘數 : 4.題目：韓信點兵，每 7人一數餘 6, 11人一數餘 5, 13人一數餘 4 : 問士兵最少有幾人？ : 解：797 人 : 5.想法： : 點兵的題目，可是餘數不同、不足數也不同，可能要用其他辦法 : 高中有做過，可是臨時想不到怎麼做.... Orz 受益太多了，我試著整理一下... 看到題目一般直覺會以代數寫出 X = 7q1 + 6 = 11q2 + 5 = 13q3 + 4 最終要寫成 X = 〔7,11,13〕q + x x 以 7,11,13 除之分別餘 6,5,4 也就是士兵最少有幾人 phxcon 版友的想法我不曉得如何直覺說明, x = 〔11,13〕b + x2 且 x%7 = 6 x2= 13c + 4 且 x2%7 = 5 c 套數字推算 x2，b 再套數字推算 x 得解 ncusnoopy 版友是 X = 13q1 + 4 ## 由大到小算的次數會比較少 = 13(11q2 + r1) + 4 ## 想辦法將除數 11 導入式子 ## 且 0<r1<11，說明算10次以內必有解 = 143q2 + 13r1 + 4 ## (13r1 + 4)%11 = 5, r1套數字推算為6 = 143(7q3 + r2) + 82 ## r1=6 帶入, 再將除數 7導入式子, 0<r2<7 = 1001q3 + 143r2 + 82 ## (143r2 + 82)%7=6, r2套數字推算為5 ## 此式同等 q3〔7,11,13〕+r2〔11,13〕+13r1 +4 = 1001q3 + 797 kioskyline 版友則提供了不用套數字的方法 ex. (13r1 + 4)%11 = 5 => [(11+2)r1 -1]%11 = 0 ## 11的倍數就不用再管了 => [2r1+(11-12)]%11 = 0 ## 1沒辦法被 2整除, 所以再借 11 => 2r1-12=0 => r1=6 ex. (143r2 + 82)%7 = 6 => [(140+3)r2 + 76]%7 = 0 ## 7的倍數不用管了 => [3r2 + (77-1)]%7 = 0 => (3r2 - 1)%7 = 0 ## r2=1/3 非整數, 不行 => [3r2 + (7-8)]%7 = 0 ## 繼續找 8, 15 => 3r2 - 15 = 0 => r2 = 5 -------------/自虐分隔線/-------------- 有了這個數學方法，似乎就能解決此類題目若一數，以 123 除之餘 101, 231除之餘 98, 312除之餘 95 X = 312q1 + 95 = 312(77q2 +r1) + 95 ## 77=231/(312,231), 0<r1<77 = 〔312,231〕q2 + 312r1 + 95 ## 312r1 +95 = 231k + 98 g.c.d 提出 => 3(104r1-77k) -3 = 0 由此知餘數之差必為 g.c.d.的倍數, 才有解 => 104r1-77k = 1 => (27r1-1)%77 = 0 1, 78, 155, 232, 309, 386, 463, 540 可被27整除似乎無更快速解...Orz => 27r1-540=0 => r1=20 = 〔312,231〕(41q3 +r2) + 6240 + 95 = 〔312,231,123〕q3 + 〔312,231〕r2 + 6335 ## 〔312,231〕r2 + 6335 = 123m + 101 => 3*104*77r2 + 6234 = 123m => 3(104*77r2-41m) + 6234 = 0 => 104*77r2-41m + 2078 = 0 => (104*77r2 + 2078)%41 = 0 => (22*36r2 - 13)%41 = 0 => (11*31r2 - 13)%41 = 0 => (11*31r2 - 13)%41 = 0 => (13r2 - 13)%41=0 => r2=1 = 〔312,231,123〕q3 + 30359 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.193.148.213 ※ 編輯: Cactuss16 來自: 123.193.148.213 (08/25 02:52)

推

netneto

08/25 10:00, , 1^F

08/25 10:00, 1^F

→

Cactuss16

08/25 10:04, , 2^F

08/25 10:04, 2^F

→

Cactuss16

08/25 10:54, , 3^F

08/25 10:54, 3^F