最簡分數的排列謎題解析--GameSchool遊戲學校

精選謎題列表

其它謎題列表

謎題分類

最簡分數的排列 - 謎題解析

本題剛看到可能會暴力列舉 
但其實有了一些工具之後，這題其實沒有想像中難喔~ 
這題的關鍵是「連分數」 
我們把題目給的17/76改寫為連分數 
<img src="http://gameschool.cc/ugc/img/content/d4/1d/2350.png" style="width:517px;height:153px;" alt="" /> 
易知，要讓整體分數變大，則第一層分母應變小，因此第二層分母要變大，故第三層分母要變小 
因此，將8用7來取代，化簡就得到答案:15/67 
不過，當然在這兩者之間還有其他分數存在，因此我們必須檢驗這兩者之間有無其他的解 
檢驗方式如下:我們假設有一分數m/n介於二者之間，那麼: 
<img src="http://gameschool.cc/ugc/img/content/d4/1d/2351.png" style="width:431px;height:88px;" alt="" /> 
明顯可以看出，m小於100時，n沒有正整數解 
所以這裡n沒有100以內的解 
綜上所述，答案為15/67 
 <hr /> 
另一種解法： 
 
假設欲求的分數是 q / p ，p、q 為互質正整數，q &lt; p ≤ 100 。 
將此分數和 17 / 76 相減，得差為： (q / p) - (17 / 76) = (76 q -17 p) / (76 p) 
按題目所述，這個個分數相鄰，故以上的差要越小越好，所以：<ul><li>(76 q -17 p) 要越小越好 (不過要大於零)</li>
<li>76 和 p 的最小公倍數 (即通分後的分母) 要越大越好 </li>
</ul>因此，可以先讓 76 q -17 p = 1 (最小的可能值)，即 76 q ÷ 17 = p 餘 1 ，找 p, q。換言之，就是找一個 76 的倍數，除以 17 後餘 1 即可。利用同餘的方法，很快能找出一組解：<div style="margin-left:40px;">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 是整數。列幾個解如下：<table align="center" border="1" style="width:500px;"><tr><td>p</td>
<td>-9</td>
<td>67</td>
<td>143</td>
</tr><tr><td>q</td>
<td>-2</td>
<td>15</td>
<td>32</td>
</tr></table></div><div>以上的解，只有 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)  &gt; 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。可以證明這是最小的解。 
 
 </div>

備註

關於GS	好玩遊戲		益智謎題		聯絡我們
關於遊戲學校常見問題服務條款隱私政策 144,133,115	自造遊戲 X檔案夢遊先生神秘解謎 CN卡通頻道 GROW成長物品拆解	密室脫逃遊戲方塊益智遊戲偵探解謎遊戲益智冒險遊戲策略棋弈遊戲觀察尋找遊戲其它益智遊戲	邏輯數學找規律 / 找不同空間概念快問快答移動成立創造力	謎語 / 燈謎偵探思考眼腦並用文字拆解圖其他謎題	留言 / 錯誤回報 service@gameschool.cc
					其他
					GS名人榜攻略編輯總表