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: 5-cent stamps and 17-cent stamps. What is the largest (finite) amount of cents which the man cannot make up with a combination of these stamps?

Solution

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

A man possess a large quantity of stamps of only two denominations: 5-cent stamps and 17-cent stamps. What is the largest (finite) amount of cents which the man cannot make up with a combination of these stamps?

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 ap + bq, with non-negative integers a and b?

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., kp (mod q). Since q and p are mutually prime, the set {kp (mod q): 0 ≤ k < q} of all such residues coincides with the segment of integers {k: 0 ≤ k < q}. This is a crucial observation.

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 kp (mod q), the union of all the sequences has gaps at the beginning. The question is to find the largest number missing from that union. I am going to show that A(p, q) = (q - 1)p - q = pq - p - q is that number.

First off, A(p, q) does not belong to the union of the sequences. If it were, we would have A(p, q) = ap + bq, with 0 < a ≤ q-1 and 0 < b. But then q(p - 1 + b) = (a + 1)p would hold, implying (since p and q are mutually prime) that (a + 1)|q, so that (a + 1) = q. We thus would have A(p, q) = ap + bq > (q - 1)p which is false.

On the other hand, all sequences fk start at or below (q - 1)p. Some may start above A(p, q) = (q - 1)p - q, some may start below that. Since their terms increase by q, sequences of the latter kind are abound to have a term between A(p, q) and (q - 1)p. It follows that any integer between these two numbers belongs to the union of the sequences. But once the union of the arithmetic sequences with q as the common difference, contains an integer segment of length q, it contains all the integers above that segment.

Returning to Sylvester's problem which corresponds to, say, p = 5 and q = 17, the answer is A(5, 17) = 85 - 5 - 17 = 63. (Another solution based on generating functions could be found on a separate page.)

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 Frobenius' problems and their answer as a Frobenius number (corresponding to the parameters of the problem.) Sylvester's A(p, q) is a Frobenius number with two parameters. For three or more parameters, a general form of the Frobenius numbers is not known. Petcović gives a solution for the above McNuggets problem. [Levitins, pp. 44, 75, 120] solve the problem for four boxes of sizes 4, 6, 9, 20.

References

  1. M. S. Petcović, Famous Puzzles of Great Mathematicians, American Mathematical Society, 2009
  2. A. Levitin and M. Levitin, Algorithmic Puzzles, Oxford University Press, 2012

Related material
Read more...

  • Diophantine Equations
  • Finicky Diophantine Equations
  • Diophantine Quadratic Equation in Three Variables
  • An Equation in Reciprocals
  • A Short Equation in Reciprocals
  • Minus One But What a Difference
  • Two-Parameter Solutions to Three Almost Fermat Equations
  • Chinese Remainder Theorem
  • Step into the Elliptic Realm
  • Fermat's Like Equation
  • Sylvester's Problem, A Second Look
  • Negative Coconuts
  • |Contact| |Front page| |Contents| |Algebra| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62018439

    Search by google: