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

Research on the Coin Problem for Three Variables

吳京達(Jing-Da Wu)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2006年)

摘要

硬幣問題又叫找錢問題或換硬幣問題，也有人叫它做兌換郵票問題，是一個十分著名的問題。
由於現在於兩個變數的情況下已有公式解，而在四個變數以上已知無closed-form solution，故本論文在三個變數的情況下做討論。此部分的問題現在尚未有通解，但已知在某些情況下有解或是上限值。所以本論文的研究目標是以不同於現有數學討論的方式，運用電腦的幫助，由大量的數據之中，整理出新的規則，希望能由新規則及舊規則推廣得到更完整的公式，以解決此問題。
我們在此問題之的某些特例之上提出一種快速的解法，我們發現了一種填表法，剛好可利用它來看出Frobenius number的規律性，因此可在最小數為2、3、4、5或6時解出所有此問題之解，且只需簡單之計算。我們發現且證明了在最小數為這些特定數時擁有某些特定之規則可快速解此問題。

關鍵字

硬幣問題 ； 找錢問題 ； 換硬幣問題 ； Frobenius數

並列摘要

Coin Problem is known as Money-Changing Problem, Coin Exchange Problem, or Stamp Exchange Problem. It is a very famous problem.
Now it already has solution for two variables. It has been proven that there is no closed-form solution for more than three variables. But it is already known that there are upper bounds in some situations.
In this thesis, we focus on solving the coin problem for three variables. We discover a table-filling approach which can be used to deduce the regularities of Frobenius numbers. From it, we derive a fast way to find answers in some special cases, i.e. the smallest vaule among the three variables is either 2, 3, 4, 5 or 6. It can find answers directly from the formulas which are very easy to be calculated.

並列關鍵字

Coin Problem ； Money-Changing Problem ； Coin Exchange Problem ； Frobenius Number

參考文獻

[1] F. Aguil?, A. Miralles, “On the Frobenius’ problem of three numbers,” Discrete Mathematics &Theoretical Computer Science, Vol.AE, 2005, pp.317-322.

[2] M. Beck, D. Einstein, S. Zacks, “Some experimental results on the Frobenius problem,” Experimental Mathematics, Vol.12, 2003, pp.263-269.

[5] S. B?cker, Z. Lipt?k, “The money changing problem revisited: computing the Frobenius number in time O(ka1),” Computing and Combinatorics Conference, Kunming, China, 2005.

[6] J. Dixmier, “Proof of a conjecture by Erd?os and Graham concerning the problem of Frobenius,” Journal of Number Theory, Vol.34, 1990, pp.198-209.

[7] R. J. Levit, “A minimum solution for a diophantine equation,” American Mathematical Monthly, Vol.63, 1956, pp.646-651.