8
$\begingroup$

I don't know the proper terms to type into Google, so please pardon me for asking here first.

While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so coins of a currency (let us, say, use the coins of the American dollar as an example) can be used to total to a given amount. For instance, one can have five coins totaling to forty cents: three dimes and two nickels.

1) How does one find other $n$ combinations of coins that can total to a set amount?

To use my example, are there other five coins that can total to forty cents? How might one algorithmically prove that those are the only solutions?

2) Given an amount not equal to a denomination, what is the minimum number of coins needed to be equivalent to the given amount?

For instance, one can have forty cents in three coins: a quarter, a dime, and a nickel. How does one algorithmically show that the "magic number" for forty cents is three (i.e., one cannot find two coins whose amounts total to forty cents)?

As mentioned already, this isn't homework; just idle curiosity. Any pointers to algorithms would be appreciated!

  • 2
    see Harris, Hirst, and Mossinghoff, *Combinatorics and Graph Theory*, 2nd ed., pp. 171--177 (Section 2.6.3, "Changing Money"). They use generating functions.2011-02-14
  • 2
    Here's a very similar question: http://math.stackexchange.com/questions/15521/making-change-for-a-dollar-and-other-number-partitioning-problems/15548#155482011-02-14

1 Answers 1