The Coin Problem for two denominations is a linear diophantine equation

where a_{1}, a_{2} and b are positive and a_{1} and a_{2} are unequal and have a gcd of one. The solutions are required to be non-negative integers.

It is called a coin problem because it can be likened to the problem ‘in how many ways can change of b dollars be made in coins of denomination a_{1} and a_{2} dollars?’

The largest b for which there is no solution is called the Frobenius number, and for the two denomination case the Frobenius number is a_{1}a_{2} – a_{1} – a_{2}. This result is attributed to James Joseph Sylvester and a proof follows.

The equation a_{1}x + a_{2}y = b has an integer solution if and only if the line representing it passes through a point in the real plane whose coordinates are integers. We call such a point an integer point. If p, q is any integer point it is obvious that since a_{1}p + a_{2}q is an integer that every integer point lies on a line of the form a_{1}p + a_{2}q = b, where b is some integer. It is not hard to show using analytical geometry that the lines for which b > 0 lie above and to the right of the line a_{1}x + a_{2}y = 0, with a line with greater b lying above and to the right of a line with lesser b. The solutions to the Frobenius equation are integer points lying in (or on the boundaries of) the upper right hand quadrant (see figure).

Since (a_{1}, a_{2}) = 1 then we know from the general solution of the binary linear diophantine equation (see previous post) that if x_{1}, y_{1} is some integer point on a_{1}x + a_{2}y = b, then so is x_{2} = x_{1} + a_{2}t, y_{2} = y_{1} – a_{1}t, for any integer t. The distance between these points is = t√(a_{1}^{2} + a_{2}^{2}), so the distance between two adjacent integer points on the line is √(a_{1}^{2} + a_{2}^{2}), and if x_{1} y_{1} is some point on the line, then x_{1} + a_{2}, y_{1} – a_{1} is the point immediately to its right.

Now consider the line a_{1}x + a_{2}y = a_{1}a_{2} – a_{1} – a_{2}. The points (-1, a_{1}-1) and (a_{2} – 1, -1) are adjacent integer points on this line, and since they lie outside the upper right hand quadrant there is no solution when b = a_{1}a_{2} – a_{1} – a_{2}, and the Frobenius number is greater than or equal to a_{1}a_{2} – a_{1} – a_{2}.

Now (0, a_{1}) and (a_{2}, 0) are adjacent integer points, and lie on the line a_{1}x + a_{2}y = a_{1}a_{2}. This line, and any line above and to the right of it has a segment of length at least √(a_{1}^{2} + a_{2}^{2}) lying in or on the boundaries of the upper right hand quadrant, and therefore must contain at least one integer point lying in or on this quadrant. Thus the Frobenius number is less than a_{1}a_{2}.

Finally, consider lines for which a_{1}a_{2} – a_{1} – a_{2} < b < a_{1}a_{2}. Each such line intersects the parallelogram defined by the points (0, a_{1}), (-1, a_{1}-1), (a_{2} – 1, -1) and (a_{2}, 0). It has a segment of length √(a_{1}^{2} + a_{2}^{2}) lying in, or on the edges of, the parallelogram and thus contain at least one integer point. However this integer point cannot be in or on the triangular segment of the parallelogram lying to the left of the y-axis (it may be on the y-axis), since the x-coordinates of all such points are greater than -1 and less than 0. Similarly it has no integer point in the triangular segment below the x-axis (but may have one on the x-axis). Thus the integer points must lie in or on the upper right hand quadrant, and thus each of the Frobenius equations for which a_{1}a_{2} – a_{1} – a_{2} < b < a_{1}a_{2} has a solution. Thus the Frobenius number is a_{1}a_{2} – a_{1} – a_{2}.

## Leave a Reply