# postage stamp problems

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 May 6, 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.