Frobenius number

[MattcAnderson]

Today I learned,

about the 'coin problem'.
"With only a 2 pence and 5 pence coins, one cannot make 3 pence, but one can make any higher integral amount.

Very interesting

Similarly, with only an unlimited number of 2 pence ant 10 pence coins, you can only make positive even amounts of pence amounts. So there is no Frobenius number for the set (2,10) and GCD(2,10) = 2.

If (greatest common divisor) GCD(x,y) = 1 then there will be a Frobenius number , that is an amount for which any higher integral amount is possible.

For chicken McNuggets in quantities of 9 and 20, the Frobenius number is 151.

generally, this is my notation, Frobenius(a,b) = a*b - a - b.

Now I cite sources before I get something wrong.

Wikipedia Coin_problem

and another link from Art of Problem Solving Online

Chicken McNugget Theorem

enjoy

Matt

[a1call]

[Dr Sardonicus]

The Frobenius or coin problem is tantalizing because it has a closed-form solution for two variables - if gcd(a,b) = 1 the largest non-representable number is

a*b - a - b.

For a = 9, b = 20, this evaluates to 151.

For more than two variables, there is no such formula. For three variables, however, there is an efficient computational method. The fact that this and other results about the problem were published in the prestigious Journal für die reine und angewandte Mathematik (AKA Crelle's Journal) is IMO some indication of their significance.

[a1call]

An interesting question for me is if for the 2 coprime varieties (neither bring 1), all solutions are unique or not.
I assume the answer is yes and a counter example if present should be easy to find.

ETA Perhaps more interesting would be the uniqueness of solutions for the all coprime more than 2 varieties (non being 1).

ETA II - In either case a multiple coin variety could be the basis for a Pomder-this style puzzle.

[a1call]

Of course what I failed to realize that if set of coins a & b has a unique solution and b & c another sand a & c yet another, then the more than 2 coins variations can't be unique unless the total value is beyond the minimum for one pair and below the minimum for the other 2 pairs.

ETA: Unless that is, you are obliged to use at least on of each type of coins.

So there are plenty of potential solutions for each pair:


PARI=GP Code:

theTotal =95
coin1 =2
coin2 =3
for(i=1,theTotal \coin1 ,{
    for(j=1,theTotal \coin2,
        if(i*coin1 +j*coin2 ==theTotal ,
            print("**** ",theTotal ," = ",i,"*",coin1," + ",j, " * ",coin2);
        );
    );
})

**** 95 = 1*2 + 31 * 3
**** 95 = 4*2 + 29 * 3
**** 95 = 7*2 + 27 * 3
**** 95 = 10*2 + 25 * 3
**** 95 = 13*2 + 23 * 3
**** 95 = 16*2 + 21 * 3
**** 95 = 19*2 + 19 * 3
**** 95 = 22*2 + 17 * 3
**** 95 = 25*2 + 15 * 3
**** 95 = 28*2 + 13 * 3
**** 95 = 31*2 + 11 * 3
**** 95 = 34*2 + 9 * 3
**** 95 = 37*2 + 7 * 3
**** 95 = 40*2 + 5 * 3
**** 95 = 43*2 + 3 * 3
**** 95 = 46*2 + 1 * 3

[MattcAnderson]

Thank you a1call and Dr.Sardonicus for your enthusiastic and helpful comments.

Another example of a two coin problem would be with
a=3 pence and
b=4 pence.

Then

since Frobenius(a,b) = a*b - a - b,
we have

Frobenius(3,4) = 3*4 - 3 - 4
so
Frobenius(3,4) = 12 - 7
finally
Frobenius(3,4) = 5 pence

This means, with only 3 pence coins and 4 pence coins,
You cannot produce a 5 pence amount.
However, you can produce amounts in {6, 7, 8, ...}.

Frobenius is sure of this.

This is a unique solution.

Good fun.
Matt

[MattcAnderson]

Hi again all,

I haven’t read any references about Frobenius numbers.

But here is my thought. Suppose you have two coins, and the value of one is an integer multiple of the other. Then the possible values of money is just the multiples of the smaller coin value.

For example, if there were a kingdom with two pence and eight pence coins, and no others, then only even amounts of pence could be given as change. And more, every even value of pence could be produced given an infinite supply of these two coins.

I believe I am right

Matt