在小盤天秤上的硬幣稱重問題之準確解

尋找假幣是一個經典問題。本研究討論在給定f 個相同重量的假硬幣和r 個相同重量的真硬幣情況下，且天平的每個秤盤只能恰好容納一個硬幣時，要如何快速地將一對真假硬幣放在天平上。我們將這個問題與另外兩個看似無關的優化問題等價，其中一個是圖論的，而另一個是數論的，運用這兩個不同的領域讓我們可以用不同的觀點建構出最佳測試策略(optimal testing scheme)，並創新了一種有條件的整數分割問題(partition with avoidance)。此外，我們還討論了這個問題的一些推論性變體(inferential variants)，並展示了這些問題與原始問題的緊密關係。

關鍵字

假幣問題；條件整數分割；圖論

並列摘要

Searching for counterfeit coins is a classical problem. In this thesis, we study a variant of this problem where each pan of the balance scale can hold exactly one coin. Given f fake coins of the same weight and r real coins of the same weight, we show how to construct an optimal testing scheme, which uses the minimum number of comparisons in the worst case, that guarantees a real coin and a fake coin will be compared. We show that this problem is equivalent to two other seemingly unrelated optimisation problems, one from graph theory and the other from number theory, where the equivalences respectively allow us to prove optimality and speed up our construction method. Moreover, we also discuss some inferential variants of this problem, and demonstrate strong connections of these problems with the original one.