100 Essential Things You Didn't Know You Didn't Know Page 15

  Suppose instead you asked: ‘What door would the other adviser tell me to go through?’ The situation is now more interesting. The truthful adviser knows that the lying adviser will tell you to go through the deadly red door so the truthful adviser will say that the other adviser will tell you to go through the red door. The untruthful adviser knows that the truthful adviser will tell you to go through the black door to safety and so the untruthful adviser will try to deceive you by saying you should go through the red door.

  You have made a life-saving discovery. Regardless of who answers your question, you get told to go through the red door. You have stumbled upon a question that is a tautology – it always has the same answer – and that is your lifeline. Your strategy for safe escape is therefore clear: ask: ‘What door would the other adviser tell me to go through?’, note the answer (red) and then go through the other door (black) to safety.

  71

  What a Racket

  Speed has never killed anyone, suddenly becoming stationary . . . that’s what gets you.

  Jeremy Clarkson

  Some things are harder than others to move. Most people think that the only thing that counts in such a problem is their weight. The heavier the load, the harder it is to shift it. But try moving lots of different types of load and you will soon discover that the concentration of the load plays a significant role. The more concentrated the mass, the easier it is to move and the faster it wobbles (recall what we learnt in Chapter 2). Look at an ice skater beginning a spin. She will begin with her arms outwards and then steadily draw them in towards her body. This results in an increasingly rapid spin rate. As the skater’s mass is more concentrated towards her centre, she moves faster. On the other hand, if you look at the shapes of girders used to build robust buildings, they have an H-shaped cross-section. This distributes more mass away from the centre of the girder and so makes it harder to move or deform the girder when it is stressed.

  This resistance to being moved is called ‘inertia’, following its common usage, and it is determined by the total mass of an object and also by its distribution, which will be determined by the shape of the object. If we think still about rotation, then an interesting example is a simple object like a tennis racket. It has an unusual shape and can be rotated in three distinct ways. You can lay the tennis racket flat on the floor and spin it around its centre. You can stand it on its top and twist the handle. And you can hold it by the racket handle and throw it up in the air so it somersaults and returns to be caught by the handle again. There are three ways to spin it because there are three directions to space, each at right angles to the other two, and the racket can be spun around an axis pointing along any one of them. The racket behaves rather differently when spun around each of the different axes because its mass distribution is different around each axis and so it has a different inertia for motion around each axis. Here are two of them:

  There is one remarkable property of these different motions, which is displayed by your three tosses of the racket. The motion around the axes about which the inertia is the largest or the smallest is simple. When the racket is flat on the ground or stood upright and spun, it does nothing very unusual. But when you spin it about the in-between axis, about which the inertia is intermediate between the largest and the smallest (shown on the right), something unusual happens. Hold the racket by the handle with the face upwards, as if you were holding a frying pan. Mark the top face with some chalk. Toss the racket so that it does a complete 360-degree turnover and catch it by the handle again. The face with the chalk mark will now be facing downwards.

  The golden rule is that a spin around the axis with the in-between inertia is unstable. The slightest deviation from the precise centre line always causes it to flip over. Sometimes this is a good thing. If you are a gymnast doing a somersault on the beam, then you look more impressive (and score higher marks) if you do a twist as well. But the twist can happen automatically because of this instability.

  A more serious example of this instability arose a few years ago on the International Space Station after it had been hit during a mistimed docking operation with a Russian supply craft. The Station was damaged and set in a slow spin. There was still gas in the system of retro rockets, which could be fired to slow the spin and return the Station to its usual state of equilibrium. The problem was, though, how should the rockets be fired? In what direction should you move the Station so as to counter the existing rotation. British astronaut Michael Foales had to solve this problem while holed up in the undamaged part of the Station with his laptop and a link to the ground. The most important things to discover were the three inertias of the Space Station with respect to rotations about its three axes. If the correcting rockets were fired wrongly, then they could set the Station spinning around its intermediate axis of inertia. The result would have been total disaster. The instability that flipped your tennis racket over had no bad effects on the racket, but flip over the Space Station and it would break apart, leaving all the astronauts dead, a quarter of a million kilograms of potentially lethal debris scattered in space and an astronomical financial loss. NASA didn’t know the three inertias for the Space Station – no one had thought such facts would be needed – and so Foales had to work them out from the design plans and then calculate how the Station would respond to rockets being fired in different directions in order to correct its spin from the accident. Fortunately, he knew about the instability of rotation about the intermediate axis and got all his calculations right. The dangerous spin was righted and the astronauts were saved. Maths can be a matter of life and death.

  72

  Packing Your Stuff

  On travel: I have learnt that you need four times as much water, twice as much money and half as many clothes as you think you need at the outset.

  Gavin Esler

  A young boy was once shown a large empty glass jar with a screwtop lid. He was handed a box of tennis balls and asked to fill the jar. He poured in some tennis balls and then moved them around a bit to try to squeeze in another tennis ball before screwing down the lid. ‘Is the jar full?’ he was asked. ‘Yes, it’s full,’ he replied. But then he was given a box of marbles and asked to see if he could fit any more in the jar. He opened the lid and found that he could fit quite a few marbles in between the tennis balls. Giving the jar a shake now and then allowed the marbles to settle into the spaces. Eventually, he couldn’t fit in another marble and announced that the jar was now full. His mentor then produced a bag of sand and asked the boy to fill the jar. Again, he unscrewed the lid and poured the sand into the top of the jar. This time he didn’t need to fiddle around very much at all, just give the jar a careful shake now and again to make sure that the sand was pouring into all the empty nooks and crannies between the tennis balls and the marbles. Finally, he couldn’t fit any more sand in the jar and screwed the lid back down again. The jar really was full!

  There are some lessons to be learned from this story. If the boy had been given the sand first and asked to fill up the jar, then there would not have been any room to fit in any marbles or tennis balls afterwards. You need to start with the biggest things if there is to be any room for them at all. The same applies to more familiar packing problems. If you need to move lots of packages into a van then you might want to know how you should set about loading them in order to have the best chance of getting them all in. Our little story shows why you should start with the largest objects and then pack the next largest and so on, leaving the smallest until last.

  The shapes of the things you are trying to pack clearly matter. Often, they are all the same size. If you are a manufacturer of sweets or other small food items, you might want to know what shape they should be in order to fit as many as possible into a jar or some other large storage container. For a long time it was thought that the answer was to make them all little spheres, like gobstoppers. Lots of little spheres seemed to give the smallest amount of empty space in between the closely packed balls. Interestingly
