Coin problem
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,
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).
[2] 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.
[3][4] In mathematical terms, the problem can be stated: This largest integer is called the Frobenius number of the set
The existence of the Frobenius number depends on the condition that the greatest common divisor (GCD) is equal to 1.
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.
A closed-form solution exists for the coin problem only where n = 1 or 2.
[5][nb 1] Sylvester also demonstrated for this case that there are a total of
Reducing and re-arranging the coefficients by adding multiples of
This shows that half of the integers in the given range are representable; since there are
Formulae[9] and fast algorithms[10] 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.
for three variables is also known as:[12] In 1978, Wilf conjectured that given coprime integers
denotes the number of all non-representable positive integers.
[13] In 2015, an asymptotic version of this was proven by Moscariello and Sammartano.
[14] A simple formula exists for the Frobenius number of a set of integers in an arithmetic sequence.
from our arithmetic seq,e and the formula for the Frobenius number remains the same.
[16] There also exists a closed form solution for the Frobenius number of a set in a geometric sequence.
[17] Given integers m, n, k with gcd(m, n) = 1: 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,[19] and included it in his algebra textbook co-authored with Anita Wah.
[20] Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working out the problem on a napkin.
A straightforward check demonstrates that 43 McNuggets can indeed not be purchased, as: Since the introduction of the 4-piece Happy Meal–sized nugget boxes, the largest non–McNugget number is 11.
The following scores (in addition to 1, 2, and 4) 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 (which in this case has a value of 6).
The worst case complexity has an upper bound which can be given in terms of the Frobenius number of a given sequence of positive integers.
Petri nets are useful for modeling problems in distributed computing.
Sloping lines denote graphs of 2 x +5 y = n where n is the total in pence, and x and y are the non-negative number of 2p and 5p coins, respectively.
A point on a line gives a combination of 2p and 5p for its given total (green).
Multiple points on a line imply multiple possible combinations (blue).
Only lines with n = 1 or 3 have no points (red).
