Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Basic Algebra
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/