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<a_1<a_2<...<a_n 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.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: