Re: [線代] 最小公倍數的問題
※ 引述《incog ()》之銘言：
: 有一個圈圈格數總共66格，每格編號從00～65
: 有一人每次可選擇前進11格，或者31格
: （因為是圈圈，所以前進超過66格時，會越過00繼續起算）
: 如果兩者至少用到一次，請問他最少要走過幾次，才能回到原點？？
: 我朋友說用橫軸跟縱軸就能求解，但是原理我不太懂
: 不知道有人能解釋一下原理是什麼意思嗎？
: 例如從格數1出發，橫軸擺+11，縱軸擺+31
: 01 12 23 34 45 56 01
: 32 43 54 65 10 21
: 63 08 19 30 41 52
: 28 39 50 61 06 17
: 59 04 15 26 37 48
: 24 35 46 57 02 13
: 55 00 11 22 33 44
: 20 31 42 53 64 09
: 51 62 07 18 29 40
: 16 27 38 49 60 05
: 47 58 03 14 25 36
: 12 23 34 45 56 01
原題等價於
11x+31y-66z=0, x,y,z為正整數, 求 x+y 的最小值
sol.
易知原方程所有整數解為
{x=-31u+6v
{y= 11u , u,v為整數
{z= v
原題等價於
u>0, v>0, -31u+6v>0, u,v為整數, 求-20u+6v的最小值
由斜率判斷可知, (u,v)=(1,6)時, -20u+6v最小為16
即(x,y)=(5,11)時, x+y最小為16
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.31.174
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1409798314.A.6F9.html
推
09/04 13:36, , 1F
09/04 13:36, 1F
討論串 (同標題文章)