上一道數學謎題
下一道數學謎題

最簡分數的排列數學謎題

答對率:82%
形如p/q,且p、q是互質的正整數者,我們稱之為最簡分數
假如我們將0到1之中,分母小於100的最簡分數全部列出來,並且由小而大排列
那麼,排在17/76之後的應該是?
ms0592138(小分/阿分/繽紛)2014-08-26提供
來源:102北一區(二)
看答案
15/67

解析

我要編輯
本題剛看到可能會暴力列舉
但其實有了一些工具之後,這題其實沒有想像中難喔~
這題的關鍵是「連分數」
我們把題目給的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 -9 67 143
q -2 15 32
以上的解,只有 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。可以證明這是最小的解。


 
5,980
上一道數學謎題
下一道數學謎題