The Frobenius Coin Problem. Consider the equation ax + by = c where a, b, c, x,

Question

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 N2 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:

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

Explanation / Answer

Let c= ab-a-b
whereas c in general is = ax + by
ax + by = ab-a-b
This comes by assuming that there exists a pair (x,y) that satisfies this.
In this acse two cases arise
1) x<b
2) x>=b
Case 1: x<b
since x<b we can say that ax<ab
ax < ab and hence ax-ab<0
ax + by =c
ax+by=ab-a-b
ab-ax= (a+b+by)
a(b-x) = by+a+b
since x<b , ax-ab is negative. Which means
-(a+b+by) is negative so
a+b+by has to be positive.


Case 2: x>=b
ax>= ab
so adding anything non negative to ax will only increase its value and the inequality will still hold true, only that the scope of equal to case will be elimiated. .
ax + by> ab
Now deducting anythng positive from RHS will still hold the inequality true as ab is already less than ax+by
ax + by >ab-a-b
c>ab-a-b (which means that c cannot be = ab-a-b)


Thus we have seen that in both cases c=ab-a-b is not (a,b) - representable

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.