三個變數之硬幣問題之延伸研究

Abstract

硬幣問題又叫找錢問題或換硬幣問題，是一個十分著名的問題。硬幣問題是求由給定不同幣值的硬幣，其最大不能湊出來的金額。在三個變數下，此問題尚未有通解，但已知在某些情況下有解或是上限值。在2007年吳京達的論文「三個變數之硬幣問題之研究」證明三個變數下最小數為6以下的解。本論文繼續在三個變數的情況做討論，以填表法加上設計程式猜測，證明最小數為7的解規則，猜測最小數為16以下的解規則，並且整理出證明的原則，和實作出部分的機械證明。期望將機械證明完成，破解最小數為16以下的三個變數硬幣問題，未來進一步破解大量三個變數下的硬幣問題。 The coin problem is known as the money-changing problem, the coin exchange problem, or the stamp exchange problem, which is an old and famous problem. The coin problem is to ask for the largest integer that cannot be made up from the given integers. Now it already has solutions for two variables and has been proven that there is no closed-form solution for more than three variables. For three variables, there are upper bounds or certain formulas in some situations. This thesis extends the result of “Research on the Coin Problem for Three Variables”. We build a program that can guess the linear formulas of the coin problem for three variables, with its smallest value up to 16. Also, we prove the guessing of the linear formulas is correct when the smallest value is 7. Furthermore, we deduced some properties for automated theorem proving and built a program that can partly prove the linear formulas. With these results, we may solve the coin problem for three variables in the future.