TOPICS
Search

Coin Problem


Let there be n>=2 integers 0<a_1<...<a_n with GCD(a_1,a_2,...,a_n)=1. The values a_i represent the denominations of n different coins, where these denominations have greatest common divisor of 1. The sums of money that can be represented using the given coins are then given by

 N=sum_(i=1)^na_ix_i,
(1)

where the x_i are nonnegative integers giving the numbers of each coin used. If a_1=1, it is obviously possibly to represent any quantity of money N. However, in the general case, only some quantities N can be produced. For example, if the allowed coins are (2,5,10), it is impossible to represent N=1 and 3, although all other quantities can be represented.

Determining the function g(a_1,a_2,...,a_n) giving the greatest N=g(a_1,a_2,...,a_n) for which there is no solution is called the coin problem, or sometimes the money-changing problem. The largest such N for a given problem is called the Frobenius number g(a_1,a_2,...).

The result

g(a_1,a_2)=(a_1-1)(a_2-1)-1
(2)
=a_1a_2-(a_1+a_2)
(3)

(Nijenhuis and Wilf 1972) is mathematical folklore. The total number of such nonrepresentable amounts is given by

 1/2(N+1)=1/2(a_1-1)(a_2-1).
(4)

The largest nonrepresentable amounts g(a_1,a_2) for two coins with denominations a_1 and a_2 are summarized below.

a_1a_2g(a_1,a_2)a_1a_2g(a_1,a_2)
2314717
2534923
2755619
2975723
3455827
3575931
37116729
38137841
310177947
451171053

Fast algorithms are also known for three numbers, but the more general problem for an arbitrary number of numbers is known to be NP-hard if n is fixed (Kannan 1992) or n is variable (Ramírez-Alfonsín 1996).

There is no closed-form solution for n=3, although a semi-explicit solution is known which allows values to be computed quickly (Selmer and Beyer 1978, Rödseth 1978, Greenberg 1988; Beck and Robins 2006). Values for small a_i are summarized below.

ag(a)ag(a)
(2,3,4)1(2,4,7)5
(2,3,5)1(2,5,6)3
(2,3,6)1(2,5,7)3
(2,3,7)1(2,6,7)5
(2,4,5)3(3,4,5)2

No closed-form solution is known for n>4.


See also

Frobenius Number, Greedy Algorithm, Knapsack Problem, Postage Stamp Problem, Subset Sum Problem

Explore with Wolfram|Alpha

References

Beck, M. and Robins, S. "The Coin-Exchange Problem of Frobenius." §C1 in Computing the Continuous Discretely. New York: Springer, pp. 3-23, 2006. http://math.sfsu.edu/beck/ccd.html.Berlekamp, E. R.; Conway, J. H; and Guy, R. K. Winning Ways for Your Mathematical Plays, Vol. 2: Games in Particular. London: Academic Press, 1982.Brauer, A. "On a Problem of Partitions." Amer. J. Math. 64, 299-312, 1942.Brauer, A. and Seelbinder, B. M. "On a Problem of Partitions. II." Amer. J. Math. 76, 343-346, 1954.Davison, J. L. "On the Linear Diophantine Problem of Frobenius." J. Number Th. 48, 353-363, 1994.Greenberg, H. "Solution to a Linear Diophantine Equation for Nonnegative Integers." J. Algorithms 9, 343-353, 1988.Guy, R. K. "The Money-Changing Problem." §C7 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 113-114, 1994.Kannan, R. "Lattice Translates of a Polytope and the Frobenius Problem." Combinatorica 12, 161-177, 1992.Nabiyev, V. V. Algorithms: From Theory to Applications. Ankara, Turkey: Seckin, p. 799, 2007.Nijenhuis, A. "A Minimal-Path Algorithm for the 'Money Changing Problem.' " Amer. Math. Monthly 86, 832-835, 1979.Nijenhuis, A. and Wilf, H. S. "Representations of Integers by Linear Forms in Nonnegative Integers." J. Number Th. 4, 98-106, 1972.Ramírez-Alfonsín, J. L. "Complexity of the Frobenius Problem." Combinatorica 16, 143-147, 1996.Ramírez-Alfonsín, J. L. The Diophantine Frobenius Problem. Oxford, England: Oxford University Press, 2005.Rødseth, Ø. J. "On a Linear Diophantine Problem of Frobenius." J. reine angew. Math. 301, 171-178, 1978.Rødseth, Ø. J. "On a Linear Diophantine Problem of Frobenius. II." J. reine angew. Math. 307/308, 431-440, 1979.Selmer, E. S. "The Linear Diophantine Problem of Frobenius." J. reine angew. Math. 293/294, 1-17, 1977.Selmer, E. S. and Beyer, Ö. "On the Linear Diophantine Problem of Frobenius in Three Variables." J. reine angew. Math. 301, 161-170, 1978.Sylvester, J. J. "Question 7382." Mathematical Questions from the Educational Times 41, 21, 1884. Wagon, S. "Greedy Coins." http://library.wolfram.com/infocenter/MathSource/5187/.Wilf, H. "A Circle of Lights Algorithm for the 'Money Changing Problem.' " Amer. Math. Monthly 85, 562-565, 1978.

Referenced on Wolfram|Alpha

Coin Problem

Cite this as:

Weisstein, Eric W. "Coin Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CoinProblem.html

Subject classifications