Coin problem

A price of 3 cents cannot be paid with just 2 and 5 cent coins without change, but any higher price can.

The coin problem (also known as the Frobenius problem ) from the field of number theory asks which natural numbers can be written in the form , where up to are given relatively prime numbers and the coefficients up to should be chosen as natural numbers (including 0). More precisely, the question is asked about the largest number that cannot be written in this form; it is called the Frobenius number . ${\displaystyle m=x_{1}a_{1}+x_{2}a_{2}+\dots +x_{n}a_{n}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{n}}$

The problem goes back to Ferdinand Georg Frobenius , the name comes from the clear formulation of the question, which prices can be paid with a given set of coins with the values to . The event was James Joseph Sylvester in 1884 completely solve, for more numbers, however, it seems to be no simple formula. ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\displaystyle n=2}$

Related to this is the postage stamp problem .

background

If the numbers to are not prime but have a common factor , all numbers that can be written as are also divisible by. In this case, there cannot be a largest number that cannot be written in the desired form. ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\displaystyle d}$ ${\displaystyle m=x_{1}a_{1}+\dots +x_{n}a_{n}}$ ${\displaystyle d}$

If, on the other hand, the numbers to are coprime as required, then according to Bézout's lemma there is a representation with whole numbers to . If you multiply this equation , you get a representation for every natural number, but with whole coefficients instead of natural ones. However, if it is sufficiently large, all coefficients can be chosen as natural numbers. The question of how big must be is precisely the problem of coins. The largest number that can be written for given or not with non-negative coefficients is often referred to as and called the Frobenius number. ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\displaystyle 1=x_{1}a_{1}+\dots +x_{n}a_{n}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{n}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\displaystyle g(a_{1},\dots ,a_{n})}$

Set of New Years Eve

In the event the following Sylvester attributed theorem gives the answer: Are and two relatively prime natural numbers, it is the largest number that is not in the form of non-negative integers and can write . ${\displaystyle n=2}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m=xa+yb}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle m=g(a,b)=ab-a-b}$

The proof consists of two parts: on the one hand it has to be shown that all numbers can be written larger than in the desired form, on the other hand it has to be proven that there is no such representation. ${\displaystyle ab-a-b}$ ${\displaystyle ab-a-b}$

So be first . According to the preliminary remark, there are at least whole numbers and with . If you put and , there is also a representation. With a suitable choice of so can . B. o d. A. be accepted. The following applies to the associated : ${\displaystyle m>ab-a-b}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle m=xa+yb}$ ${\displaystyle x':=x+tb}$ ${\displaystyle y':=y-ta}$ ${\displaystyle m=x'a+y'b}$ ${\displaystyle t}$ ${\displaystyle 0\leq x<b}$ ${\displaystyle y}$

${\displaystyle yb=m-xa\geq ab-a-b+1-(b-1)a=-b+1>-b}$

Since is divisible by , it is therefore not negative , as desired. ${\displaystyle yb}$ ${\displaystyle b}$ ${\displaystyle yb\geq 0}$ ${\displaystyle y}$

The second part is a contradiction proof : If such a representation were, so would . The left side and the first summand on the right side are divisible by, so the second summand must also be a multiple of . Since and are relatively prime, a multiple of and as a positive number should be at least . It would be analogous that the right side would have at least the same size , which is a contradiction. Consequently, it can not be represented with non-negative coefficients. ${\displaystyle ab-a-b=xa+yb}$ ${\displaystyle ab=a(x+1)+b(y+1)}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle y+1}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle x+1\geq b}$ ${\displaystyle 2ab}$ ${\displaystyle m=ab-a-b}$

Representations with more than two numbers

There is no known formula for that produces the largest non-representable number, and it is likely that there is no closed formula either. Instead, there are a number of estimates, formulas for special cases and algorithms with different runtime behavior. ${\displaystyle n>2}$

Estimates

In this case , the estimate is known as the lower bound. ${\displaystyle n=3}$ ${\displaystyle g(a_{1},a_{2},a_{3})\geq {\sqrt {3a_{1}a_{2}a_{3}}}-a_{1}-a_{2}-a_{3}}$

Of Issai Schur estimate comes that provides an upper bound. ${\displaystyle g(a_{1},\dots ,a_{n})\leq \min(a_{i})\max(a_{i})-\min(a_{i})-\max(a_{i})}$

Special cases

For the case and , and with pairwise prime numbers , and holds . This was a task at the 1983 International Mathematical Olympiad . ${\displaystyle n=3}$ ${\displaystyle a_{1}=ab}$ ${\displaystyle a_{2}=bc}$ ${\displaystyle a_{3}=ac}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle g(a_{1},a_{2},a_{3})=2abc-ab-bc-ac}$

Also known is the Frobenius number for arithmetic and geometric sequences of any length. If and are coprime, then: ${\displaystyle a}$ ${\displaystyle d}$

