The Maths of Sorting Things Out

 

The Maths of Sorting Things Out

 

John D. Barrow
Gresham Professor of Geometry

 

The point of today's talk is really trying to understand problems which seem rather simple - how to pack your luggage, how to pack music tracks onto a CD most effectively, how to figure out what is the best type of set of denominations that you might need for a coinage, or what denominations for stamps.  These are very simply posed problems, which turn out to be perplexingly complicated, too complicated for computers to get very far with, and I hope, by the end of the lecture, you will have some appreciation for these sorts of counting and sorting problems.

Complexity, whether it is in traffic systems, in your mail service or trying to organise a timetable for National Rail services or something of that sort, you can see that it is clearly possible to transform whether it is - positions or traffic flows and so forth - into numbers, and so arriving at a solution which optimises something - that produces good organisation, uses space and time in the best possible way - turns out to be a numerical problem; a counting problem with some added aspect of optimisation added into it.

To first of all give you a flavour for how rather simply posed problems can turn out to be alarmingly difficult, here is a famous conjecture in arithmetic.

        Every even number can be written as the sum of 2 prime numbers

It carries the name of Christian Goldbach, who first posed it in a letter to the great Leonhard Euler in 1742, and he believed, because he had carried out many trials and he could not find a counter-example, that every even number bigger than two can be written as the sum of two prime numbers.  So 8 is 3 + 5, 12 is 5 + 7, and so on.  No one has ever proved this to be true for all possible choices of even number and no one has ever found a counter-example.  A few years ago, there was a novel about this conjecture, published by Faber & Faber, and they were offering a £1 million prize for anyone who came up with a proof in the next year that was agreed by some panel of mathematicians.  Well, nobody did.

What do we know about this little problem?  We know, by computer search, that it is true for all the even numbers up to 6 x 1016.  That is not that big a number - you are only looking at 16-digits.  There are a lot of bigger numbers between there and infinity.  But the biggest number they've tested the Goldbach conjecture against so far is this:

        389965026819938
        = 5569 + 389965026814369

You can see that on the scale of things that computers usually attack, this does not look really very impressive at all, but to arrive at this it took a couple of years of computing time.  The reason for the difficulty is that you are looking at all possible ways of adding two numbers together to make this number, and then you have got to check that the two candidate numbers are primes.  So there is a lot of complicated operations to carry out there, so there are a lot of false combinations to rule out.

One of the developments that has happened in mathematics since the early 1970s is the use of computers in new ways.  So we now use computers not just to add up columns of numbers and carry out long and tedious calculations, which we would be able to do if we had the time and if we could do it reliably enough, but computers have become involved in carrying out the operation of proof and doing algebra and doing integrals, so doing things that traditionally mathematicians alone did.  Also, they are useful for carrying out investigations.  If you have a set of rules of a complicated game, you could not from those rules, generally, predict all the types of game that could take place, and a good way of proceeding to understand the game would be to get the computer to play a great many games and begin to understand what the possible outcomes look like.  The study of chaos and complexity and many other topics where you cannot solve what is going on with pencil and paper because it is too complicated, involve doing this type of experimental mathematics, so getting a feel for the landscape of possibilities on a computer is useful for you to narrow down on what the conjectures might be that you might want to prove.

Many people think that there is probably nothing beyond the reach of computers, that you could do everything with a computer, but we know that it is really rather easy to defeat a computer with one of these complicated problems.

A famous problem, which produced a lot of controversy because it was the first use of a computer to do something which previously humans did, was this famous Four-Colour Conjecture, which turned into the Four-Colour Theorem in 1972.  This is an old problem, whereby you are asked to colour in a map of different regions, using as few colours as possible so that no two regions of the same colour touch one another.  The question is: what is the smallest number of colours which will do this trick for you?

Everyone had always believed that it was four, because you could do examples and you could never find a counter-example, but there was no proof that four always sufficed.  In 1972, a proof was arrived at, but it was arrived at in a rather unusual way.  It was a computer-aided proof, where two mathematicians arrived at a proof which would be true so long as some very large number of particular types of map could be checked one by one that they were not counter-examples.  They used the computer to do that checking of some vast number of possibilities, and so the computer carried out the check and found no counter-example in this vast collection of possibilities, and the theorem was announced as proved.  But the proof had never passed through a single human being's mind, so it was computer-aided.

