Using only 4$ and 7$ bills, you could pay any integer number of dollars, greater than 17.
Prove it.

Given two coprime numbers a and b, what is the minimal number M(a,b) such that any amount greater or equal to M(a,b) can be expressed as p*a+q*b (p & q non-negative integers)?

How much is M(37,38)?

(In reply to Can you prove it? by Jer)

I don't know if this proof is nice or not, but here's a more detailed explanation.

Consider a and b, relatively prime, a < b. In this problem, a = 4, b = 7.

Now consider what multiple of b is equal to i mod a for each possible i in the range [1, a-1]. Why? Because we know that we can make any value = i mod a higher than this simply by taking the "magic" number of b's to get the right modulus and adding however many a's we need to make up the difference. Also, we know that no smaller numbers = i mod a can be solved since no smaller number of b's create that mod and no number of a's can alter the remainder mod a. And finally, we exclude i = 0 because these numbers are trivially made by just using a's and have no exclusions.

So we want to solve equations like bx = i mod a and get a set of {x} values that correspond to the a-1 {i} values. Now, no x can be zero since i is never zero. Also, two different values of i cannot produce the same value of x -- the LHS would be the same in both cases but the RHS would differ mod a. That means there are a-1 different values in the set of {x}, and that the range of values in {x} is from 1 to a-1 (mod a). Since there are a-1 distinct values between 1 and a-1, ALL of the values from 1 to a-1 are present. And that means the largest of these is a-1.

That in turn means that one number at which you can say for sure that all future values can be made is b*(a-1). It may not be the smallest, such number, though. For example, in the concrete problem, b*(a-1) is 21 and indeed all numbers >= 21 can be expressed, but 20 can also be expressed (it's a multiple of 4) and so can 19 (7 + 3*4) and so can 18 (7*2 + 4).

What we really want is the *largest* number that you *can't* make. But we know that too. It's just 'a' less than our current non-minimal solution, namely b*(a-1) - a. This is the largest "failure" number, and so the next integer higher is the smallest number across all moduli at which all higher numbers are solvable. One more than b*(a-1) - a is b*(a-1) - a + 1 = ab - b - a + 1 = (a-1)*(b-1)

Posted by Paul on 2013-05-02 15:13:03