So You Think You've Got Problems Read online

  18

  THE MEERKAT IN THE MIRROR

  A meerkat is looking at itself in a wall mirror. It sees its reflection perfectly framed: the top of its head reaches the top of the mirror and its feet reach the bottom.

  What happens when the meerkat steps back from the mirror? Does it see less of itself in the mirror, or do gaps open up above its head and beneath its toes?

  Assume that the wall mirror is vertical, and that the meerkat is rod-straight upright when looking at itself.

  Meerkats lend themselves well to the previous problem since the one thing everyone knows about them is that they like to stand up. What about the behavioural traits of real cats? They are mischievous, independently minded and like to move around at night.

  19

  CATCH THE CAT

  A straight corridor has seven doors along one side. Behind one of the doors sits a cat. Your mission is to find the cat by opening the correct door. Each day you can open only one door. If the cat is there, you win. If the cat is not there, the door closes, and you must wait until the next day before you can open a door again. The cat is restless and every night it moves to sit behind another door. The door it moves to is either the one immediately to the left or the one immediately to the right of where it was previously.

  How many days do you need to make sure you will find the cat?

  The question is asking you to find a strategy that guarantees you will catch the cat in a fixed number of days, whichever door it starts behind and wherever it moves in the night. The key to the solution is to begin with a smaller number of doors, find the pattern, and then increase the number of doors. I’ll get you started. Imagine there are only three doors. If you open the middle door on two consecutive days you are guaranteed to get the cat, since if the cat is not behind the middle door on day one, it must be behind either of the end doors. And if it is behind either of the end doors on day one, it has no option but to move behind the middle door on day two. If there are four doors, you can catch the cat in four days. I’m not going to explain the strategy, but you will purr with delight when you work it out. Remember, the cat will only move to a door immediately to its right or its left, and it may return to a door it was behind previously.

  Predatory aggression is a common theme in puzzles. Usually, but not always, felt by frustrated solvers.

  20

  MAN SPITES DOG

  A house is surrounded by a five-foot-high wall. Its front door can only be reached by a path, which you enter from the main gate.

  A postman arrives at the gate. He sees a dog in the garden. The dog sees him, springs up and runs to the gate to attack him, stopped only by its leash, which is tied to a tree. The dog is barking and straining at the leash, trying to get as near to the postman as possible. The dog will attack the postman if he walks along the path.

  How might the postman manage to deliver the letter safely?

  21

  THE GERM JAR

  X and Y are two types of germ that exhibit the following predator-and-prey behaviour.

  X germs: a single X will eat one Y per minute if any are available. Once an X has eaten a Y, the X multiplies to become two Xs.

  Y germs: a single Y will double every minute into two Ys, unless it is eaten by an X.

  In other words, an X only doubles after devouring a Y, but a Y will double on its own. A scientist has a jar containing 30 Y germs, and places inside it a single X germ.

  After how many minutes are there no more Y germs left in the jar?

  A famous recreational problem about predation concerns a man thrown into a circular arena with a hungry lion. If the man and the lion have the same maximum running speed, and both have limitless energy, will the lion eventually catch the man or can the man always evade the lion?

  The problem is notable not only because it captured the imagination of the mathematical community, but also because for several decades people kept getting it wrong. The German mathematician Richard Rado proposed the problem in 1932. (Like the protagonist of the puzzle, Rado, a Jewish man in Berlin, was also fearing for his life. A year later he fled the Nazi regime to Britain.) Originally, the prevailing view was that the man was doomed, that in a bounded circular arena he would not be able to escape the jaws of the hungry lion. Yet in the 1950s, the Cambridge professor Abram S. Besicovitch discovered a strategy in which the man would, in fact, be able to dodge the lion ad infinitum. The man was saved. While the proof is too involved for this book, the strategy is easy to understand: the man will evade capture if, for each time interval, he runs in a line perpendicular to the line between him and the lion, choosing the direction that keeps him closer to the centre point of the circle.

  Here’s a simpler challenge involving a circular arena and a peckish predator.

  22

  THE FOX AND THE DUCK

  A duck is floating in the middle of a circular lake. A fox is prowling round the bank. The fox can run four times faster than the duck can paddle, and the fox will always position itself in the best possible spot on the side of the lake to catch the duck.

  The duck can only fly from dry land. Is there a way for the duck to reach the side of the lake – and fly to safety – without being caught by the fox?

  At first glance, the duck’s prospects don’t look good.

  Let’s say that the fox is at the top of the lake, as shown in the image opposite. If the duck decides to paddle in a straight line as fast as it can in the opposite direction to the fox, then by the time it gets to the shore the fox will be waiting. We can work this out with some basic geometry. The duck’s path is a distance of r, the radius of the lake. The fox’s path is a distance of πr. (It travels half the circumference of the lake, and the circumference of a circle is 2πr, where the value of π is approximately 3.14.) The fox thus needs to run a distance that is 3.14 times greater than the distance the duck has to paddle. Since the fox is four times faster than the duck, it will get there first.

  The challenge is to plot a path that allows the duck to step onto land at a point the fox can’t get to quick enough.

  John von Neumann – the speed-solver of the ‘zig-zagging fly’ (Problem 10) – is considered, together with the economist Oskar Morgenstern, to be the founding father of game theory, the mathematical analysis of decision-making. The games von Neumann was originally thinking about were parlour games, but as the subject expanded it found wide applications in many fields, such as psychology, philosophy, politics, sociology and, of course, recreational puzzles. Game theory models the behaviour of individuals who interact according to certain rules and aim to ‘win’ – in other words, to get the best possible outcome for themselves. Such as the lions in the following puzzle.

  23

  THE LOGICAL LIONS

  Ten lions are in a pen. Their favourite food is sheep. The lions know, however, that any lion that eats a sheep will become drowsy, and is likely to be eaten by another lion if one is nearby. A lion that eats a lion will also become drowsy, and thus also risks being eaten.

  A sheep is put in the pen. Each of the lions is desperate to eat it, but will only do so if they are sure they will not be eaten themselves.

  What happens to the sheep?

  (Extra question: what happens if there are 11 lions in the pen at the start?)

  To avoid ambiguity, if the sheep is eaten, it must be eaten by one lion only, and not shared between the pack. We can assume that lions will always act in their best interests and are impeccable logicians.

  Pigs are highly intelligent creatures, even the ones that don’t have PhDs. In 1979, Basil Baldwin and G. B. Meese, of the Babraham Institute, Cambridge, conducted an experiment involving pigs, as described in the following puzzle. The experiment became famous because it showed that game theory perfectly modelled the animals’ behaviour.

  24

  TWO PIGS IN A BOX

  Two pigs live in a box: a bigger, dominant one, and a smaller, subordinate one. The box is arranged such that when a lever is pressed at one end,
