The coin problem (also referred to as the Frobenius coin problem or Frobenius problem, after the mathematician Ferdinand Frobenius) is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations, for example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations has no common divisor greater than 1.
There is an explicit formula for the Frobenius number when there are only two different coin denominations, and : the Frobenius number is then . If the number of coin denominations is three or more, no explicit formula is known. However, for any fixed number of coin denominations, there is an algorithm for computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input). No known algorithm is polynomial time in the number of coin denominations, and the general problem, where the number of coin denominations may be as large as desired, is NP-hard.
Statement
In mathematical terms, the problem can be stated:
Given positive integers such that gcd, find the largest integer that cannot be expressed as an integer conical combination of these numbers, i.e., as a sum: where are non-negative integers.
This largest integer is called the Frobenius number of the set , and is usually denoted by
The existence of the Frobenius number depends on the condition that the greatest common divisor (GCD) is equal to 1. Indeed, the potential sums are multiples of the GCD in all cases. Hence, if it is not 1, then there are always arbitrarily large numbers that cannot be obtained as sums. For example, if you had two types of coins valued at 6 cents and 14 cents, the GCD would equal 2, and there would be no way to combine any number of such coins to produce a sum which was an odd number; additionally, even numbers 2, 4, 8, 10, 16 and 22 (less than m=24) could not be formed, either. On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of is bounded according to Schur's theorem, and therefore the Frobenius number exists.
Frobenius numbers for small n
A closed-form solution exists for the coin problem only where n = 1 or 2. No closed-form solution is known for n > 2.
n = 1
If , then we must have so that all natural numbers can be formed.
n = 2
If , the Frobenius number can be found from the formula , which was discovered by James Joseph Sylvester in 1882. Sylvester also demonstrated for this case that there are a total of non-representable (positive) integers.
Another form of the equation for is given by Skupień in this proposition: If and then, for each , there is exactly one pair of nonnegative integers and such that and .
The formula is proved as follows. Suppose we wish to construct the number . Since , all of the integers for are mutually distinct modulo . Thus any integer must be congruent modulo to one of these residues; in particular, taking there is a unique value of and a unique integer , such that . Rearranging, we have a nonnegative integer so that . Indeed, because .
To show that exactly half of the integers are representable as non-negative integer linear combinations, one first shows that if the integer is representable, then is not representable, where .
One then shows that the converse is true as well: if is not representable, then is representable. To show this, use the fact that , which allows us to write . Reducing and re-arranging the coefficients by adding multiples of as necessary, we can assume (in fact, this is the unique such satisfying the equation and inequalities).
Similarly we take satisfying and . Now we can add these equations to write which, using yields . The integer is positive, because . In fact, since the left-hand side of is divisible by , and , we must have that is divisible by . Yet , so , so that . Substituting this into and subtracting from both sides yields . So . This implies that , which means that exactly one of or is negative. If is negative, then , which means that is representable; the case when is negative entails that is representable.
Thus for any non-negative integer , we know that exactly one of or is representable (and these are distinct, because must be odd as the integers are relatively prime). This shows that half of the integers in the given range are representable; since there are integers in the range , this gives the desired result.