POLY007: Amount that cannot be paid in bills of m and n dollars (proposed by Luis Lopes, 11/14/01).
In a country, there are only two values for the bills: 7 and 11. What is the greatest amount that cannot be paid with those bills? The answer is 59. In trying to solve this problem, I came up with the following conjecture: Let m and n be positive integers without common divisors. The greatest amount that cannot be paid with bills of values m dollars and n dollars is mn-m-n dollars. Prove or disprove the conjecture.
Discussion. [FvL, 11/15/01]: This problem has been
subject of a talk in February this year to on the National Math teachers
Conference in the Netherlands. The talk was by Frits Beukers of Utrecht
University. He gave several names for the problem, among which "Frobenius
porblem". So we have a,b coprime. We claim:
(1): The largest n which cannot be written as n=ax+by
for x,y>=0 is n=ab-a-b.
Beuker's approach: He proves instead:
(2): The largest number n with n=ax+by for x,y>=1 is
n=ab.
This is clearly equivalent to (1).
There are clearly no numbers x,y>=1 with ab=ax+by, that
would contradict to a,b being coprime. Now let m>ab. We know that - using
the Euclidean algorithm - there integers p,q, possibly negative or zero
with m=ap+bq. Taking p'=p+kb and q'=q-ka for some integer k we can find
p',q' such that m=ap'+bq' and 1<=q'<=a. But then bq'<m and thus
ap'>0 ==> p'>=1. That proves (2) and consequently (1).
[SCL, 11/15/01]: I will ask a tougher question,
and give an old use for the original problem.
The tougher question is: if a_1, a_2, a_3, ...,
a_k are positive integers, with gcd 1, what is the largest integer which
is not the sum of a non-negative linear combination of the given integers?
As far as I know, that problem is unsolved for
k=3, except in special cases. I've had highschool students use the case
k=3 for a project for science fairs.
Now, the application. In Pratt's thesis on sorting, he
proves that one can do a version of the shell-sort that works in time O(n
log(n) log(n)). If a list x[1],x[2],...,x[q] is sorted so x[i]<=x[i+q],
wherever the indices make sense, call the list q-ordered. If a list which
is q-ordered is then r-sorted (say by a bubble-sort) so that now x[i]<=x[i+r]
for all appropriate i, then the list remains q-ordered.
Also, if a list is 2-ordered and 3-ordered, no element
is more than one position out of place, so one pass of a bubblesort will
put all elements in the correct place. Pratt's idea now is to successively
q-sort the given list, where q ranges over integers of the form (2^s)(3^t).
The q-sorts can be done in any order as long as one does the (2q)-sort
and the (3q)-sort before the q-sort.
The neat thing about Pratt's version is that it almost
instantly gives a parallel sort network with depth O(log(n) log(n)). [And,
yes, one can use expander graphs to get a better depth, but Pratt's method
is so simple that I still like it.]
[PY, 11/21/01]: Aad Goddijn of the Netherlands has just sent me the following: In the example Luis Lopes gives, with bills of 7 and 11, there are 30 amounts you cannot pay, of which 59 is the highest one. Now 30 = (7-1)(11-1)/2, so exactly halve of 0, 1, 2, ... , 59 are payable. And here is your general problem: With bills of m and n, (m,n)=1, how many amounts cannot be paid? The correct answer is indeed (m-1)(n-1)/2. There is still more structure in the set 0, 1, ..... , (m-1)(n-1)-1 related to 'payable or not payable'.
[SCL, 11/26/01]: Just for reference: Here is where I first came across this problem (in my first semester as an undergaduate). [Anybody who knows my score on that year's contest also knows I didn't solve very many questions.] On the 1971 Putnam, problem A-5 reads: "A game of solitaire is played as follows. After each play, according to the outcome, the player receives either $a$ or $b$ points ($a$ and $b$ are positive integers with $a$ greater than $b$), and his score acumulates from play to play. It has been noted that there are exactly thirty-five non-attainable scores and that one of these is 58. Find $a$ and $b$." My memory also says that this type of problem is related to Gauss's lemma (number theory). I don't have a reference for this if it is true.
[FR, 11/28/01]: This is sometimes called Sylvester's theorem or Sylvester's formula. A number of more famous theorems and formulas also go by these names. You can find references to it on the web; I couldn't find any in MathSciNet. I first ran across the terminology not too long ago when a referee suggested that we appeal to Sylvester's theorem in the course of some proof.
[PY: 11/28/01]: Now I see how the whole thing can be easily explained. If we begin with the original problem with 7 and 11, write the natural numbers in rows of elevens:
1 2
3 4 5 6 7
8 9 10 11
12 13 14 15 16 17
18 19 20 21 22
23
28
33
34 35
42 44
45
49
55
56
63 66
67
70
77
78
88
...
...
Highlight every amount that can be paid in sevens and
elevens. These obviously include the multiples of 7 and of 11. In particular,
this means that all the entries in the rightmost column are highlighted.
Clearly it is also true that if one number is highlighted, then so is every
number beneath it in the same column. Therefore, the largest unpayable
amount is 11 less than 77-7, namely, 59.
This also leads to an enumeration of the amounts not
payable: there are sum([7k/11], k=1,2,...10) of them. But this same sum
is exactly what we see in Gauss' proof of the law of quadratic reciprocity.
It is the number of lattice points inside and underneath the diagonal of
the 7 by 11 rectangle.
This clearly extends to relatively prime numbers m and
n in place of 7 and 11.
[LZ, 12/3/01]: I believed that you could find help for any elementary problem in Arthur Engel's "Problem-Solving Bible", and I was right. Check out Problem 145 (page 136) and it's solution (page 156). By the way, the book is on Yellow Sale now, so there's no excuse for not owning it.
Bibliography. [1] A.Engel, Problem-Solving Strategies, Springer, 1998.
Return to [Polya
Home Page] [Members]
[Problem Center]
[Inventory]
[Reserve Area]