This famous problem is not unique in that respect.  It shares with many complicated problems a structure which one might define as intractability.  By classifying problems into two sorts - you can go a lot further if you wish and sub-divide them further - but 'easy' problems are problems which, when you add extra bits to them, the amount of calculating that you or the computer has to do increases in proportion to the number of bits that you have in the problem.  So if you have got 100 sources of income to account for in your tax return, it will probably take you 100 times longer to complete it than if you just have one source of income, so this is a simple problem in this sense.  So the complexity - the calculating time to deal with it - here just grows in proportion to the number of bits that you add to it.

There are many simple experiences and problems which are not like this.  So, if you have one child, then the difference between having one child and having ten children is not just a factor of ten in complexity.  It might be in the amount of food you have to buy, but in other respects, it is not just a factor of ten. 

Hard problems are different, so they rapidly get out of hand, because each time you add another bit to the problem, the amount of calculating you have to do doubles, so each time you add another ingredient, the computer time is doubling.  The four-colour problem is a problem of this sort, so each time you create a map that is a little bit bigger that you have to deal with to prove your theorem, the amount of computational time to check it doubles.

The easy and hard problems can be set out schematically like this:

        'Easy' problems with N parts - Calculation time grows as N
        'Hard' problems with N parts - Calculation time grows as 2N

There are many almost trivially simple problems which have this hard type of ballooning in the computational time and the number of possibilities that you have to check.  Here is one I think I showed in a previous lecture.

It is perhaps the poor person's Rubik Cube of the 1950s and 1960s.  I can remember getting these boring little puzzles in Christmas stockings, the sort of thing that you did not want to get - only a pair of stockings would be less welcome.  It is like a Rubik Cube in two-dimensions.  It is like a jigsaw-type puzzle made of squares, and each square has got the parts of a monkey in different colours, and so there are top halves and bottom halves and there are several colours, and you have to put the puzzle together so that you make whole monkeys of the same colour across the borders.

If you just look at this puzzle in a counting fashion, you have got nine cards to match up, and you have got four orientations in which you can put each card down.  So if you just put down the first card, you have got nine ways to put that card down.  The next card could be put down in eight ways, and the next one in seven, and so on and so on, so the number of ways in which you could put down all the nine cards is 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2, which we wrote as nine factorial, 9!, but each time you put the cards down, you had four choices of orientation, so you have got another 49 options.  So if you multiply that out, it is a rather large number - it is bigger than 95 billion.  So you can see that, even with a very fast computer, if you were just checking the possibilities one by one, you are soon going to be out of time.

In fact, if you just buy the deluxe version of the puzzle, which is four by four, then you are looking at 25! x 45 possibilities.  Even if you used a computer that could check a million of those moves every second, you are looking at more than 500 trillion trillion years of computing time to check them all.

So you can see that very simple problems can generate an enormous number of possibilities very easily, and the brute force approach with a computer is not going to be particularly helpful.

Another famous problem, this time unlike the Four-Colour problem, it is an unsolved problem, is the Travelling Salesman Problem.  This problem has a million dollar prize attached to it.  The reason there is such a big prize is not because the world of travelling salesmen are so wealthy that they can sponsor this competition, but these hard and complex problems have a wonderful and almost unsuspected property.

In the 1970s, a person called Cook showed that if you could solve one of these types of problems, or find a way to turn a hard problem into an easy problem - so instead of having the computation doubling at each step, it just increases in proportion to the steps - if you could do that for one of these problems, there would be a way to do it for all of them.  So it is a real panacea and one of the most valuable things that you could ever discover commercially and so forth.  So the Travelling Salesman Problem solution is not just going to solve the Travelling Salesman Problem; it is going to solve almost any other nasty problem like this you could think of.

The Travelling Salesman Problem is simply the idea that you have to visit lots of cities and you want to visit the cities, all of them, once and only once.  What is the route that you should take that minimises the total distance travelled?

This is a hard problem, because each time you add another city to visit, the computation doubles.  You can see in a way why this is the case because if you add a city, it does not just add on an extra leg onto the trips that you have already got sorted out - it could change everything.  So these problems are highly entwined.