food is dispensed in a bowl at the other. The distance between the lever and the bowl means that the pig pressing the lever will get to any newly dispensed food second.

  Which pig eats better?

  After all this talk of food, here’s some wine to wash down the final puzzle in this chapter.

  25

  TEN RATS AND ONE THOUSAND BOTTLES

  You have inherited a collection of one thousand bottles. All the bottles contain wine except one, which contains poison. The only way to discover what’s in a bottle is to drink it. If you drink poison, however, you die.

  Thankfully, you have 10 rats. If a rat sips poison, or poison mixed with wine, it will die after exactly one hour. If a rat drinks wine, it survives. How do you determine which bottle is poisoned exactly one hour after the first rats are given their first sips?

  With unlimited time, 10 rats are plenty to help you discover the poisoned bottle. For example, you could separate the thousand bottles into 10 batches of 100, and allocate each batch to a different rat. Let the rats take a sip from every bottle in their batch. An hour later one rat will be dead, narrowing the options for the poisoned bottle to the 100 bottles in that rat’s batch. Separate these 100 into nine smaller batches, one each for the nine remaining rats. Again, a dead rat will pinpoint the contaminated batch. Carry on in this way and the rats, now metaphorically as well as literally rat-arsed, will soon narrow the options to a single poisoned bottle.

  Poisoning rats in series, however, is unnecessarily long-winded. The solution is to poison in parallel, in other words to get the rats to quaff contrasting concoctions concurrently. At least one rat will remain alive during your attempt at mass intoxication.

  Dodging death sets us up for the next chapter. It begins with a curious animal, perhaps the best known puzzler of all.

  Tasty teasers

  Gruelling grids

  1) What is the smallest number of straight lines you need to draw across a 3 x 3 grid so that every cell in the grid has at least one of the lines passing through it? The answer is less than three. Draw your solution.

  2) What is the smallest number of straight lines you need to draw across a 4 x 4 grid so that every cell in the grid has at least one of the lines passing through it? The answer is less than four. Draw your solution.

  3) Place five stones on the 8 x 8 grid shown below in such a way that every square consisting of nine cells has only one stone on it

  The remaining questions all ask you to draw a pattern on a grid of 16 dots, shown below.

  4) A polygon is a shape in which each side is a straight line. The H polygon below has 12 sides and the K has 13. Draw a polygon on the grid with 16 sides. (Note: each side of the polygon must join two dots. Lines cannot overlap. The shape, which need not resemble a letter, must have no gaps in its outline, and each dot can be passed through at most once.)

  5) Below is a single square made by joining four dots in the grid. Find the other 19 squares that can be made by joining four dots. (Lines connecting the four dots may pass through other dots.)

  6) The illustration below shows a way to connect 14 of the dots with lines, such that the angle at every dot is acute (i.e., less than 90 degrees). Find a way to connect all 16 dots so that there is an acute angle at every dot.

  I’m a mathematician, get me out of here

  SURVIVAL PROBLEMS

  The most famous riddle of the ancient world was also a high-stakes challenge: get it wrong, and you were eaten alive.

  What walks on four legs in the morning, two legs at noon and three legs in the evening, asked the Sphinx, the mythical lion-woman, to travellers approaching Thebes. Oedipus replied: ‘Man, who crawls on all fours as a baby, then walks on two feet as an adult, and then uses a walking stick in old age.’ Oedipus’ reward for solving the puzzle was freedom to enter Thebes, where he would eventually kill his father by accident, marry his mother and blind himself by sticking pins in his eyes. Maybe he should have given the Sphinx the wrong answer – he would have saved everyone a lot of trouble.

  (In some tellings of the Oedipus story, the Sphinx has a second riddle: There are two sisters: one gives birth to the other and she, in turn, gives birth to the first. Who are the two sisters? The answer will be revealed in the following pages.)

  Jeopardy adds spice to a puzzle. In this chapter you will also use your wits to save your skin. Just as Oedipus faced off against the Sphinx, you will go mano a mano against evil executioners, malevolent monarchs and perverse prison wardens, each one setting a challenge more fiendish than the last. You – and others – will find yourselves in all manner of apparently impossible pickles: in a dungeon, on a boat, in handcuffs, stranded on distant islands and incarcerated in some really weird jails. Some of these problems are about escape. Some are about survival. All of them are about having a plan.

  26

  FIRE ISLAND

  You are marooned on a rectangular-shaped island that stretches 500m from north to south and 3km from west to east. The island is surrounded by high cliffs, and is completely covered in dry, combustible forest. The wind is constant and always blows from west to east. On Monday at noon the entire western edge of the island catches fire. The fire, aided by the wind, moves 100m eastward every hour. If you are trapped by the flames, or if you jump off the island, you will die. In your rucksack you have a compass, a calculator, a penknife and a copy of the Bible.

  How do you survive until Wednesday?

  27

  THE BROKEN STEERING WHEEL

  You are in a getaway car driving through empty wasteland. Suddenly you realise that the steering wheel is broken: it does not turn right. You can only travel in two directions: straight ahead and left.

  You are at point A, moving in the direction of the arrow. How do you drive to your hideout at X on the other side of the lake without going beyond the demarcated area (shown by the dotted line)? You are not allowed to reverse, get out of the car or cross the lake.

  Puzzles can save your life. That’s why they’re worth studying, wrote the French mathematician Claude-Gaspard Bachet de Méziriac in 1612, in what is generally regarded as the earliest book of recreational mathematics, Problèmes Plaisants et Délectables Qui Se Font Par Les Nombres (Amusing and Entertaining Problems That Can Be Had With Numbers). Dismiss recreational problems at your peril, he says, since they will come in handy in all manner of life-and-death situations.

  Consider Titus Flavius Josephus, a Jewish scholar and one of several men hiding in a cave during the Siege of Yodfat in 67 CE. Rather than die at the hands of the enemy, explains Bachet, the men decided to kill themselves. Josephus volunteered a ‘fair’ plan about how they might carry out the collective suicide. The men should stand in a circle, count out a fixed number, kill the person counted out; count out the same number again, kill that person, and so on, counting out until no one was left. Thanks to his mathematical nous, Josephus’ magnanimous suggestion was in fact a reverse-engineered guarantee of his own safety. ‘Josephus chose himself such a good starting position,’ writes Bachet, ‘such that if the slaughter continued to the end he would be the last one alive, or maybe he would save a couple of his most trusted friends.’

  Even though there is no clear evidence that Josephus did indeed use this method to survive the siege, ‘counting-out’ puzzles are called ‘Josephus problems’. They were among the most popular recreational brainteasers of the Renaissance, and the first famous puzzles in which the aim is evading execution. In Problèmes, Bachet sets out the most common variation. A boat has 30 passengers. Half of them are to be thrown overboard. If you know which 15 you want to drown, how do you arrange the 30 in a circle such that if every ninth person is thrown overboard, the first 15 counted out are your preferred choices? (The solution is encoded in Bachet’s phrase ‘Mort, tu ne falliras pas, En me livrant le trépas!’ – ‘Death you will not fail to deliver my demise!’ Can you work it out? The answer is in the back.)

  Here’s a more manageable variation with only 10 on deck.

  28<
br />
  WALK THE PLANK

  Pirates have captured five British and five French sailors. The pirate captain decides that five of the captives must be thrown into the sea. The sailors are positioned in a circle in this order:

  The captain will start with an arbitrary sailor, in position a, and count out clockwise every bth sailor. He will save the first five counted out, and the others will face a watery death.

  In order to save the five British sailors, what are a and b?

  In order to save the five French sailors, what are a and b?

  Let position 1 be the 12 o’clock position occupied by the French sailor, with the other positions counted clockwise from there.

  (Note that when a person is counted out they are not included in any subsequent count.)

  Death by drowning features in almost all Western Josephus problems. In Japan, however, the problem is told as a fable about hubris. A farmer has a certain number of children with his first wife and a certain number with his second. In order to decide who inherits his wealth, the children are arranged in a circle and every tenth child is counted out until only one – the single heir – is left. One of the mothers starts the counting, aiming for her child to be the winner, but she makes a mistake due to over-confidence, and ends up counting out all her own kids.