Coin problem

From Wikipedia, the free encyclopedia

In mathematics, a coin problem is any of a class of problems of the general form:

You have only certain coins available to you, say seven-quatloo and ten-quatloo coins. You have as many of each size as you want; can you make exact change for any number of quatloos, or any number from a certain size onward? (With only Q7 and Q10 coins, there is no way to make change for eight quatloos, but every amount greater than Q53 can be changed.) If so, what is that size? (This need not involve coins: the same question can be asked of stamps, boxes, or chicken McNuggets.)

If all coins are an even number of quatloos, you can't make exact change for any odd number of quatloos; this will also be true if the denominations have three, or some larger number, as common divisor. So, in more precise language:

Given positive integers: $a_1,a_2,\dotsb,a_n$ , whose greatest common divisor $\operatorname{gcd}(a_1,\dots,a_n)$ is 1, find the largest number N that cannot be expressed as

$a_1x_1+a_2x_2+\dotsb+a_nx_n,$

for some non-negative integers $x_1,x_2,\dotsb,x_n$ .

(If the greatest common divisor is not equal to 1 then $N$ does not exist because only multiples of the gcd can occur as linear combinations as above; but if the g.c.d. is 1, there is an $N$ . This largest number is sometimes called the Frobenius number, while the Diophantine equation

$b=a_1x_1+a_2x_2+\dotsb+a_nx_n$

is sometimes referred to as the Frobenius equation.

1 Solutions
2 Examples
- 2.1 McNugget numbers
- 2.2 Other examples
3 External links

[edit] Solutions

The coin problem has been solved for $n = 1,2,3$ . No closed-form solution is known for $n > 3$ .

[edit] n = 1

If $n = 1$ , then unless $a 1 = 1$ , there will be an infinite number of positive integers m that cannot be expressed as $m = a 1 x 1$ (those not divisible by $a 1$ ).

[edit] n = 2

If $n = 2$ , the Frobenius number can be found from the formula $b = a 1 a 2 - a 1 - a 2$ . This formula was first discovered by James Joseph Sylvester in 1884.

[edit] n = 3

Fast algorithms are known for three numbers, though the calculations can be very tedious if done by hand.

[edit] Examples

[edit] McNugget numbers

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 were of 6, 9, and 20 nuggets. Since the Happy Meal-sized nugget boxes of 4 can now be purchased separately, the modern McNugget numbers are linear combinations of 4, 6, 9, and 20.

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. Therefor, there exists a largest non-McNugget number, and all numbers larger than it are McNugget numbers. For the modern version of the McNugget numbers, 4=2*2 and 9=3*3 suffice for the theorem to apply.

The McNugget numbers are as follows:

Original McNugget numbers: all integers except 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43.

Modern McNugget numbers: all integers except 1, 2, 3, 5, 7, and 11.

[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.