Airlines have to do something rather similar when they create timetables, but they sort of cheat.  They just work out a timetable for one collection of routes for one part of the globe, and another one for another part, and they just glue them together, and it is too bad if you miss the connection.  They will then try by hand to sort of work on some of the difficulties here and there, but they do not have a solution to this problem.

There are other versions of this problem that come up in unsuspected places, and there is one from the world of silicon chips and computer technology.  There is always a question of how best to wire silicon chips, and the idea is that the robot has got to make electrical connections around more than 3,000 electronic points of contact on this chip.  You can see this is a version of the Travelling Salesman Problem.  You want to work out how to do this: you visit each point once and only once, otherwise you will have a short circuit; you want to do it in the least amount of possible time, because if you are making millions of these chips and your robot is touring around doing that, if you can save 10% on the time the robot takes to deal with one chip, this is a big saving in the production process, and as we know, time is money.  They eventually found a solution which was, until a few years ago, the largest Travelling Salesman Problem that had been solved.  It is only 3,038 sites, so it is really not very big, but this took 1.5 years of computing time on the world's fastest computer to find, at that time.

Since then, the record has been broken by corralling lots of computers to work on the problem at the same time, in parallel.  There is a Swedish group who worked out a real version of Travelling Salesman by considering the optimal tour of all the villages and towns in Sweden, which goes to nearly 25,000 cities, towns and villages.  This took eight years of computing time to find, and as far as I know, it is still the record.

That is a look at some of these famous problems which sound simple but because there are so many possibilities, they take an enormous time to solve.  At the heart of their difficulty is this problem that, when you add another bit to the problem, like when you add another city, you cannot use the same recipe that you have been using already, so there is not a simple rule of thumb, a simple formula, a simple computer programme, that will just churn out the solution for any number of cities.  You have seen roughly why: you add another city somewhere, it can disrupt the solution that you have got previously, in complicated ways, and so you effectively have to start from scratch.

We are going to have a look at three types of hard problem now.  It is rather different in flavour.  They are all about sorting things out, and they will be rather familiar to you.  The first is going to be about packing things in an optimal way, and again, as I just said, it is a situation where you cannot prove that this is the best solution.  You require some trial and error, some exploration of the problem, and then at the end, you will be able to convince yourself, in these cases, that you have got the best problem.

What packing is generally about is that you have got a certain amount of space, you have got all sorts of things to put into that space, and some of them are big and some of them are small, and so the problem is of what order do you put things into the packing space in order to make best use of the space?  You have all had this type of problem when you have tried to pack for your holidays.

Just to give you an example of why you need to think about this sort of problem: suppose that you had something like a large jug.  I first of all had some tennis balls, and I put some tennis balls in the jug until I could not fit any more in, and I asked someone, 'Is it full?'  They would say, 'Yes, it's full - you can't get another tennis ball in.'  But then I took out of my pocket some little marbles and I added them to the jug.  We then manage to get quite a few extra marbles in.  When we could not get any more in, we would ask the person, 'Is it full?'  Maybe they would say, 'Yes, it's full - you can't get any more marbles in.'  But then I got a bag of sugar here and I poured the sugar in, and it filled all the nooks and crannies that were left, all the way up to the top, and it is now full.  But you can see, if I had put the sugar in first, I would not have been able to get anything else in, so the order in which you went about packing things has a big impact on what you can get in.  So if, when you take your children on holiday, you fill the whole of the boot of the car up with sweets and packets of crisps, you will not be able to get any of the suitcases in, but if you put the suitcases in first, you will be able to get in sweets and tennis balls and things like that in all the gaps.  So, in a general way, you can appreciate why the order in which you do things is very important.

What are some more serious examples of things like this?  Suppose you are in the music business and you have got lots of tracks that last different periods of time - how should you put the tracks on the CDs so that you waste as little space as possible?

We have seen examples of packing things in boxes; scheduling tasks is another disguised version of this problem.  Suppose you have lots of computer data entry staff and tasks are coming in to the office, and you have got dozens of people and you have got to schedule the jobs for them; or maybe there are dozens of photocopying jobs of all sorts of different lengths which are long, and you have only got a certain number of machines - how do you schedule the task for the computer data enterers or for the photocopying machines so that you make best use of the machines in the time available, and you do not have some machine sitting idle for a long period of time while other jobs are sitting waiting?

