Mathematical puzzles that involve postage stamps have been around almost as long as postage stamps themselves, the first of which, the Penny Black, was issued by Great Britain on 6 May 1840. Some such puzzles ask what postage amounts can or can't be made with stamps of certain values. Others are based on the ways that a block of stamps can be folded or torn along the perforations. One of this type appears as problem no. 285 in Henry Dudeney's Amusements in Mathematics (1917). It starts by saying you have just bought 12 stamps in a rectangular block of three rows with four stamps in each. (In Dudeney's diagram, they are labeled 1, 2, 3, 4 across the top row, and so on.) He goes on: "[A] friend asks you to oblige him with four stamps, all joined together – no stamp hanging on by a mere corner. In how many different ways is it possible for you to tear off those four stamps? You see, you can give him 1, 2, 3, 4, or 2, 3, 6, 7, ... , and so on. Can you count the number of different ways in which those four stamps might be delivered?" This can be thought of as a problem involving tetrominoes, which are a type of polyomino. (Solution below.)

 

The Postage Stamp Problem, also known as the Frobenius problem, is a long-standing challenge in number theory and in computer science. Suppose a country issues n different denominations of stamps but allows no more than m stamps to be put on a single letter. The Postage Stamp Problem is to write and implement an algorithm (a stepwise set of rules) that, for any given values of m and n, computes the greatest consecutive range of postage values, from one on up, and all possible sets of denominations that realize that range. For example, for n = 4 and m = 5, the stamps with values (1, 4, 12, 21) allow the postage values 1 through 71. If the values of the stamps is constant and not part of the input, algorithms can be, and have been, devised that give a short-cut solution. However, in the general case where the number of stamp values is part of the input, the Postage Stamp Problem has been shown to be an NP-hard problem, and thus not susceptible to an efficient algorithmic approach.

 

Solution to Dudeney's postage stamps problem

Dudeney gives the solution to his "The Four Postage Stamps" problem as follows: "[T]he four stamps may be given in the shape 1, 2, 3, 4, in three ways; in the shape 1, 2, 5, 6, in six ways; in the shape 1, 2, 3, 5, or 1, 2, 3, 7, or 1, 5, 6, 7, or 3, 5, 6, 7, in twenty-eight ways; in shape 1, 2, 3, 6, or 2, 5, 6, 7, in fourteen ways; in shape 1, 2, 6, 7, or 2, 3, 5, 6, or 1, 5, 6, 10, or 2, 5, 6, 9, in fourteen ways. Thus there are sixty-five ways in all.