Coin problem

Uses your system voice; voice and rate in settings.

Snapshot

≈ 11 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, 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 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, x and y , where the greatest common divisor of these two numbers is 1: xy-x-y . 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 (in the logarithms of the coin denominations forming an input).

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.

In mathematics, 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 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, x and y , where the greatest common divisor of these two numbers is 1: xy-x-y . 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 (in the logarithms of the coin denominations forming an input).

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. Given positive integers a_1,a_2,\dots,a_n such that gcd (a_1,a_2,\dots,a_n)=1 , find the largest integer that cannot be expressed as an integer conical combination of these numbers, i.e., as a sum: k_1a_1+k_2a_2+\dots+k_na_n where k_1,k_2,\dots,k_n are non-negative integers.

This largest integer is called the Frobenius number of the set \{a_1,a_2,\dots,a_n\} , and is usually denoted by g(a_1,a_2,\dots,a_n) The existence of the Frobenius number depends on the condition that the greatest common divisor (GCD) 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 (less than m=24) 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 \{a_1,a_2,\dots,a_n\} 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. === n = 1 === If n=1 , then we must have a_1=1 so that all natural numbers can be formed. === n = 2 === If n=2 , the Frobenius number can be found from the formula g(a_1, a_2) = a_1a_2-a_1-a_2 , which was discovered by James Joseph Sylvester in 1882. Sylvester also demonstrated for this case that there are a total of N(a_1, a_2) = (a_1-1)(a_2-1)/2 non-representable (positive) integers.

Another form of the equation for g(a_1, a_2) is given by Skupień in this proposition: If a_1,a_2 \in \mathbb{N} and \gcd(a_1, a_2) = 1 then, for each n \ge (a_1-1)(a_2-1) , there is exactly one pair of nonnegative integers \rho and \sigma such that \sigma and n = \rho a_1 +\sigma a_2 . The formula is proved as follows. Suppose we wish to construct the number n \ge (a_1-1)(a_2-1) . Since \gcd(a_1, a_2) = 1 , all of the integers n - j a_2 for j=0,1,\ldots,a_1-1 are mutually distinct modulo a_1 .

Thus any integer m must be congruent modulo a_1 to one of these residues; in particular, taking m = a_1 there is a unique value of j=\sigma \ge 0 and a unique integer t , such that a_1 = n - \sigma a_2 + ta_1 . Rearranging, we have a nonnegative integer \rho = 1-t so that n = \rho a_1 +\sigma a_2 . Indeed, \rho\ge 0 because \rho a_1 = n - \sigma a_2 \ge (a_1-1)(a_2-1) - (a_1 -1)a_2 = -a_1 + 1 > (-1)a_1 .

To show that exactly half of the integers 0, 1, \ldots, ab - a - b are representable as non-negative integer linear combinations, one first shows that if the integer k \in [0,ab-a-b] is representable, then N - k is not representable, where N = ab-a-b . One then shows that the converse is true as well: if k is not representable, then N-k is representable. To show this, use the fact that \gcd(a,b) = 1 , which allows us to write k = xa + yb .

Reducing and re-arranging the coefficients by adding multiples of ab as necessary, we can assume 0 \le x (in fact, this x is the unique such x satisfying the equation and inequalities). Similarly we take u, v satisfying N - k = ua + vb and 0 \le u . Now we can add these equations to write N = (u+x)a + (y+v)b which, using N = ab-a-b yields ab-b(1+y+v) = a(x+u+1) . The integer x+u+1 is positive, because x,u \ge 0 . In fact, since the left-hand side of ab-b(1+y+v) = a(x+u+1) is divisible by b , and (a,b)=1 , we must have that x+u+1 is divisible by b .

Yet x,u \le b-1 , so x+u+1 \le 2b-1 , so that x + u + 1 = b . Substituting this into ab-b(1+y+v) = a(x+u+1) and subtracting ab from both sides yields b(1+y+v)=0 . So 1+y+v = 0 . This implies that y+v = -1 , which means that exactly one of y or v is negative. If y is negative, then v \ge 0 , which means that N-k = ua + vb is representable; the case when v is negative entails that k is representable.

Thus for any non-negative integer k \in [0,ab-a-b] , we know that exactly one of k or (ab-a-b)-k is representable (and these are distinct, because ab-a-b must be odd as the integers a,b are relatively prime). This shows that half of the integers in the given range are representable; since there are (ab-a-b+1) = (a-1)(b-1) integers in the range [0,ab-a-b] , 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 f(a_1, a_2, a_3) \equiv g(a_1, a_2, a_3) + a_1 + a_2 + a_3 \geq \sqrt{3a_1a_2a_3} is relatively sharp.

( f here is the modified Frobenius number, which is the greatest integer not representable by positive integer linear combinations of a_1, a_2, a_3 .) The asymptotic average behaviour of f for three variables is also known as: f(a_1, a_2, a_3) \sim \frac8{\pi}\sqrt{a_1a_2a_3}, A simple formula exists for the Frobenius number of a set of integers in an arithmetic sequence.

Given integers a, d, w with gcd(a, d) = 1: g(a,a+d,a+2d,\dots,a+wd)=\left(\left\lfloor\frac{a-2}{w}\right\rfloor\right)a+d(a-1) The n=2 case above may be expressed as a special case of this formula. In the event that a > w^2-3w+1 , we can omit any subset of the elements a+2d, a+3d, ..., a+(w-3)d, a+(w-2)d from our arithmetic sequence and the formula for the Frobenius number remains the same. 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(m, n) = 1: g(m^k,m^{k-1}n,m^{k-2}n^2,\dots,n^k)=n^{k-1}(mn-m-n)+\frac{m^2(n-1)(m^{k-1}-n^{k-1})}{m-n}. A simpler formula that also displays symmetry between the variables is as follows. Given positive integers a,b,k , with \gcd(a,b)=1, let A_k(a,b) = \{a^k, a^{k-1}b, \ldots, b^k\} . Then g(A_k(a,b))={\sigma}_{k+1}(a,b) - {\sigma}_k(a,b) - (a^{k+1} + b^{k+1}), where {\sigma}_k(a,b) denotes the sum of all integers in A_k(a,b).

44 = 6 + 6 + 6 + 6 + 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 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 (with the exception of 3 itself); including a single box of 20 does not help, as the required remainder (23) 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. Since the introduction of the 4-piece Happy Meal–sized nugget boxes, the largest non–McNugget number is 11.

In countries where the 9-piece size is replaced with the 10-piece size, there is no largest non–McNugget number, as any odd number cannot be made. When a univariate polynomial is raised to some power, one may treat the exponents of the polynomial as a set of integers.

The expanded polynomial will contain powers of x greater than the Frobenius number for some exponent (when GCD=1), e.g., for (1 + x^6 + x^7)^n the set is {6, 7} which has a Frobenius number of 29, so a term with x^{29} will never appear for any value of n but some value of n will give terms having any power of x greater than 29.

When the GCD of the exponents is not 1, then powers larger than some value will only appear if they are a multiple of the GCD, e.g. for (1+x^9+x^{15})^n , powers of 24, 27,... will appear for some value(s) of n but never values larger than 24 that are not multiples of 3 (nor the smaller values, 1-8, 10-14, 16, 17, 19-23).

Further reading

describes algorithm built into Mathematica How to order 43 Chicken McNuggets – Numberphile

Text derived from https://en.wikipedia.org/w/index.php?oldid=1345552326 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

8 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.