If you are running TV shows and you have got advertisements that have been paid for to run during that show, so you have got three or four commercial breaks, they have got particular time intervals that they can run for, and you have got advertisements that last for many different periods of time, how can you best schedule what advertisements you are going to run in what commercial breaks so that you waste as little time as possible and don't disrupt the running time of the television show?

These are all disguised versions of this type of packing problem.  You have got things of different sizes, you have got a limit on the total space: how do you use the space?

We are just going to look at one example, so let us suppose that we are in the world of data rather than suitcases, and we have got these 25 files of data and we have got to fit them onto computer discs, and each of the discs has got a maximum capacity of 10 Gb.  We will not mention the units again - we will just say ten.  So, what we are told about these files is that these are the sizes of the individual files:

        6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1

If you add this lot up, it comes to 106, and we want to know how we can fit them onto discs so that we use the smallest number of discs that is possible.  Let us look at some strategies for doing this.

The first strategy that you might think of, which gets imposed upon you in some types of problem, is called 'next fit'.  What you do here is that you put the first track on the first disc, the next one that comes along you put in the same disc, if it will fit, otherwise you start a new disc.  In our case, the first file is 6, and because the capacity of a disc is 10, the next file, which is size 6, will have to go on a new disc. You are not allowed to go back with this strategy, so once you have left a disc unfilled, you cannot return to fill it later on, so it is as though the discs are on a sort of production line that is going past you - you have to make a quick decision and then the disc is gone - so you cannot go back and fill the gaps.

So what happens?  If we have a column per disc, we can show the first disc like this:

 

 

 

5

5

 

 

 

 

 

 

 

 

2

 

 

 

5

5

2

 

 

 

4

 

 

 

2

 

 

 

5

5

2

 

 

 

4

 

4

 

8

1

 

 

5

5

3

 

7

 

4

2

4

 

8

7

6

6

5

5

3

 

7

6

4

2

4

 

8

7

6

6

5

5

3

3

7

6

5

2

4

5

8

7

6

6

5

5

4

3

7

6

5

2

4

5

8

7

6

6

5

5

4

3

7

6

5

3

4

5

8

7

6

6

5

5

4

2

7

6

5

3

4

5

8

7

6

6

5

5

4

2

7

6

5

3

4

5

8

7

 

 

So the first disc is entirely taken up by the file of size six (represented by the six digits in the first column).  The second disc is also taken up by a single six.  Then I have got four lots of five, which are nice, so I can get two of the fives on the next disc, and I can do the same with the next two fives, so there is no wasted space over these discs.  But then I have got a four, a three, and a couple of twos, so I can get those into the next disc and the start of the one after that.  Then I have got a three followed by a seven, which accounts for the next two discs.  You can see from the diagram how the rest works.  What is characteristic is that there are empty gaps, so there is wasted space here.  How many have we had to use?  Well, if you count along the bottom, 14 discs have been used to fit all these tracks to fit all these tracks on.  Only two of them are full.  There are 34 empty slots from this 'next fit' strategy.  So there is 140 slots in all, 14 discs times 10, so 76% are filled, so you have wasted 24% of the space.  So this is not so good.

So let us think about how we might do better.  I will mention three things that you could do.

You could allow yourself to go back.  This might not be an option in some problems.  Suppose we call this 'First Fit', so when you have the new number to fit in, you are allowed to go back and put it in the first disc where there is still room.

The other thing you could do, which I call 'Worse Fit', but it is not necessarily the worst strategy, is to put it on the disc that has got most space in it, so it is the most unfilled one.

The last one is to put the next track on the disc that leaves the least room after it has been added, so you are trying to fill things up as best you can.

First, let us look at 'first fit'.  We are not going to look at all those options, but we will look at 'first fit'.  So, in this case, you can put the track on the first disc that has space, and you can go back and fill gaps in earlier discs.  This strategy allows you to go back, fill empty spaces, and you will see, this time, you can get everything in in twelve discs, so you have saved two entire discs in the process.  You have got six filled discs here, and you have got 14 slots that are empty now, so you're 88% full with this strategy.  So it is a big difference in being able to go back and make use of empty space.

