A and B are two positive integers such that:

1. The number 59 can be made by adding non-negative integral multiples of A and B in exactly one way.

2. Some numbers below 59 cannot be produced in this way at all, while some can be produced in one way and others in more than one way as sums of non-negative integral multiples of A and B.

3. All numbers above 59 can be produced in more than one way as sums of non-negative integral multiples of A and B.

What two numbers can A and B be?

A well known rule (I think it is on this site somewhere) is that if A and B are relative primes then the expression AB - A - B gives the greatest number that cannot be expressed as the sum of multiples of A and B.

Now AB is the first number that can be done in TWO ways, A copies of B or B copies of A.
Every number from 0 to AB-1 can be dome in some number of ways.  Every number from AB and above can be done on one more way than itself minus AB.

So if we want the largest number that can be done in one way we want to take the largest number that can be done in no ways: AB-A-B and add AB to it.

This yields 2AB-A-B = 59
or A = (B+59)/(2B-1)

Whose integer solutions (A,B) are
(60,1), (9,4), (4,9), and (1,60)

Posted by Jer on 2011-08-21 01:28:14