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 what is the largest monetary amount that cannot be obtained using only coins of specified denominations.[1] 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.
There is an explicit formula for the Frobenius number when there are only two different coin denominations. If the number of coin denominations is three or more, no explicit formula is known; but, for any fixed number of coin denominations, there is an algorithm 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]
Contents |
In mathematical terms the problem can be stated:
This largest integer is called the Frobenius number of the set { a1, a2, ..., an }, and is usually denoted by g(a1, a2, ..., an).
The requirement that the greatest common divisor (GCD) equal 1 is necessary in order for the Frobenius number to exist. If the GCD were not 1, every integer that is not a multiple of the GCD would be inexpressible as a linear, let alone conical, combination of the set, and therefore there would not be a largest such number. For example, if you had two types of coins valued at 4 cents and 6 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. On the other hand, whenever the GCD equals 1, the set of integers that cannot be expressed as a conical combination of { a1, a2, ..., an } 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. No closed-form solution is known for n > 2.[4]
If n = 1, then a1 = 1 so that all natural numbers can be formed. Hence no Frobenius number in one variable exists.
If n = 2, the Frobenius number can be found from the formula . This formula was discovered by James Joseph Sylvester in 1884.[5] Sylvester also demonstrated for this case that there are a total of non-representable integers.
Fast algorithms are known for three numbers, though the calculations can be very tedious if done by hand. Furthermore, lower- and upper bounds for the n = 3 Frobenius numbers have been determined. The Frobenius-type lower bound due to Davidson
is reported to be relatively sharp.[6]
A simple formula exists for the Frobenius number of a set of integers in arithmetic sequence.[7] Given integers a, d, s with gcd(a, d) = 1:
There also exists a closed form solution for the Frobenius number of a set in geometric sequence.[8] 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 included it in his algebra textbook co-authored with Anita Wah.[9] Picciotto thought of the application in the 1980s while dining with his son at McDonald's, working the problem out on a napkin. A McNugget number is the total number of McDonald's Chicken McNuggets in any number of boxes. The original boxes (prior to the introduction of the Happy Meal-sized nugget 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.[10] The fact that any integer larger than 43 is a McNugget number can be seen by considering the following integer partitions
implying that any larger integer can obtained by adding some number of 6's to the appropriate partition above.
Furthermore, a straightforward check demonstrates that 43 McNuggets can indeed not be purchased, as:
In rugby union, there are four types of scores: penalty goal (3 points), drop goal (3 points), try (5 points) and converted try (7 points). By combining these any points total is possible except 1, 2, or 4.
Similarly, in American football any score is possible in a non-forfeit game except 1. The only ways to score 1 point are by a single point conversion after a 6 point touchdown, or to win by forfeit, where the score will be recorded as 1-0. As 2 points are awarded for a safety and 3 points for a field goal, all other scores apart from 1 are possible.