The Frobenius Coin Problem Consider the equation ax by c w

The Frobenius Coin Problem. Consider the equation ax + by = c where a, b, c, x, y are natural numbers. We can think of $a and $b as two denominations of coins and $c as some value that we want to pay. The equation has a solution (x, y)  are elements of N² if and only if we can make change for $c, and in this case we say that c is (a, b)-representable. More generally, we will consider the set of (a, b)-representations of c:

R_a,b,c := {(x, y) are elements of N² : ax + by = c}. The problem is trivial when ab = 0 so we will always assume that a and b are both nonzero.

Solution

In general, we have k 2 coins p1, . . . , pk such that 2 p1 < p2 < · · · < pk and gcd(p1, . . . , pk) = 1.

The problem is to figure out which natural numbers n can be expressed as linear combinations of p1, . . . , pk with nonnegative integer coefficients, that is, n = i1p1 + · · · + ikpk, with i1, . . . , ik N.

Note that if we allow the ij to be negative integers, then by B´ezout, every integer n Z is representable in the above form.

The restriction to nonnegative coefficients ij makes the problem a lot more challenging. In the case of two coins p, q (with 2 p < q and gcd(p, q) = 1), it can be shown that every integer n (p 1)(q 1) is representable with nonnegative coefficients, and that pqpq = (p1)(q1)1 is the largest integer that can’t be represented with nonnegative coefficients.

For n between 1 and ab1 and not divisible by a or b, exactly one of n and abn is representable.

There are ab a b + 1 = (a 1)(b 1) integers between 1 and ab 1 that are not divisible by a or b.

Finally, we note that p{a,b}(n) > 0 if n is a multiple of a or b, by the very definition of p{a,b}(n).

Hence the number of nonrepresentable integers is 1/2 (a1)(b1).

The number pq p q, usually denoted by g(p, q), is known as the Frobenius number of the set {p, q}.