WHY WON’T THE CASE FIT IN THE BOOT?
How to squeeze things in or keep them apart
No matter how hard some of us try, when we have to fit the holiday luggage into the boot of the car there always seems to be one bag that is determined not to fit.
Normally a bit of repacking and reshuffling of the bags solves the problem, but fitting things into a tight space is a serious problem in the business world, and packing problems have been a source of investigation for many years.
One of the oldest such problems is that of packing circles into rectangles, a problem encountered by supermarket staff when stacking or packing tins of, say, baked beans. The tins have a circular cross-section, and have to be fitted into a rectangular shape. This may be the shelves they are to be displayed on, or the boxes they are transported in.
Fitting circles into squares
The obvious way to put circles together is in a rectangular grid, or ‘lattice’, like this:
However, this is not the most efficient method. There is quite a bit of wasted space, and it’s easy to work out what this wastage is. Remember that the area of a circle is π (about 3.14) times the radius squared. If the radius of a tin of beans is 5cm then its area is π x 25, which works out at roughly 78.5cm2. The area of the square around it is 10 x 10, or 100cm2, so the circle is occupying only 78.5 per cent of the area.
There is a far better way of packing baked beans together, and this is the hexagonal method:
Here, the proportion of the area covered by the circles is just over 90 per cent. The exact figure is π/(2√3).
In fact, if you are packing tins of baked beans into a vast space, there is a mathematical proof, Thue’s Theorem, which says this form of hexagonal packing is the densest packing possible. So, as is so often the case in mathematical problems, the optimal solution to a problem turns out to be based on one of the simplest known patterns.
However, Thue’s Theorem is strictly true only if there is an infinite amount of space. The available space in the real world is most definitely finite. When space is limited, the most ‘regular’ packing is not always the most efficient. Take for example the problem of fitting nine tins of baked beans into a square tray. If you pack the tins in the normally optimal hexagonal layout, the smallest possible square tray that will hold them has to be about 31⁄2 tin diameters across.
Compare this with the usually less efficient square array:
Here, the tins fit into a 3 x 3 square. In fact, in 1964 this was proved to be the optimal fit of nine circles into a square. You can’t fit nine tins into a smaller square, however hard you try. Not unless you crush them, anyway.
As the number of tins increases, the optimal pattern changes. Some are quite surprising. For example, the optimal packing for thirteen tins is a square of roughly 3.7 x 3.7, in this formation:
It may look a bit of a mess, but it has been proved to be the best solution. Twelve of the tins are locked into position, while the thirteenth, the black one, is rattling around in the middle.
In everyday situations, it isn’t that common to fit a box around the items being packed. Usually the box size is fixed, and the problem is to squeeze in as many items as possible. So mathematicians have also investigated the problem of fitting as many circles as possible into a square of some given dimension. This is subtly different from the problem that has been discussed up to now.
To make the dimensions easier to handle, let’s switch from baked-bean tins to pennies. If the diameter of a penny is 1cm, how many pennies can you fit into a 10cm x 10cm square? You might guess that you can fit 100 pennies in, which is true if you use the regular square array.
However, it is possible to fit in more than this. If you arrange the pennies in a hexagonal array, it turns out that you can squeeze in an extra five pennies, making 105 in total.
But even this isn’t the maximum. By combining square and hexagonal packing, it is actually possible to fit another penny into the square. As with the earlier example, the optimum solution is not the most ordered and regular one:
This type of packing problem is relevant not just for shops and packagers wanting to squeeze as many items into limited space as possible, but also for manufacturers who want to cut as many pieces out of a sheet as possible. One nice example of this comes from the shoemaking industry. In some upmarket manufacturers, shoemakers still cut the leather uppers from cowhides by hand. Each cutter is given a target number of uppers to cut from the hide, and if he exceeds the target he gets a bonus. Perhaps you have replicated this problem in the kitchen with a pastry cutter.
So far all of the discussion has been about packing circles into squares. Just as common is the problem of packing rectangles into rectangles. Here, the obvious way to stack is to put the flat surfaces against each other, forming patterns like a chessboard, or the herringbone effect to be seen on many wooden floors.
However, the mathematician Paul Erdos discovered that such rigid and neat patterns are not always optimal. In exactly the same way that a bit of irregularity can help you to squeeze in more circles, sometimes more squares can be packed into a given space by twisting them around a little. Erdos produced a formula that said that in a square with side S cm and tiles with sides of 1cm, there is guaranteed to be a packing that leaves no more than S0.634cm2 uncovered. To put this in perspective, tiling a square of 100.5 x 100.5cm (area 10,100.25cm2) with 1cm square tiles in regular chessboard format will leave a space of about 100cm2 uncovered. However, by jiggling them in a less regular pattern it should be possible to squeeze in at least 81 more, leaving no more than 100.50.634, or 18.6cm2, uncovered.
The challenge of fitting squares into circles also has a practical application. The square silicon chips used for computers are cut from circular wafers of silicon. You can probably picture how the curved edges of the wafer end up as waste. However, the larger the wafer, the smaller the proportion of wafer that needs to be thrown away, which is why manufacturers have invested a lot of money in finding ways of growing larger silicon crystals.
Three dimensions – stacking a pile of oranges
When it comes to three dimensions, the problem of packing takes on a whole new level of complexity. The most analysed three-dimensional problem is that of stacking oranges.
Go to a fruit stall, and you might well see oranges being stacked in a pyramid like this:
Viewed from above, the oranges form hexagonal arrays layered on top of one another. In 1690, the great astronomer Kepler speculated that this was probably the most efficient way of stacking spherical objects (that is, the amount of air trapped between the oranges is the minimum possible). Nobody was able to find a better way of stacking spheres, but it wasn’t until 1996 that it was finally proved to be true. Stacked this way, the oranges occupy π/√18 of the available volume (a little over 74 per cent).
This may make you wonder what would happen to the oranges if you were able to compress this stack together so that all of the air gaps were removed. What is the solid shape that each orange would be squashed into? Would it involve hexagons, like those produced when you squash together the circles here? You can try to find out by squeezing together soft spherical objects, such as peas, freezing them and dissecting the result. (We tried it with marshmallows but they are much too elastic and bounce back to their original shape when unsquashed.)
It turns out that the squeezed oranges form into a peculiar regular solid known as a rhombic dodecahedron. This solid has twelve faces, each of them the shape of a diamond, with the following dimensions:
Viewed from some directions the outline of the rhombic dodecahedron is a hexagon, and viewed from others it makes a square. It is really quite a beautiful object.
Because of its efficient packing structure, shapes approaching the rhombic dodecahedron can be found in some crystals, as well as in beehives and, presumably, in piles of soft, rotting tomatoes.
Conveniently, everything we have been packing so far has been the same size. Again, real life tends not to be so simple. Whether you are filling the fridge with food or packing parcels into suitcases, the fact is that most of the time the objects to be packed are all shapes and sizes. In these cases, mathematicians usually throw their hands up in despair and leave it to operational researchers, who are less purist in their approach and are often content to come up with solutions that are reasonable but not perfect. The trick of the operational researcher is very often to develop sets of rules or algorithms that are guaranteed to lead to a solution that is within a certain target – say 10 per cent – of the best possible.
Think of those occasions where you are moving house. You know that the volume of items you need to shift is enough to fill about twenty identical boxes – except that it would require far too much time and planning to work out what to put where. Instead, you go for the easiest method of packing, which is to put items at random into the first box, and, when the next item you pick up doesn’t fit, you seal up the box you have been filling and start on a new one. This is known as a ‘first-fit strategy’. How efficient is it? It turns out that, however unlucky you are with the order in which things come to hand, the number of boxes you need will always be within 70 per cent of what could be achieved with perfect allocation. So if your best possible is 20 boxes, you can reassure yourself that even the lazy first-fit method strategy should require at most 34 boxes. If this isn’t good enough – and, let’s be honest, 70 per cent is a bit of a waste, though this is the worst-case scenario – a strategy of packing the biggest things first and the smallest last always turns out to be within 22 per cent of the very best solution. This means a worst case of 25 boxes, instead of the optimal 20. And, since many of us tend to use a biggest-first strategy, especially when filling the car boot, this shows that when it comes to packing, common sense is a good substitute for deep mathe -matical thinking.
Incidentally, this result doesn’t just apply to putting objects into boxes. The things being ‘packed’ can be all sorts of other resources, such as money or time. Think of the people turning up at an embassy to have their visas processed. Because the circumstances of each case are different, each will take a different amount of time to be dealt with. These different service times are equivalent to the differently sized parcels. The officer behind the desk only has a certain amount of time at work each day, and that available time is equivalent to the box.
One rather bureaucratic embassy we came across dealt with people on a first-come-first-served basis, just like the basic boxfilling method described earlier. If a new arrival at the desk was deemed to require more time than the administrator had remaining before clocking off for the day, the applicant was told to come back the next morning (i.e. today’s box was full), and the desk closed for the night. This certainly seemed inefficient, though we can say with confidence that at most 70 per cent too many days were used to handle applications.
The attraction and repulsion of packing people together
What is great about most inanimate objects is that they don’t mind being packed together as tightly as possible. This is not usually the case for people. The phenomenon known by psychologists as ‘personal space’ has all sorts of implications for the way people can be packed together. Another fundamental difference between people and baked beans, of course, is that the people usually have some influence on how they arrange themselves and so design their own packing rules on the hoof.
One of many classic people-packing problems is sitting down at the cinema. Unlike baked-bean cans or luggage, the audience arrives in dribs and drabs, and although the packing arrangement for a full house is predetermined, the way people occupy a cinema when it is not filled to capacity is a rather more complex problem.
Two forces are at work in determining where people sit in the cinema:
• Attractive forces. These are forces that are pulling people to sit in certain positions, though the strength of each force will depend on the individual. Some will be attracted to a position near the screen (so they can see), others to the back of the cinema (so they can engage in unobserved activities), and others are simply drawn to the most accessible seats (the end of the row, for example). This will lead to clusters of people building up sporadically around the theatre.
• Repulsive forces. By far the strongest repulsive force for people in cinemas is other people. This is the personal-space factor. Given a choice, people will choose to sit as far from people they don’t know as possible, and will also avoid being directly behind somebody, so that their view is not impeded.
If the repulsive force were the only influence on cinema sitting, people would tend to seat themselves in something approximating a hexagonal lattice, which has cropped up before in this chapter, since that is the spacing in two dimensions that puts people as far from each other as possible. However, because of the various attractive forces, the hexagonal spread will be distorted, with denser packing near the front, back and central aisle of the theatre.
A similar combination of attraction and repulsion occurs on a bus. Here the attractive forces are primarily convenience.
Seats nearest the door or the top of the stairs are preferable for most people, though the front seats on the top deck have a special charm for some of us. The repulsive forces on a bus are stronger than those in a cinema, so the spread of passengers tends to be more even. Informal observation would suggest that single passengers always choose empty pairs of seats if they are available.
When all the customers or passengers are seated on the bus or in the cinema, the pattern they form could be called the equilibrium state. All this may sound vaguely like some of the stuff taught in physics lessons. There is certainly a tenuous analogy between the way people sit themselves and the forces between atomic particles.
How to get on to a tube train
A lot of research has been conducted into the dynamics of crowds and how they pack together and move. One interesting conclusion from this is that there is a best and worst place to stand if you want to get on to a tube train. Mathematical simulations have demonstrated that you will get to the doors far more quickly if you are on the platform edge moving along the side of the train than if you are front-on to the doors. The most obvious reason for this is that you tend to move more cautiously if you are at risk of bumping into people on either side of you. Moving along the platform edge, however, you have to worry only about bumping into the people on one side.
Total repulsion and the gentlemen’s urinal
There are a few packing situations where the repulsion force is the dominant one. In these situations, the aim of the packing is for the objects to be spaced out from each other as far as possible. There is little point in having radio masts clustered together, for example, since their aim is to reach as wide a geographic range as possible. Since each radio mast broadcasts about the same distance in every direction, its reach can be represented as a circle. The aim of the network designers is therefore to cover the entire territory with as few circles as possible.
This spreading-apart problem is similar to the packing together of baked-bean tins, only this time no gaps between circles are permitted. Since every location must be within reach of at least one of the radio masts, circles will have to overlap. The optimal solution once again will be something close to the hexagonal lattice.
A more human spacing problem arises in the gentlemen’s urinal. Women not used to the inner workings of this room may not be aware that the positioning of men at the wall is usually such that the spacing is as large as possible. If the urinal is empty, the first male to enter will tend to occupy a stall at the very end of the line. The next will occupy the stall at the opposite end. In order to keep the distances as large as possible, the third will therefore occupy the stall that is as near to the middle as possible. Each subsequent arrival is subconsciously (or maybe selfconsciously) bisecting the largest space available. If the largest space is less than three stalls long, this inevitably means that a new arrival will be forced to stand immediately next to one or other of the current occupants. The repulsion force in this situation can be so strong for some males that they will divert to a cubicle instead.
This behaviour is quite predictable. Whether the simple maths involved has any practical application outside the gents’ toilet is another matter. Nor does it help to explain why women visit the ladies’ in pairs.