The next thing you might think about to try and make things more efficient, this going backwards helps, but somehow the problem seems to be that something large sort of comes up unexpectedly near the end.  At the end, you run into trouble; you have to start a lot of extra new discs because you have filled up a lot of space early on.  What if you sorted things beforehand?  So, suppose you sort things in descending order? 

There is a general strategy for these sorts of problems, which is sometimes just called the 'greedy strategy' or the 'greedy algorithm', which means that you start with the big things that take up most space.  My little example with the tennis balls and the marbles and the sand - you could see that if I start by packing the big things in first, I am going to be able to get the other things in in some measure; if I had started with the small things, you will never get the big things in.  So this type of greedy strategy is rather like sorting in descending order, and now you can try the other strategies on the sorted distribution.

We can first try our 'next fit' approach, and you are not allowed to go back in this 'next fit' strategy that we looked at.  But this time we will re-arrange our sequence of files into the following descending order:

        8,7,7,6,6,6,5,5,5,5,5,5,4,4,4,4,3,3,3,2,2,2,2,2,1

So you have got eight first, and then you have got the sevens, and then you have got the sixes, and so on.  In this approach we will use fourteen discs still.  So it looks good, but it's still not too great an improvement.  We have only got three full discs from this method.  There are 34 slots empty.  So it is pretty much the same, 76% full, as the unsorted 'next fit'.

But our 'first fit', where we were allowed to go back, shows the combination of being able to return and to sort things is really a winning strategy here.  So we have got a sorted distribution, we put the first one in the next available disc, and then we are allowed to go back.  In doing this the distribution of files across the discs are as follows:

 

2

3

3

4

4

4

5

5

5

1

 

2

3

3

4

4

4

5

5

5

2

 

8

3

3

4

4

4

5

5

5

2

 

8

7

7

4

4

4

5

5

5

3

 

8

7

7

6

6

6

5

5

5

3

2

8

7

7

6

6

6

5

5

5

3

2

8

7

7

6

6

6

5

5

5

4

2

8

7

7

6

6

6

5

5

5

4

2

8

7

7

6

6

6

5

5

5

4

2

8

7

7

6

6

6

5

5

5

4

2

 

 

So in this method we start with our eight, and then we do our two sevens, and then we do the sixes, and then we do the fives.  We have then got some fours, which we fit into the gaps wherever we can.  We do the same with the threes and the twos, and then there is the one.  In doing it in this way we have got no wasted space here at all.  We have got 96% full, with only seven slots empty, and we have used eleven discs, of which ten are full.

You will remember that we had 106 files in total, and so you can work out really that this is the best possible fit.  With 106 files, there is no way you could have less than eleven discs.  You have got ten on each one, so 106 divided by 10 is 10.6, so you could not possibly do better than this.  There is no way of putting these into these ten because there is no space.

So this is an example of how different strategies really make a difference in these sorts of problems.

Let us move on to a different, in some ways, much simpler, counting problem.  In mathematics' circles, there are things called McNugget numbers, which are interesting.  They have their origins in chicken nugget boxes long ago.  When chicken nuggets first came on the market from McDonalds, they came in boxes that either contained six bits of chicken, nine bits of chicken, or twenty bits of chicken.  So you begin to wonder, what are all the possible numbers of bits of chicken that you could purchase?  You see, there is no way in which you can buy seven bits of chicken.  You can have six, and you can have six plus nine, you can have twenty plus nine, so all the combinations of some number times six, plus some number times nine, plus some number times twenty, give you all the possible numbers of pieces of chicken that you can have.  So you can ask, what is the largest number which cannot be expressed in this way, and we call it the non-McNugget number.  You can convince yourself that any sufficiently large number can be written as a linear combination of sixes and nines and 20s, okay, and so there must be a number below which you cannot do it.

To see that this is true, if you just take this run of numbers:

        44, 45, 46, 47, 48 and 49

You can make those in terms of sixes and nines and twenties, in the following ways:

        44 = 6+9+9+20
        45 = 9+9+9+9+9
        46 = 6+20+20
        47 = 9+9+9+20
        48 = 6+6+9+9+9+9
        49 = 9+20+20

