So You Think You've Got Problems Read online

  The next puzzle is about rabbits. Sorry, I mean ribbits.

  5

  A BUNCH OF HOPS

  Ten lily pads are positioned in a straight line across a pond. A frog sits on the leftmost lily.

  At any stage, a frog can either jump to the next lily along, or hop over that lily and land on the lily two positions along.

  If the frog never goes backwards, how many different ways are there for it to reach the lily on the right?

  Let’s hop on. From an animal famed for its jumps, to one famed for its humps.

  The camel is a double celebrity in puzzle-land.

  First, it gives a bravura performance as the protagonist in a medieval puzzle about transporting grain. Secondly, it appears in a traditional puzzle about a family feud. (I’ll start with the first and get to the second later.)

  The gist of the grain transportation problem is this: what is the best strategy to get a camel to deliver grain from A to B, given that the more the camel walks, the more of the grain it will require as food? The first question of this type appeared in the foundational work of modern-day puzzledom, Alcuin of York’s eighth-century manuscript, Propositiones ad Acuendos Juvenes, or Problems to Sharpen the Young. A caravan of similar problems about walking and eating, or walking and drinking, trod over the dunes in the following centuries.

  6

  CROSSING THE DESERT

  Four Bedouin tribesmen, each with a camel, are standing together at the edge of a desert. The group must deliver an important package to a camp in the middle of the desert, four days’ camel-ride away. Camels can only carry enough water for five days. If the Bedouin cooperate, and are able to transfer water between camels in the desert without losing any due to spillage and evaporation, how is it possible for one of them to deliver the package and all of them return to their starting point with only 20 days’ supply of water?

  Alcuin’s camel problem is a brilliant example of a piece of fun that evolved into a serious area of mathematical research. In the twentieth century, the grain-guzzling camel was upgraded to a gas-guzzling machine. The ‘jeep problem’ asks you to find the best way to drive as far as you can from your source of petrol if you can only carry a finite amount of petrol at a time, but are allowed to deposit it at drop-off points and return to pick up more. This problem has obvious applications in exploration and warfare. Indeed, the first detailed analysis of the problem was funded in 1946 by the United States Army Air Forces. If your exploratory mission requires you to bring your own fuel – because you are traversing the Antarctic, flying over enemy territory, or discovering new areas of the solar system – you will grapple with exactly this type of logistical issue.

  7

  SAVE THE ANTELOPE

  You are a vet working in the Sahara when you hear that an endangered antelope has broken its leg 400 miles away from your practice. You decide to rescue the animal in your jeep, the specifications of which are:

  It does 100 miles to the gallon.

  The tank has a maximum capacity of a gallon of petrol.

  In addition to what’s in the tank, the jeep will carry four one-gallon canisters of petrol.

  There are no petrol stations between you and the injured animal, so in order to drive long distances you have to drop off canisters at certain points and return to pick them up later. You can only drop off canisters that are full. You can return to base as many times as you like to refuel.

  How do you reach the animal and bring it to your practice using only 14 gallons of petrol?

  Study of the jeep problem led to a staggering result, the kind you can’t quite believe even though the maths proves it’s true. Let’s imagine there is a service station with an unlimited supply of fuel, and you have a jeep with a finitely sized tank. It is possible to drive as far as you like from that service station using only petrol from there. In other words, you could theoretically drive all the way around the world in a Fiat Uno using only petrol that you took with you from London. (Like the problem above, the strategy relies on making many sorties to drop off fuel and pick it up later. If n is the number of miles you can drive on a full tank, you can get as far as n with no drop-offs. You’ll have to take my word that you can reach a distance of n (1 + 1/3) with a single fuel drop-off, you can reach n (1 + 1/3 + 1/5) with two drop-offs, and the more drop-offs you are able to make, the further and further you can travel, even though the extra distances you can go get smaller and smaller. Since the series 1 + 1/3 + 1/5 + 1/7 + … is a divergent series, meaning that by including more and more terms it can be made to exceed any finite value, the distance the jeep can travel will also exceed any finite value.)

  *

  The other classic problem about camels involves three children arguing about their inheritance. The kids are in a hump about who gets the humps. The puzzle in the form presented below dates from the nineteenth century. In recent years it has been reinvented as a morality tale about how a random act of generosity solves an apparently intractable problem.

  A man’s dying wish is that his herd of 17 camels is divided among his three children, such that the eldest child gets half of them, the middle child gets a third of them, and the youngest a ninth of them. The children are unable to decide how many camels each is to receive because of the arithmetical impossibility of dividing 17 by 2, 3 or 9 and getting a whole number of camels. (No camels are to be harmed during the solving of this problem.)

  In order to resolve the dispute, the children approach a wise old woman and explain the situation. She listens intently. To the children’s surprise, she fetches her own camel and gives it to them.

  ‘Now that you have 18 camels,’ she says, ‘you can divide them up in accordance with your father’s wishes.’

  The eldest child takes 9 camels, which is half of them, the middle child takes 6, which is a third, and the youngest takes 2, a ninth. However, 9 camels + 6 camels + 2 camels = 17 camels. In other words, one camel is left over. ‘I’ll take my camel back, thanks,’ says the old woman, and she and her camel walk away.

  The puzzle here is to explain the apparent contradiction in why a group of objects that cannot be cleanly divided into a half, a third and a ninth can be divided into those proportions when an extra object is added and then taken away. (I’ll explain how it works in the Answers section.)

  The wise woman who negotiates peace among feuding siblings makes for a charming parable, in which the eighteenth camel represents a fresh idea that resolves a deadlocked situation.

  She returns to help another family in a similar predicament.

  8

  THE THIRTEEN CAMELS

  A man leaves 13 camels to his three children in the following proportions: to the eldest, half; to the middle child, a third; to the youngest, a quarter. The children can’t decide how many each should get, because you cannot divide 13 by 2, 3 or 4 without inflicting severe pain on a camel.

  They consult a wise old woman to resolve their dispute. How does she fix it?

  Camels and horses are historically the two most popular riding animals. Have you ever wondered which is faster? Or slower?

  9

  CAMEL VS. HORSE

  Kamal has a camel and Horace has a horse. The friends are arguing about which animal is slower, so they decide to race them along a one-mile stretch of track, with the winner being the one that reaches the finish line last. They get in their saddles. But, predictably, they just stand there, since no one wants to start first and risk being the first to finish. An hour later, Ada shows up. She asks what’s going on. The men get out of their saddles and explain. Ada says a few words, at which point the men sprint to the animals, jump on, and race to the finish line as fast as possible.

  What was Ada’s advice?

  The following animal puzzle also involves two friends riding at speed in a straight line.

  10

  THE ZIG-ZAGGING FLY

  Two cyclists are racing towards each other along a straight road. When they are 20 miles apart, a fly on the nose of one of the
