Coin problem
In mathematics, the coin problem 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 is setwise coprime.
There is an explicit formula for the Frobenius number when there are only two different coin denominations, and, where the greatest common divisor of these two numbers is 1:. 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. 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: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 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 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 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 .
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. 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.
''n'' = 3
Formulae and fast algorithms are known for three numbers though the calculations can be very tedious if done by hand.Simpler lower and upper bounds for Frobenius numbers for n = 3 have also been determined. The asymptotic lower bound due to Davison
is relatively sharp.
The asymptotic average behaviour of for three variables is also known as:
Wilf's conjecture
In 1978, Wilf conjectured that given coprime integers, and their Frobenius number, we havewhere denotes the number of all non-representable positive integers. In 2015, an asymptotic version of this was proven by Moscariello and Sammartano.
Frobenius numbers for special sets
Arithmetic sequences
A simple formula exists for the Frobenius number of a set of integers in an arithmetic sequence. Given integers a, d, w with gcd = 1:The case above may be expressed as a special case of this formula.
In the event that, we can omit any subset of the elements from our arithmetic sequence and the formula for the Frobenius number remains the same.
Geometric sequences
There also exists a closed form solution for the Frobenius number of a set in a geometric sequence. Given integers m, n, k with gcd = 1:Examples and applications
McNugget numbers
One special case of the coin problem is sometimes also referred to as the McNugget numbers. The McNuggets version of the coin problem was introduced by Henri Picciotto, who placed it as a puzzle in Games Magazine in 1987, and included it in his algebra textbook co-authored with Anita Wah. Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working out the problem on a napkin. A McNugget number is the total number of McDonald's Chicken McNuggets in any number of boxes. In the United Kingdom, the original boxes were of 6, 9, and 20 nuggets.According to Schur's theorem, since 6, 9, and 20 are relatively prime, any sufficiently large integer can be expressed as a linear combination of these three. Therefore, there exists a largest non–McNugget number, and all integers larger than it are McNugget numbers. Namely, every positive integer is a McNugget number, with the finite number of exceptions:
Thus the largest non–McNugget number is 43. The fact that any integer larger than 43 is a McNugget number can be seen by considering the following integer partitions
Any larger integer can be obtained by adding some number of 6s to the appropriate partition above. A straightforward check demonstrates that 43 McNuggets can indeed not be purchased, as:
- boxes of 6 and 9 alone cannot form 43 as these can only create multiples of 3 ;
- including a single box of 20 does not help, as the required remainder is also not a multiple of 3; and
- more than one box of 20, complemented with boxes of size 6 or larger, obviously cannot lead to a total of 43 McNuggets.
Other examples
In rugby union, there are four types of scores: penalty goal, drop goal, try and converted try. By combining these, any points total is possible except 1, 2, or 4. In rugby sevens, although all four types of scoring are permitted, attempts at penalty goals are rare, and drop goals are almost unknown. This means that team scores almost always consist of multiples of tries and converted tries. The following scores cannot be made from multiples of 5 and 7 and so are almost never seen in sevens: 3, 6, 8, 9, 11, 13, 16, 18 and 23. By way of example, none of these scores was recorded in any game in the 2014-15 Sevens World Series.Similarly, in American football, the only way for a team to score exactly one point is if a safety is awarded against the opposing team when they attempt to convert after a touchdown. As 2 points are awarded for safeties from regular play, and 3 points are awarded for field goals, all scores other than 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 and 7–1 are possible. This is directly related to the concept of Scorigami.