Because you can add a six to each of these numbers, because you can add a box of six pieces of chicken, that will give you 50, 51, 52, 53, 54 and 55.  You can see that if you did that again, you could get every bigger number just by adding sixes to these.  In fact, the largest number which you cannot make as a combination of sixes and nines and twenties is 43.  You can see that because when you combine the sixes and nines, they are both divisible by three - you can only make numbers which are divisible by three.  If you try to save the situation by using a twenty, or two twenties, then that does not help, so you cannot make 43 out of sixes and nines and twenties.  So 43 is the largest, and here are all the other numbers of chicken pieces that cannot be made from these boxes:

        1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43

Obviously, one to five, you cannot do, seven and eight, you cannot do, then ten and eleven, and then you have a run, 13, 14, 16, 17, and then there is another run in the low twenties, but 43 is the largest non-McNugget number.

So this is characteristic of a certain sort of problem, where you are adding combinations together.  The general question is of what is the largest number that does not have some property?

However, the world was shattered by a development in the chicken nugget business because, in 1979, a new number appeared in this problem when the Happy Meal appeared, which allowed you to have four pieces of chicken!  So the whole problem then becomes much less interesting, because you want to know what are the numbers that you cannot express in terms of four, six, nine and twenty, and this dramatically reduces the complexity of the problem, and the largest one is eleven.  So there is no way you can make an eleven out of these combinations of boxes.  You can make a twelve, you can have two sixes, you can a thirteen, fourteen, and so on, every bigger number.  So eleven is the new non-McNugget champion.

There are two famous problems of this sort that turn out to be mathematically much more interesting than this one, and I am going to spend the rest of my time telling you about them.

The first one is just known as the Stamp Problem or the Postage Stamp Problem.  A Postage Stamp problem asks, if you have an envelope which will only hold a certain number of stamps, then what is the smallest total stamp value that will not fit on the envelope?  For example, suppose you just have stamps that have value one, three and five, and no envelope can have more than three stamps, then the smallest postage that you cannot fit on is twelve.  Anything bigger, you will not be able to fit on possibly either.  So this is the structure of this problem - as again with many of these problems, it is not only about stamps on envelopes.  Whenever you have things coming in a certain number of denominations - they might be packages that have a certain size, and there is only a certain amount of space that you can fit them in - this type of problem arises.  So the packages might have different values, and the different values might correspond to different volumes, and you have a limit on the amount of storage space.

So this problem turned out to be really unexpectedly difficult, in many ways. It is one of these problems that, in a sense, is equivalent to the Travelling Salesman Problem - and this was shown definitively just a few years ago.  So if you could solve this problem, you would be able to solve all these other computationally hard problems as well.

The situation, in mathematical language, is that you have got some envelope which holds some maximum number of stamps, which we will call h, so you cannot fit any more on.  Your stamps come in particular values, and we will call those values a1, a2, a3, and so on.  What you want to do is to sort these stamps in ascending order, and we will take the bottom stamp to have one unit, for simplicity's sake here.  What we want to know is: what is the smallest whole number that you cannot write as a linear combination of the 'a's?  So it might be six of a1, plus seven of a2, and so on, where the sum of the numbers of stamps that you use has to be smaller than h:

        An envelope can only hold a maximum number of stamps £ h
        Stamps have values An = {a1, a2, ... an}
        Sort in ascending order so that 1 = a1 < a2 < ... < an

        We want the smallest integer that cannot be written as
        N(h, An) = F1a1 + F2a2 + ... + Fnan 
        where F1 + F2 + ... + Fn < h

This problem has the structure where the first part is of a problem of Diophantus, Diophantine arithmetic, where you are just looking for solutions of problems which combine whole numbers, integers, in particular ways.  The added subtlety here is that there is an inequality involved in the total number that you can use.

So in this simple problem, the exact solution is only known in the case where there are two stamp values.  So, in that case, this number of consecutive values is given by the limit ah plus three, minus the second stamp's value, times second stamp's value, minus two.

        n(h, A2) = (h + 3 - a2)a2 - 2 for h ≥ a2 - 2

So the first one is one, you see, and this is for all cases where the number of stamps is bigger than the second stamp's value minus two. 

You can write this in a different way: so if the second stamp's value is two, it looks like the whole number part of this combination here, h2 + 6h minus one over four.  So that square bracket means take the whole number part, so the square brackets of pie would be three.

        n(h,2) = [(h2 + 6h +1)/4]
        [...] is integer part, so [3.14] = 3