cyclists starts flying in a straight line towards the nose of the other cyclist. When it reaches the nose of the other cyclist, it immediately turns around and flies back towards the first cyclist, and it carries on flying between the cyclists’ noses as they approach each other.

  If the cyclists are both cycling at a constant speed of 10 miles an hour, and the fly flies at a constant speed of 15 miles an hour, how far has the fly flown when the cyclists meet?

  You can solve this the hard way or the easy way. The hard way is to calculate how far the fly travels before it touches the nose of the second cyclist, and then how far it travels back before touching the nose of the first cyclist, and so on, adding up a series of decreasing lengths.

  I’ll leave it to you to find the easy way.

  The zig-zagging fly is part of mathematical folklore because of an episode involving one of the twentieth century’s greatest scientists, John von Neumann, the Hungarian-American who made many important advances in economics, computer science and physics.

  On being told the puzzle by a friend, von Neumann solved it instantly in his head.

  ‘So you saw the trick,’ his friend remarked.

  ‘No,’ he replied. ‘I just summed the distances.’

  Geniuses can sometimes be a bit stupid.

  The next puzzle is also about insects moving in one dimension. And like the last one, its apparent unwieldiness unravels from a simple insight.

  11

  THE ANTS ON A STICK

  Six ants are walking along the edge of a 1m stick, as illustrated below. Aggie, Bozo, Daz and Ezra are walking from left to right as we look at the diagram. Carlos and Freya are walking from right to left. The ants always walk at exactly 1cm per second. Whenever they bump into another ant, they immediately turn around and walk in the other direction. When they get to either end of the stick, they fall off.

  Their starting positions from the left end of the stick are: Aggie 0cm, Bozo 20cm, Daz 38.5cm, Ezra 65.4cm and Freya 90.8cm. Carlos’s position is not known – all we know is that he starts somewhere between Bozo and Daz.

  Which ant is the last to fall off the stick? And how long will it be before he or she does fall off?

  Now for a puzzle involving rubber. It’s stretching, that’s for sure. Like the previous question, it is also about invertebrates travelling from one end of a long piece of material to the other.

  12

  THE SNAIL ON THE ELASTIC BAND

  A snail lies at one end of an elastic band that is 1km long, as shown below. It crawls towards the other end at a constant rate of 1cm per second. At the end of each second, the elastic band is stretched by a kilometre. In other words, when the snail has crawled 1cm the elastic is 2km long, when it has crawled 2cm the elastic is 3km long, and so on.

  Show how the snail eventually reaches the end of the elastic band.

  The snail sets off on a daunting task that appears to get even more dispiriting as each second passes. If it travels at only 1cm a second, and the elastic band stretches by 1km a second, our initial reaction is that the snail will always be getting further and further from its target destination rather than nearer to it. It’s a beautiful puzzle, however, because the snail does get there in the end. (We need to assume that the elastic band stretches uniformly as far as possible, that the snail never dies.)

  To get a sense of why the snail is not doomed to eternal crawling, consider its distance from the left end of the elastic band. (It’s a mathematical snail, so consider it as a point, starting at the band’s left edge.) After one second, the snail has travelled to a point 1cm along, which on stretching becomes a point 2cm along, since stretching the elastic from 1km to 2km has the effect of doubling the distance between any two points. After another second the snail is 3cm from the left end, which on stretching instantly becomes 4.5cm, since stretching the elastic from 2km to 3km has the effect of multiplying the distance between any two points by 3/2. In other words, the snail is carried forward by the stretching and covers an increasing distance each second, which gives us some hope that it might be able to traverse its ever-expanding floor.

  I included the snail puzzle because the result is spectacular, even though the full proof requires a piece of information that, while familiar to mathematicians, will not be known to everyone. Astute readers will notice, however, that this result can be deduced from material I have already shared in preceding pages.

  Now for some puzzles that require no technical mathematics at all.

  13

  ANIMALS THAT TURN HEADS

  Move a single matchstick so that the horse changes direction.

  The dog is facing left. Can you make him face right – while keeping his tail pointing upwards - by moving only two matches?

  The fish has a blueberry for an eye. Can you move the blueberry and three matches to make the fish point the other way?

  14

  BANISHING BUGS FROM THE BED

  Your bedroom is full of critters that can wriggle and creep along any solid surface, but cannot swim.

  You want to stop these pesky bugs getting into your bed. It’s easy to stop them getting up from the floor: you stand each leg of the bed in a bucket of water.

  But how do you stop them from crawling up to the ceiling and falling down on your sheets? A gutter like the one shown below won’t work since the bugs could fall onto the edge of the gutter and then crawl round and drop onto the bed.

  What construction will keep your bed bug-free?

  Suspending a canopy, or mosquito net, over the bed is not the solution, since the critters will crawl all over it, and might well crawl underneath it and up to the bed. Were you to find a way to hermetically seal this canopy to the floor, you would still have to open it to reach the bed, and when you did the bugs would be able to crawl through the opening too.

  The next puzzle might sound like a sitcom skit, but it has genuine mathematical content. Everyday language is full of ambiguities and assumed knowledge. Mathematical statements, on the other hand, are precise. The challenge of the puzzle is to apply mathematical rigour to a non-mathematical statement for comic effect. Let your inner pedant run free!

  15

  THE DUMB PARROT

  The owner of a pet shop never lies and is very precise with his words. A customer asks him about the parrot in a cage on his counter. ‘This bird is extremely intelligent,’ he replies. ‘She will repeat every word that she hears.’ The customer buys the bird. A few days later, however, the customer returns. ‘I’m furious! I spoke to the parrot for hours but the stupid bird has not repeated a single thing!’

  Given that the pet shop owner did not lie, how is this possible?

  Here’s one for nothing. The parrot could be dead. The Monty Python solution. Easy. But can you come up with at least four more reasons for the bird’s silence that – while possibly far-fetched – do not contradict the owner of the shop?

  So far, I’ve included puzzles involving mammals, arthropods, a fish, an amphibian and a bird. Only one class of animal is left.

  16

  CHAMELEON CAROUSEL

  A colony of chameleons on an island currently comprises 13 green, 15 blue and 17 red individuals. When two chameleons of different colours meet, they both change their colours to the third colour. Is it possible that all chameleons in the colony eventually have the same colour?

  Heron of Alexandria lived in the first century BCE. He is the most important mathematician to share a name with a common animal, which is surely enough to get him a mention in this chapter. Heron invented many ingenious contraptions that were way ahead of their time, including a vending machine, a mechanical puppet theatre and a steam engine. He also discovered a theorem that is the basis of many splendid puzzles. I’ll illustrate it here in the context of two houses and a road. It states that the shortest path from house A to house B via a point on the road is the one marked below, constructed by drawing a line to B', where B' is a reflection of B across the road. The line from A to B' is straight, so it is obviously the
shortest path from A to B', and it is also the same length as the path from A to B via the road. You are now equipped to solve the next puzzle, about an animal taking the optimal path to lunch.

  17

  THE SPIDER AND THE FLY

  A fly lands on the inside of a cylindrical glass tumbler, 2cm from the rim, as illustrated right. A spider is on the opposite side of the glass, 2cm from the bottom. The glass has a height of 8cm and a circumference of 12cm. If the fly remains stationary, what is the shortest distance the spider must crawl in order to reach it?

  Look again at the earlier image of the houses and the road. The angle at which the path from A hits the road is the same as the angle at which the path leaves the road for B. In other words, the picture illustrates the law of reflection of light, which states that when light hits a mirror, the angle of incidence is equal to the angle of reflection. (Imagine the road is a side view of a mirror, and A is a light source. The beam that leaves A and reflects to B is exactly the one illustrated by the black line.) Heron knew the law of reflection of light. Using his theorem about minimal distance, he became the first person to deduce that light always takes the shortest path.