Home > Number theory, Problem Solving > Frobenius Coin Problem

Frobenius Coin Problem

I encountered a problem in the past few days which sounded like this:

What is the largest weight which cannot be obtained by using weights of 6, 10 and 15 units only?

This is a special case for a more general problem, namely, the Frobenius Coin Problem. This states that given $n$ types of coins having integer values $1 with $\gcd(a_1,a_2,...,a_n)=1$, which is the greatest sum of money that cannot be obtained by using the above type of coins. This number is denoted by $g(a_1,a_2,...,a_n)$.

The case $n=2$ is easy. The formula is $g(a,b)=ab-a-b$. For the case $n\geq 3$ we cannot find such a closed form for $g$. There exist some interesting algorithms, although, and a few theorems that can help us.

Theorem 1. If $a_1,a_2,a_3$ are relatively prime and $\gcd(a_1,a_2)=d$ then

$g(a_1,a_2,a_3)=d g(\frac{a_1}{d},\frac{a_2}{d},a_3)+(d-1)a_3$.

Note that if $a_3 > g(\frac{a_1}{d},\frac{a_2}{d})$ then $g(a_1,a_2,a_3)=d(a_1a_2-a_1-a_2)+(d-1)a_3$.

Theorem 2. Let $\gcd(a_1,a_2)=d$, $a_1=a_1'd,\ a_2=a_2'd$ such that there exist integers $x_1,x_2 \geq 0$ with $a_3=x_1a_1'+x_2a_2'$.  Then

$g(a_1,a_2,a_3)=\displaystyle\frac{a_1a_2}{d}-a_1-a_2+(d-1)a_3$.

For references and proofs see for example this book.
With each of the above formulas we get that $g(6,10,15)=29$.