So if you work out what this is, the first few different values of h, as your envelope gets bigger are:

        2, 4, 7, 10, 14, 18, 23, 28, 34, 40, ...

When you go up to four stamps the number is really growing very fast.  It is growing like the fourth power of the size of the envelope:

        N(h,4) > 2.008 x (h/4)4 + O(h3)

So this postage stamp problem is a first example of this type of combinatorical problem of packing things with constraints.

The last problem I want to look at, which I think is more interesting than the stamp one, and it is perhaps more immediate, is sometimes called the Coin Problem, and I call it the Spare Change Problem.  It is about what denominations of coin should you have in your currency so that you are able to make change in an optimal way.  So you want to be able to make every amount, say, from one to 100, with your coins, but you might also want to have the smallest number of coins on the average being used, so how should you do that?  If you only had a 1p coin you can make every amount from one to 100 without any problem, but your pockets get very heavy and life slows down at the checkout counter.

If you are sufficiently old, you will remember some of the old form of English coinage.  They were set out in what might strike us today as odd choices.  There was a farthing, a quarter of an old penny, half an old penny, two and sixpence, threepence, sixpence, two shillings.  Nowadays, we have a rather different set of denominations.  So what is best and what are the properties of these coin systems?

If you are in the United States or you are in Europe or the UK, you have a decimal system, so you want to make change from one to 100, or one to 99 if you do not have a pound coin.  In Europe, the denominations that we have below 100 are 1, 2, 5, 10, 20, and 50 coins and Euro cents.  America has a smaller system: it has a cent, a nickel, a dime, and it has the quarter, so it has fewer coins, and the denominations are slightly different.  So what you are interested in with these coins, and one of the reasons they are selected as they are is that you want a system of making change that allows you to use the Greedy Algorithm, so you start with the big coins first.  So if somebody says, 'Give me 76p,' and you have got loads of coins, what the Greedy Algorithm means is that the way you do it is: you see how many 50s do you need first - one; how many 20s - one; how many 10s - none, you do not need a 10; you want one five, and then you want one one.  In America, you would do it with a 50, a 25, and a 1.

        76 pence = 50 + 20 + 5 + 1 (4 coins)
        76 cents = 50 + 25 + 1 (3 coins)

So in America, you have got fewer coins in the collection, but you can do 76 in three coins; here, you need four.  But the point is that, in both systems, it is this Greedy Algorithm that gets you to the best solution.  So this I call the Handy Property of Currencies. 

There are lots of systems that do not have that property.  For instance, 'old money', as my mother used to call it, in Britain did not have that property.  So, after the farthing disappeared, we had half, a one, three, six, twelve, 24 and 30, old pence.  Now, suppose you want to make four shillings.  That was 48 old pence.  If you followed the Greedy Algorithm, you would take a thirty, you would not need a 24, you would pick a twelve, and then you would pick a six, but you could have done it more easily with two two-shilling pieces, so two two-shillings would have been two-24s, so there was a non-Greedy solution in old money that does not exist anymore.  So when you double a coin value, you get this property, so when you had a fourpenny piece, a groat, and you wanted to make eight-pence, you could do it with two groats more easily than a sixpence and two pennies. 

But if you want automatic sorting, manipulation of coins by machines and so forth, having this Greedy Algorithm is rather useful.  You can see, if there is a unique way to make things like this, a best possible way, it is going to help you if you operate by weighing coins and combining them in that fashion.

Geoff Shallit at the University of Waterloo in Canada, who works on integer sequences, decided a few years ago, that he would carry out some investigation, first of the US system, and then you could extend this to the European system, to see if you could make it better in some, perhaps unexpected, way.

So what you discover, in the US system, first of all, is that if you want to make all possible amounts, from one up to 100 cents, by combining coins using this Greedy Algorithm, you can ask 'What's the average number of coins that you need?'  You can do a few cases in your head.  If there was only a 1 cent coin in existence, you are going to need 99 coins to make 99 cents, and so on and so on, and the average number that you will need to make them all is 49.5, so the average number of coins that you would need for a transaction would be 49.5, so that is not so good.  So, if you take the actual situation, and work out all the numbers of coins that you need for each transaction, from one up to 99, the average number is 4.7, so that characterises the US system.

        Average number of coins needed to make 1 to 100 cents with
        1, 5, 10, 25 denominations is 4.7

