Lowest Integer That Can't Be Made
Date: 04/05/2004 at 11:49:41 From: Mary Subject: algebra You have an unlimited number of 'a' cent stamps and 'b' cent stamps. With them, you will be able to make many different postages. Both a and b are relatively prime positive integers. I am interested in finding a cutoff point, that is, a postage value above which any postage amount can be made. I need to find a formula involving a and b, that will give the cutoff point for any such pair of numbers a and b.
Date: 04/06/2004 at 09:39:46 From: Doctor Rob Subject: Re: algebra Thanks for writing to Ask Dr. Math! I like to look at this problem like this. I'll use a = 5, b = 8, as an example. Assume that b > a. Arrange the numbers from 0 upwards in an array with b columns, in order like reading a book. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 .... If you can make an amount of postage in this array, then you can make all the amounts below it in the same column by adding one or more b-cent stamps. For example, if you can make 10 cents with two 5-cent stamps, you can make 18, 26, 34, 42, and 50 by adding 1, 2, 3, 4, or 5 8-cent stamps. Now start with the column headed by 0. You can make 0 cents postage by taking no stamps of either kind. Thus every number in that column can be made. Now move 'a' columns to the right. You can make 'a' cents with 1 a-cent stamp. Thus every number in that column from 'a' downwards can be made. Now move 'a' columns to the right again, wrapping around if necessary. You can make 2*a cents with two a-cent stamps. Thus every number in that column from 2*a downwards can be made. In the example, all of the column headed by 0 can be made, all of the column headed by 5 can be made, and all of the column headed by 2 from 10 downwards can be made (but not 2 itself). Continue dealing with columns in this way. Since a and b are relatively prime, you will eventually visit every column. The last column to be visited will be the one containing (b - 1)*a, which is headed by b - a. In the example, you'll visit the columns in this order: 0, 5, 2, 7, 4, 1, 6, and 3. In that last column, you'll be able to make postage for all money totals from (b - 1)*a downwards, using (b - 1) a-cent stamps and some number of b-cent stamps. The largest amount of postage which cannot be made is the number just above (b - 1)*a, namely (b - 1)*a - b, or a*b - a - b or (a - 1)*(b - 1) - 1. Thus every amount of postage from (a - 1)*(b - 1) on can be made from a-cent and b-cent stamps. In the example, the last column is the one headed by 3. You can make all numbers from (8 - 1)*5 = 40 - 5 = 35 downwards, but not 40 - 5 - 8 = 27. So all numbers from 28 = (8 - 1)*(5 - 1) upwards can be made. Thus your "cutoff point" is (a - 1)*(b - 1). In my example, it's 28. X 1 2 3 4 X 6 7 X 9 XX 11 12 XX 14 XX XX 17 XX 19 XX XX 22 XX XX XX XX 27 XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX .... Feel free to reply if I can help further with this question. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.