Sylvester's Problem
James Joseph Sylvester was one the greatest British mathematicians of the 19th century. He was known for his absentmindedness and poor memory; on one occasion he even denied the truth of one of his own theorems. Still, he never forgot his origins. E.g., he was precluded from obtaining a Cambridge degree because it required to state his allegiance to the Church of England which he - being Jewish - refused to do.
In 1884 Sylvester submitted to the Educational Times the following problem:
A man possess a large quantity of stamps of only two denominations:

|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
A man possess a large quantity of stamps of only two denominations:
Solution
Let's do something more general and solve the following problem:
Let p and q be two mutually prime integers greater than 1. What is the largest number that could not be expressed as a linear combination
To solve the latter, form a family of arithmetic sequences:
f0 = {0 + 0, 0 + q, 0 + 2q, 0 + 3q, ...}
f1 = {p + 0, p + q, p + 2q, p + 3q, ...}
f2 = {2p + 0, 2p + q, 2p + 2q, 2p + 3q, ...}
f3 = {3p + 0, 3p + q, 3p + 2q, 3p + 3q, ...}
...
fq-1 = {(q-1)p + 0, (q-1)p + q, (q-1)p + 2q, (q-1)p + 3q, ...}.
There is no need in the "next" progression fqp as it would be a subsequence of the very first sequence. Other than that, the above q sequences have no common terms.
The terms in fk, 0 ≤ k < q have the property of sharing a residue modulo q, viz.,
Indeed, had the sequences started with the corresponding residues, their union would have covered the entire set of non-zero integers. Since each fk started with a number kp which is not less than
First off, A(p, q) does not belong to the union of the sequences. If it were, we would have
On the other hand, all sequences fk start at or below
Returning to Sylvester's problem which corresponds to, say, p = 5 and q = 17, the answer is
Note: A more formal proof could be found in [Petcović, pp. 60-64]. The book also delves into the McNuggets problem, which is to determine the largest number of nuggets that cannot be delivered using McDonald's standard boxes of 6, 9 and 20 nuggets. Problems of this kind are known as
References
- M. S. Petcović, Famous Puzzles of Great Mathematicians, American Mathematical Society, 2009
- A. Levitin and M. Levitin, Algorithmic Puzzles, Oxford University Press, 2012


|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72256962