The Coin Problem for two denominations

The Coin Problem for two denominations is a linear diophantine equation

a_{1}x_{1}+a_{2}x_{2}=b

where a1, a2 and b are positive and a1 and a2 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 a1 and a2 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 a1a2 – a1 – a2. This result is attributed to James Joseph Sylvester and a proof follows.

The equation a1x + a2y = 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 a1p + a2q is an integer that every integer point lies on a line of the form a1p + a2q = 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 a1x + a2y = 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 (a1, a2) = 1 then we know from the general solution of the binary linear diophantine equation (see previous post) that if x1, y1 is some integer point on a1x + a2y = b, then so is x2 = x1 + a2t, y2 = y1 – a1t, for any integer t. The distance between these points is = t√(a12 + a22), so the distance between two adjacent integer points on the line is √(a12 + a22), and if x1 y1 is some point on the line, then x1 + a2, y1 – a1 is the point immediately to its right.

Now consider the line a1x + a2y = a1a2 – a1 – a2. The points (-1, a1-1) and (a2 – 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 = a1a2 – a1 – a2, and the Frobenius number is greater than or equal to a1a2 – a1 – a2.

Now (0, a1) and (a2, 0) are adjacent integer points, and lie on the line a1x + a2y = a1a2. This line, and any line above and to the right of it has a segment of  length at least √(a12 + a22) 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 a1a2.

Finally, consider lines for which a1a2 – a1 – a2 < b < a1a2. Each such line intersects the parallelogram defined by the points (0, a1), (-1, a1-1), (a2 – 1, -1) and (a2, 0).  It has a segment of length √(a12 + a22) 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 a1a2 – a1 – a2 < b < a1a2 has a solution. Thus the Frobenius number is a1a2 – a1 – a2.

Advertisements

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