${\displaystyle g(a,a+d,a+2d,\dots ,a+(n-1)d)=\left(\left\lfloor {\frac {a-2}{n-1}}\right\rfloor +1\right)a+(d-1)(a-1)-1}$

For coprime numbers and for the geometric sequence with quotient : ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle {\tfrac {p}{q}}}$

${\displaystyle g(q^{n-1},q^{n-2}p,q^{n-3}p^{2},\dots ,p^{n-1})=p^{n-2}(pq-p-q)+{\frac {(p-1)q^{2}(q^{n-2}-p^{n-2})}{q-p}}}$

Algorithms

Many algorithms for the coin problem are based on graphs . For this, the equation is modulo considered so . A weighted digraph is constructed on the knot , where there is an arc from the knot to the knot if and only if there is a ( ) with , the weight of the arc . It can be shown that the Frobenius number can be obtained by looking for the shortest path from 0 to for all nodes and determining the length of the longest of these paths. Then is the Frobenius number . With the help of the Dijkstra algorithm , the Frobenius number can thus be easily calculated. If you also use the special symmetry properties of the graph, you can develop faster algorithms. ${\displaystyle a_{1}}$ ${\displaystyle m\equiv x_{2}a_{2}+\dots +x_{n}a_{n}\mod a_{1}}$ ${\displaystyle 0,1,\dots ,a_{1}-1}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle a_{i}}$ ${\displaystyle 1<i\leq n}$ ${\displaystyle u+a_{i}\equiv v\mod a_{1}}$ ${\displaystyle a_{i}}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle D}$ ${\displaystyle D-a_{1}}$

Ravi Kannan developed an algorithm that calculates the Frobenius number for each fixed in polynomial time (based on to ). The general problem, that is, even if it is variable, is, however, NP-difficult . ${\displaystyle n}$ ${\displaystyle \log a_{1}}$ ${\displaystyle \log a_{n}}$ ${\displaystyle n}$

example

The graph for the McNugget problem. The blue arches weigh 9 each, the red 20 each.

A common example is the McNugget numbers. The question is how many Chicken McNuggets you can buy if you put them together from the classic packaging sizes of 6, 9 and 20 pieces. The estimates provide that . The exact number can be easily determined; the method with the aid of the graph is used here as an example. This one has six knots. The arcs that belong to the number 9 are shown in blue and divide the nodes into three pairs, the red arcs belong to the number 20 and form two groups of three. Overall, the graph is strongly connected because the numbers are relatively prime. The shortest paths from node 0 result (only one of several options is always given): ${\displaystyle {\sqrt {3\cdot 6\cdot 9\cdot 20}}-6-9-20\approx 19\leq g(6,9,20)\leq 94=6\cdot 20-6-20}$

• 0 → 2 → 4 → 1 (length ) ${\displaystyle 20+20+9=49}$
• 0 → 2 (length 20)
• 0 → 3 (length 9)
• 0 → 2 → 4 (length ) ${\displaystyle 20+20=40}$
• 0 → 2 → 5 (length ) ${\displaystyle 20+9=29}$

The longest of these paths has the length , hence the following applies . The graph also provides a possible representation for every number that can be represented. If you want about 47 Chicken McNuggets, you look for the shortest path from 0 to 5. This consists of a blue and a red arc, so you should first buy a pack of 9 and a pack of 20 Chicken McNuggets. For the remaining 18, take three 6-packs. ${\displaystyle D=49}$ ${\displaystyle g(6,9,20)=49-6=43}$ ${\displaystyle 47\equiv 5\mod 6}$

Individual evidence

1. ↑ Matthias Beck, Shelemyahu Zacks: Refined upper bounds for the linear Diophantine Problem of Frobenius. In: Advances in Applied Mathematics. Vol. 32, 2004. pp. 454-467. doi: 10.1016 / S0196-8858 (03) 00055-1
2. ↑ ^{a b} Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis, Stan Wagon: Faster algorithms for Frobenius numbers. In: Electronic Journal of Combinatorics. Vol 12, 2005. ( online )
3. ↑ 3. Task of the IMO 1983 ( online )
4. ^ Jorge Ramírez Alfonsín: The Diophantine Frobenius problem. Oxford University Press, 2005. pp. 59f.
5. ^ Darren C. Ong, Vadim Ponomarenko: The Frobenius Number of Geometric Sequences. In: INTEGERS: the Electronic Journal of Combinatorial Number Theory Vol. 8, 1, 2008. ( online )
6. ^ Ravi Kannan: Lattice translates of a polytope and the Frobenius problem. In: Combinatorica. Vol. 12, 2nd pp. 161-177. doi: 10.1007 / BF01204720

Web links

• Eric W. Weisstein : Coin Problem . In: MathWorld (English).