Some people might worry that, because some things tend to cost $5.99 or something of that sort, there are certain amounts that come up a lot, which might bias the system, and if you had a 99 cent coin, things might be a lot simpler.  But unfortunately, in the US, they have this habit of never adding the sales tax to the up-front price, so everything you buy turns out to have a weird price.  It may say $4.99 in the window, but when you pay for it, it is $5.17 or something like that.  So this is a good way of averaging things out.

So you could ask, if you stick with four coins like this, could you do better?  What Shallit discovered is that there are two systems that do better.  If you had a 1 cent, a 5, an 18 and a 29 cent coin, you would do much better - you would have an average of 3.89 coins per transaction.  That is without taking into account that people would change what they charge for things to match these.  But, better still, there is another combination that only changes one value, and that is if you stay with the 1, the 5 and the 25, and introduce an 18 cent coin then you also have only 3.89 coins on average per transaction.  So his recommended strategy was to replace the ten cent, the dime, with an 18 cent coin.

        What is the best case using only 4 values?
        1, 5, 18, 29    and    1, 5, 18, 25 are both better!
        They need an average of 3.89 coins to make all 1 → 100 cent amounts
        Best to use the 1, 5, 18, 25 values
        And replace the dime with a new 18c piece

Suppose you think about this in the European system.  We have got 100 and 200p coins.  The analogue here would be to think how many coins do you need to make everything up to 500, and the answer is that you need 4.6, on the average, so it is not dissimilar to the American system, to make all those amounts. 

If you do the same computer study and you see what happens if you change each coin in turn, then adding a 133p or a 137p cent coin reduces the average, so having an extra coin of these strange values, one or the other, reduces the number of coins that you would need in the European or UK system rather unexpectedly.

Could you do better still?  So this is the last thought for today, and this is rather surprising I think, that when you look at lots of currencies, certainly ours and the Euro, you see there is a certain pattern of the denominations that are used.  We have a 1, a 2, and a 5, and then we have a 10 and a 20 and a 50, and then in notes, you have coins, 100, 200, 500 - so we like this 1, 2, 5 combination.  But, if you changed it to 1, 3, 4, so that you had 10, 30 and 40, 100, 300, and 400, and you look at all the ways that you then have of making change, you do better.  In fact, you do 6% better on the average, using 6% fewer coins in transactions. 

So, just to see how this goes, that this method is still pretty Greedy:

        68    =  50 + 10 + 5 + 2 +1          = 40 +10 + 10 + 4 + 4
        134  = 100 + 20 +10 +2 + 2         = 100 + 30 + 4
        243  = 200 + 20 + 20 + 2 +2        = 200 + 40 + 3
        279  = 200 + 50 +20 + 5 + 2 +2   = 200 + 40 + 30 + 3 + 3 +3

If you want the Greedy property, then this new method is not the way to go, but it is curious that you do about 6% better, and even if you take into account that there might be some bias towards transactional amounts sort of ending in zero and one and two, rather than higher numbers, it still remains about the same.

Of course, if you really want to make a big reduction in the amount of change that you have, the simplest thing of all to do is just to eliminate the 1p or the 1 cent coin, and round everything up and down to 5p or 5 cents.  One day, that will come, because there will be no value at all attached to 1, 2, 3, or 4 pennies or cents.  If you were to do that, then what would happen, in the American system, for example, where you will remember that there is 4.6/4.7 coins on average per transaction, that would plummet down to about 2.6/2.7, just by eliminating the ones, and all the sums thereafter would be for 5s, for 10s, for 15s, for 20s - for multiples of 5.

So I hope this little excursion into making change, putting stamps on envelopes, and packing your luggage, has shown you that there are unusual uses of very simple mathematics, uses that end up really being very complicated.  This Coin Problem, like the Stamp Problem, is computationally hard, in the technical sense.  If you were to solve it, you would have a way of solving all these other computationally hard problems as well.  Those results were only proved really about ten or fifteen years ago, step by step, by mathematicians who are specialists in the structure of these types of integer sequences.

 

 

© John D Barrow, 24 November 2009