2018年9月27日 星期四

代數解餘數問題 (Andy 奇想)

https://4rdp.blogspot.com/2018/09/andy.html

今年暑假 Andy 有一奇想,用代數解餘數問題,以往大家用中國餘式定理解題,他自己想另外方法來解,今記錄下來。

例題,一籃橘子,三個一堆餘一,五個一堆餘二,七個一堆餘三,十一個一堆餘五,請問總共最少多少個橘子?

假設橘子數量  x = 3a+1 = 5b+2 = 7c+3 = 11d+5
則  3a = 5b+1,  5b = 7c+1,  7c = 11d+2
3a = 5b+1    最小值  a = 2, b = 1
5b = 7c+1    最小值  b = 3, c = 2
7c = 11d+2   最小值 c = 5, d = 3

令 a = 2+5n,   b = 1+3n
令 b = 3+7m,  c = 2+5m
令 c = 5+11k,  d = 3+7k


3(2+5n) = 5(3+7m)+1
3n = 7m+2     最小值 n = 3, m = 1
5m = 11k+3    最小值 m = 5, k = 2

令 n = 3+7p,  m = 1+3p
令 m = 5+11q,  k = 2+5q

3p = 11q+4     最小值 p = 5, q = 1

把 p,q 值反帶回上式
n = 38,  m = 16,  k = 7

把 n,m,k 值反帶回上式
a = 192,  b = 115, c = 82,  d = 52

所以  x = 577


我觀察 Andy 從小就很喜歡二元一次整數解問題,訓練數學感 3 ─ 好難的小二數學 他的解法就是代值試算,所以本題最小值解的部分就是他從小的習慣,不過這要迭代很多次才能得值,解法蠻直觀,就先記錄下來。

沒有留言:

張貼留言