本題剛看到可能會暴力列舉
但其實有了一些工具之後,這題其實沒有想像中難喔~
這題的關鍵是「連分數」
我們把題目給的17/76改寫為連分數
易知,要讓整體分數變大,則第一層分母應變小,因此第二層分母要變大,故第三層分母要變小
因此,將8用7來取代,化簡就得到答案:15/67
不過,當然在這兩者之間還有其他分數存在,因此我們必須檢驗這兩者之間有無其他的解
檢驗方式如下:我們假設有一分數m/n介於二者之間,那麼:
明顯可以看出,m小於100時,n沒有正整數解
所以這裡n沒有100以內的解
綜上所述,答案為15/67
另一種解法:
假設欲求的分數是
q / p ,p、q 為互質正整數,q < p ≤ 100 。
將此分數和 17 / 76 相減,得差為: (q / p) - (17 / 76) =
(76 q -17 p) / (76 p)
按題目所述,這個個分數相鄰,故以上的差要越小越好,所以:
- (76 q -17 p) 要越小越好 (不過要大於零)
- 76 和 p 的最小公倍數 (即通分後的分母) 要越大越好
因此,可以先讓 76 q -17 p = 1 (最小的可能值),即 76 q ÷ 17 = p 餘 1 ,找 p, q。換言之,就是找一個 76 的倍數,除以 17 後餘 1 即可。利用同餘的方法,很快能找出一組解:
i) 76 除以 17 餘 8。
ii) 8 × 2 = 16,除以 17 餘 16 ,也就是餘 (-1);故 8 × (-2) = -16,除以 17 就是餘 1。
iii) 其中, (-2) 除以 17 餘 (-2) ,也就是餘 15。
iv) 所以,76 × 15 除以 17 就是餘 1。即 q = 15,代回得 p = 67。
v) 要寫成通解,即 p = 76 k + 67、q = 17 k + 15 ,k 是整數。列幾個解如下:
以上的解,只有 p = 67、q = 15 都是 100 以內的正整數。
所以目前 15 / 67 是一組可能的解。可以證明它是最小的,也就是緊接著 15 / 76 的:
兩分數的差為 (76 q -17 p) / (76 p)
p = 67、q = 15 代回後得 1 / (76 × 67),其分子是 1;如果你選另一組 p, q,使分子 (76 q -17 p) = n ≥ 2 ,則n / (76 p) 一定會更大:因為 p 不能超過 100,n / (76 p) ≥ 1 / (76×50) > 1 / (76 × 67)。得證。
這個方法雖然略麻煩,但是可以適用其它的數字。舉例,若題目改問:「排在 1 / 3 之後的是多少?」
用以上方法來算,設 q / p,則兩分數的差是 (3 q - p) / (3 p)。
根據以上,令 (3 q - p) 越小越好,3 和 p 的公倍數越大越好。
令 3q - p = 1 (最小的),得 p = 3q - 1,即 p 除以 3 會餘 2。
所以,可令 p = 98 (最大的);然後,解得 q = 33。
所以找到的答案是 33 / 98。可以證明這是最小的解。