Pilgrims, planes and postage stamps
17th Century navigation problems
In 1620, a little before Sir Isaac Newton's time, the Pilgrim Fathers sailed for Virginia, but, due to poor navigation, ended up in Massachusetts some hundreds of miles away! Sir Isaac, although Master of the Mint, was in fact more like the equivalent of Government Chief Scientist and so he was asked about the important practical problem of longitude measurement. However it wasn't fully solved in a way sailors could use at sea for some 150 years, when accurate chronometers became available.
The Mayflower in Plymouth Harbour by Halsall. (Source: Pilgrim Hall Museum).
This was an exciting time when new problems were being thrown up by exploration and invention, and mathematicians were doing their best to produce methods to explain and solve them. Unfortunately practical problems do not always have a neat and tidy mathematical solution, so real world users, sailors, builders, engineers and the like, have to do the best they can.
In the case of the navigational problems mentioned above, latitude was easy to measure from the pole star. Thus, an interim solution was to find a recognisable bit of land at the right longitude, and then sail north or south to the right latitude.
Present day Problems
The situation is similar today since after centuries of regarding calculating as mere accountancy, pure mathematics is accepting numerical methods as having an important role where classical analysis fails to solve many important problems.
As W W Sawyer points out in Mathematician's Delight, the "cultivated areas" of pure mathematics are mainly marked out by the wooden ploughs of pre 1950 mathematics, but there is still much important land awaiting the exploitation by steel ploughs of other methods. Although his expectations of development in non-linear mathematical methods were realised, notably by chaos theory, much progress is also being made by the application of number crunching.
In dealing with practical problems it is important to attack the right problem and not get locked into elegant mathematics for its own sake. Often a solution involves breaking down the problem into simpler sections which can be solved, and sticking these together, like the longitude solution.
In one more modern case, including "calculation" in the problem definition hindered its solution. In 1940 there was a need to locate German night bombers sufficiently accurately for Anti Aircraft fire. It was realised that with accurate values of range from three radars at known positions (R1, R2 & R 3 in the diagram) the position was fully defined in 3D, and did not depend on the, rather poor, angular information available from the radars at that time.
Three radar stations can give accurate range information, compensating for their poor directional information.
The first attempt at a solution was to calculate the position in real time. In 1940 this meant hand calculation which produced a solution in about half an hour, by which time the bomber had dropped its bombs and was 100 miles away!
The second attempt was to pre-calculate all the solutions and use a look up table. This ended up occupying two large rooms full of filing cabinets. With luck the answer could be found in half an hour, by which time...
Heinkel HE-111 German Blitz Bomber. (Copyright: Felts Field Aviation, Inc).
The working solution was to avoid calculation as such, but to have a scale map of the area with a graduated string extending from each radar location. When pulled out to the lengths corresponding to the radar ranges these met at a point defining the target location, which was then measured.
The first two attempts were unsuccessful due to focusing on "calculating", in other words plugging numbers into a general analytic solution, rather than finding the particular solution somehow and then extracting numbers. Strictly of course there are two solutions, one up in the air and the other below the level of the radar stations. Anyone who could not tell the difference was not trusted near an anti-aircraft gun!
The stamp problem
It is difficult to find interesting examples of this sort which are simple enough to be solved in a reasonable time without specialised experience and yet don't descend to contrived problems. The following is a simple real problem, from a small business, which cannot be solved analytically but yields to the number crunching attack. It can also be solved using the very simple procedures typical of computer programming exercises, thus indicating these do have some real use after all!
Postage stamps come in a limited range of denominations. However, the cost of sending a parcel can range freely depending on its destination and weight. The basic problem is therefore how to make up these odd amounts from a fixed range of commonly available stamps.
UK first and second class stamps from the 1997 collection "Architects of the air".
The three most common stamps are the UK first class, UK second class and minimum overseas denominations. At the time of writing these are 26p, 20p and 30p respectively. We add a further practical constraint that no more than six stamps can be used on any one envelope. For a particular case there may be no exact solution, in which case the nearest above has to be used. These are practical constraints, which can easily be fitted into a numerical solution.
The algorithm
The algorithm chosen was as follows:-
- Input the three denominations stocked.
- Calculate the value of all possible combinations of stamps up to the maximum set by the number per envelope, storing the results in a table with the combinations responsible.
- Sort this table into value order.
- When a particular required value is input, the table is searched for this value, and the matching combination(s) printed out together (or the next higher one to cover the case of no exact solution). An alternative would be to print the whole sorted table on paper.
This algorithm was actually programmed in Pascal, chosen for the convenience of a compiled language and because the source code is closer to English than say C. It has run on an Amstrad PCW with adequate speed, as well as on PCs, since the run time is quite short due to using integers for arithmetic. Probably it would be acceptably fast on a programmable calculator, although selection of a fast sort method may then be important.
Further reading
"Mathematician's Delight" by W W Sawyer published by Penguin. A very readable and down to earth book on what mathematics is really about.
"Longitude: the true story of a lone genius who solved the greatest scientific problem of his time" by Dava Sobel published by Fourth Estate.
About the author
Barry Priestley is a systems engineer at Racal Radar Defence Systems.