Coin problem

From Wikipedia, the free encyclopedia

The coin problem (also referred to as Frobenius coin problem or Frobenius problem) is a mathematics problem associated with the German mathematician Ferdinand Georg Frobenius and often introduced in the context of making exact change given the availability of coins of specific denominations.

With only 2 pence and 5 pence coins available, one cannot make exact change for 3 pence, but one can for any higher amount.
With only 2 pence and 5 pence coins available, one cannot make exact change for 3 pence, but one can for any higher amount.

In mathematical terms the problem can be stated:

Given n natural numbers a_1, a_2, \dots , a_n with greatest common divisor 1, find the largest natural number that can not be expressed as a non-negative integer combination of these n numbers.

For a given set \{\,a_1, a_2, \dots , a_n\,\} this largest number is referred to as the Frobenius number g(a_1, a_2, \dots , a_n). The existence of such a Frobenius number is tightly linked to the condition GCD(a_1, a_2, \dots , a_n) = 1 and follows from Schur's theorem.

Determining the Frobenius number for arbitrary n is known to be NP-hard.[1]

Contents

[edit] Frobenius numbers for small n

A closed-form solution exists for the coin problem only where n=1,2 or 3. No closed-form solution is known for n>3. [2][3]

[edit] n = 1

If n = 1, then a1 = 1 so that all natural numbers can be formed. Hence no Frobenius number in one variable exists.

[edit] n = 2

If n = 2, the Frobenius number can be found from the formula g(a1,a2) = a1a2 − a1 − a2. This formula was discovered by James Joseph Sylvester in 1884.[4] Sylvester also demonstrated for this case that there are a total of N(a1,a2) = (a1 − 1)(a2 − 1) / 2 non-representable integers.

[edit] n = 3

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

g(a_1, a_2, a_3) \geq \sqrt{3a_1a_2a_3} - a_1 - a_2 - a_3

is reported to be relatively sharp.[5]

[edit] Examples

[edit] McNugget numbers

McDonald's Chicken McNuggets in a box of 20.
McDonald's Chicken McNuggets in a box of 20.

One special case of the coin problem is sometimes also referred to as the "McNugget numbers". 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 number can be expressed as a linear combination of these numbers. They are relatively prime because 6=2*3, 9=3*3, and 20=2*2*5, making 1 the greatest common divisor. Therefore, there exists a largest non-McNugget number, and all numbers larger than it are McNugget numbers.

Graphical solution of the Chicken McNuggets problem. The grid of points indicates that quantities that can be purchased are any positive multiple of 3 (with the exception of 3 itself) and any positive multiple of 20, as well as linear combinations thereof. Each sloping line x+y=k represents a total number of k nuggets. A red line goes through no grid points, so this number of nuggets cannot be purchased. A blue line goes through at least one grid point, so this number of nuggets can be purchased. The highest red line is x+y=43.
Graphical solution of the Chicken McNuggets problem. The grid of points indicates that quantities that can be purchased are any positive multiple of 3 (with the exception of 3 itself) and any positive multiple of 20, as well as linear combinations thereof. Each sloping line x+y=k represents a total number of k nuggets. A red line goes through no grid points, so this number of nuggets cannot be purchased. A blue line goes through at least one grid point, so this number of nuggets can be purchased. The highest red line is x+y=43.

The largest non-McNugget number is 43.[6] The fact that any number of McNuggets larger than 43 can be purchased, can be seen by considering that

44 = 6 + 9 + 9 + 20
45 = 9 + 9 + 9 + 9 + 9
46 = 6 + 20 + 20
47 = 9 + 9 + 9 + 20
48 = 6 + 6 + 9 + 9 + 9 + 9
49 = 9 + 20 + 20

and that any larger number of McNuggets can be ordered by adding the right number of boxes of 6 to the appropriate combination above.

Furthermore, a straightforward check demonstrates that 43 McNuggets can indeed not be purchased, as:

1) boxes of 6 and 9 alone can not form 43 as these can only create multiples of 3 (with the exception of 3 itself);

2) including a single box of 20 does not help, as the required remainder (23) is also not a multiple of 3; and

3) more than one box of 20, complemented with boxes of size 6 or larger, obviously can not lead to a total of 43 McNuggets.

The McNugget numbers are all natural numbers except the non-McNugget numbers 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43 (sequence A065003 in OEIS).

[edit] Other examples

Another case exists for 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 every score is possible except 1. The only way to score 1 point is AFTER a 6 point score. 2 points from a safety, and 3 from field goals mean all other numbers are possible.

[edit] References

  1. ^ D. Beihoffer, J. Hendry, A. Nijenhuis, and S. Wagon: Faster algorithms for Frobenius numbers.
  2. ^ Eric W. Weisstein, Coin Problem at MathWorld.
  3. ^ Michael Spivey, Quadratic residues and the Frobenius coin problem.
  4. ^ J.J. Sylvester, Question 7382, Mathematical Questions from the Educational Times, 37 (1884) p.26.
  5. ^ M. Beck and S. Zacks, Refined upper bounds for the linear Diophantine problem of Frobenius; Adv. Appl. Math. 32 (2004) p. 454 - 467.
  6. ^ Eric W. Weisstein, McNugget Number at MathWorld.

[edit] External links

Languages