, it turned out that this wasn’t the best shape to use. If sweets are made in the shape of little ellipsoids, rather like mini-rugby balls or almonds, then more of the space can be filled by them. So Smarties and M&Ms fill a volume more efficiently than any collection of identical spheres. If the ellipsoids have their short to long axes in the ratio of 1 to 2, then they leave just 32% of the space empty, compared with 36% if they were made into spheres. This seemingly trivial fact has many important consequences for business efficiency and industrial manufacture, reducing wastage, shipping costs and the avoidance of unnecessary packaging.

  73

  Sent Packing Again

  All my bags are packed; I’m ready to go.

  John Denver

  Our little packing problem with the jars in the previous chapter was a nice simple one. We started with the biggest objects and progressed down to the smaller ones. In practice, our problem may be more tricky. We may have lots of containers to fill up with shopping items of different sizes. How do we go about distributing the items of different sizes across the bags so as to use the smallest number of bags? ‘Packing’ might not just mean packing in space either; it can mean packing in time. Suppose you are the manager of a big copy-shop business that runs off copies of different documents of different sizes all day for customers. How do you allocate the different copying jobs to the machines so that you minimise the total number of machines that you need to complete the day’s work?

  These are all versions of a problem that computers find very time consuming to solve when the number of items to be packed and the number of ‘boxes’ in which to pack them becomes large.

  Imagine that you can use large storage boxes that hold a maximum of 10 packages and you are given 25 packages of different sizes to stack in the boxes so as to use the smallest number of containers in the most efficient way. The sizes of the individual packages are as listed here:

  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

  First, let’s imagine that these packages arrive on a conveyor belt so you can’t sort them out as a group: you just stack them away one by one, as they come. The easiest strategy to follow is to put them into the first bin until the next won’t fit, and then start a new bin. You are not allowed to go back and fill empty spaces in earlier bins because they have been taken away. The strategy is sometimes called ‘Next Fit’. Here is how you end up filling the bins, starting from the left and adding a new one, as required. The 6-pack goes in the first box. The next 6-pack won’t fit so we start a 2nd box. The 5-pack won’t fit in there as well, so we start on a 3rd box. Adding the next 5-pack fills it and the next two 5-packs fill the next box and so on. Here is what ends up in the boxes if we follow this Next Fit prescription for the packages in the order given above :

  [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]

  We have used 14 boxes and only three of them are full (the two [5,5]s and the [8,2]). The total amount of empty space in the unfilled boxes is 4+4+1+5+3+4+1+3+2+5+2 = 34.

  The large amount of wasted space has been caused by the fact that we can’t go back and fill an empty space in an earlier box. How much better could you do if you could operate a packing strategy that allowed you to put packages in the first available box that had room? This is sometimes called ‘First Fit’ packing. Using First Fit, we start as before with a 6 and 6 in separate boxes then fill two boxes with two 5-packs. But the next is a 4-pack, which we can put in the first box with the 6. Next there is a 3-pack, which can fit in the second box with the 6-pack; then we can get two 2-packs and a 3-pack in the fifth box and so on, until we end by dropping the 1-pack back in the second box, which fills it. This is what the final packing allocation looks like:

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

  First Fit has done much better than Next Fit. We have only used 12 boxes, and the amount of wasted space is down to 1+1+2+5+2+3 = 14. We have managed to fill six of the boxes completely.

  We can now start to see how we might do better still in this packing business. The wasted space tends to come when we end up with a big package later on. The spaces left in the earlier boxes are all small ones by then, and we have to start a new box for each new package. We could clearly do better if we could do some sorting of the packages into descending size order. This may not always be an option if you are handling luggage coming off an airline’s luggage belt, but let’s see how much it helps when you can do it.

  If we sort our packages by descending order of size then we end up with the new list:

  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

  Now let’s try our old Next Fit strategy again with the sorting done – call it ‘Sorted Next Fit’. The first six packages all go in their own boxes, then we fill three boxes with pairs of 5-packs, and so on. The end result looks like this:

  [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]

  Bad luck at the end! We had to use a new box just to accommodate that last 1-pack. Using Sorted Next Fit we have ended up needing 14 boxes again – just as we had to do without the sorting – and we have wastage of 34 again. This is just the same as with the unsorted Next Fit. But if that final 1-pack hadn’t been included we would have still needed 14 boxes for Next Fit but only 13 for Sorted Next Fit.

  Finally, let’s see what happens with a ‘Sorted First Fit’ strategy. Again, the first six packages go into separate boxes, the six 5-packs then fill three more boxes, but then the sorting comes into its own. Three of the 4-packs fill the boxes with the 6-packs in, while the other 4-pack starts a new box. The remaining packages fill the gaps nicely, leaving only the last box unfilled:

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

  We have used 11 boxes, and the only wasted space is 4 in the last box. This is far superior to the performance of our other strategies and we could ask whether it is the best possible result. Could there be another packing strategy that used fewer boxes than 11? It is easy to see that there couldn’t. The total size of all the packages we have is 1 × 8 + 2 × 7 + 3 × 6 + . . . + 5 × 2 + 1 × 1 = 106. Since each box can only contain packages of total size 10, all the packages require at least 106/10 = 10.6 boxes to accommodate them. So we can never use fewer than 11 boxes, and there will always be no fewer than at least 4 waste spaces.

  In this case, we have found the best possible solution by using the Sorted First Fit method. If you look back at the very simple problem we looked at in the last section, fitting objects of three sizes into a jar, we were really using the Sorted First Fit strategy because we put the bigger objects in before the smaller ones. Unfortunately, packing problems are not all this easy. In general, there is no quick method for a computer to find the best way of packing any given assortment of packages into the smallest number of boxes. As the sizes of the boxes get bigger and the variety of sizes of the packages grows, the problem becomes computationally very hard and will eventually, if the number of packages gets big enough and their sizes diverse enough, defeat any computer to find the best allocation in a given time. Even in this problem, there are other considerations that might render the Sorted First Fit only second best. The sorting of the packages, on which the efficiency of the method depends, takes time. If the time taken to box up the packages is also a consideration, then just using fewer boxes may not be the most cost-effective solution.

  74

  Crouching Tiger

  Tyger! Tyger! burning bright

  In the forests of the night.

  William Blake

  A little while ago a tragic incident occurred at San Francisco Zoo, when Tatiana, a small (!) 135-kilogram Siberian tigress jumped over the wall of its enclosure, killed one visitor, and left two others seriously injured. Press reports quoted zoo officials as being amazed by the evidence that the tiger had managed to leap over the high wall around its enclosure: ‘She had to have jumped. How she was able to jump that high is amazing t
o me,’ said the zoo’s Director, Manuel Mollinedo. Although at first it was claimed that the wall around the tiger enclosure was 5.5 metres high, it later turned out to be only 3.8 metres, a good deal lower than the 5 metres recommended for safety by the American Association of Zoos and Aquariums. But should we feel safe with any of these numbers? Just how high could a tiger jump?

  The wall was surrounded by a dry moat that was 10 metres wide, and so the captive tiger faced the challenge of high-jumping 3.8 metres from a running start at a horizontal distance of at least 10 metres away from the wall at take-off. Over short distances on the flat a tiger can reach top speeds of more than 22 metres per second (i.e. 50 miles per hour). From a 5-metre start, it can easily reach a launch speed of 14 metres per second.

  The problem is just that of launching a projectile. It follows a parabolic path up to its maximum height and then descends. The minimum launch speed V that will achieve the vertical height h from a launch point at a distance x in front of the wall is given by the formula

  V2 = g (h + √(h2 + x2))

  Where g = 10 m/s2 is the acceleration due to Earth’s gravity. Notice some features of the equation that show that it makes sense: if gravity were made stronger (g gets bigger) then it is harder to jump, and the minimum launch-speed, V, must get bigger. Similarly, as the height of the wall, h, gets bigger or the distance away at take-off, x, increases, a larger launch-speed is needed to clear the wall.