So You Think You've Got Problems

by Alex Bellos

  14 BANISHING BUGS FROM THE BED

  The ceiling gutters need to be positioned outside the line of the bed, and the other way around.

  15 THE DUMB PARROT

  If we are told that the owner of the pet shop never lies, the problem must lie with either the customer or the bird. Here are four possible answers:

  The bird is deaf. (She repeats every word she hears, but hears nothing.)

  The bird will repeat every word she hears exactly a year after hearing it.

  The bird is so intelligent she decided to ignore the owner because she deemed him too stupid.

  The customer is lying.

  16 CHAMELEON CAROUSEL

  No, the chameleons will never all have the same colour.

  Let the number of green, blue and red chameleons be G, B and R, and consider what happens when two chameleons meet. If green meets blue, both will become red. In other words, the total number of green lizards becomes G – 1, the total number of blue lizards becomes B – 1, and the total number of red lizards becomes R + 2.

  Now consider what happens to the difference between the number of lizards of each colour when green meets blue – in other words, what happens to G – B, B – R and R – G:

  G – B goes to G – 1 – (B – 1) = G – B

  B – R goes to B – 1 – (R + 2) = B – R – 3

  R – G goes to R + 2 – (G – 1) = R – G + 3

  So, when green meets blue (and by extension when any two chameleons of different colours meet), either the difference between any two colours stays the same, or it increases or decreases by 3.

  When all the chameleons in the colony are the same colour, the difference between any two colours (that’s G – B, B – R, and R – G) will be zero.

  Now let’s enter the numbers given in the question: 13 green, 15 blue and 17 red. In other words, the difference between green and blue is 2, between blue and red it’s 2, and between red and green it’s 4. We know that when chameleons meet, the difference between any two colours either stays the same or changes by 3. We can deduce that it is impossible for the difference between any two colours to be 0, since you cannot get to 0 from either 2 or 4 simply by adding or subtracting 3.

  17 THE SPIDER AND THE FLY

  Imagine the glass is made out of cardboard and unroll it, as shown below. From Heron’s theorem, the shortest path from the spider to the fly is the distance from the spider to X, where X is 2cm up the vertical from the horizontal edge of the cardboard. This distance is the hypotenuse of a right-angled triangle that has sides 6cm and 8cm. Using Pythagoras’ theorem for right-angled triangles (which states that the sum of the squares of the sides is equal to the square of the hypotenuse), we deduce that the distance in cm that the spider will travel is √(62 + 82) = √(36 + 64) = √100 = 10cm.

  18 THE MEERKAT IN THE MIRROR

  The vertical meerkat is looking at a vertical mirror, as illustrated here.

  First we’re going to work out where the mirror must be hanging, and how long it is, so that the meerkat can see its reflection perfectly framed.

  If the meerkat can see the top of its head, light from the top of its head must hit the mirror at a certain point and then rebound into its eyes. Let this point be A. Since the angles of incidence and reflection are equal, the height of A must be halfway between the height of the meerkat’s eyes and the height of its head.

  Likewise, if the meerkat can see its toes, light from the toes must hit the mirror at a point and then rebound into its eyes. Let this point be B. The height of B must be half the height of the meerkat’s eyes from the ground.

  If the meerkat’s reflection is perfectly framed, meaning that it can see no lower than its toes and no higher than its head, then the mirror must be positioned exactly between A and B. (Which means its length is equal to half the meerkat’s height.)

  We’ve worked out the position of the mirror without knowing how far the meerkat is from the wall. Which means that the meerkat can be any distance from the wall, and it will see its reflection perfectly framed. When the meerkat steps back, points A and B stay where they are, meaning that the animal’s reflection neither magnifies nor shrinks with respect to the mirror: it stays perfectly framed. Because the angles of incidence and reflection of light are always equal, the angle from A to the meerkat’s eyes is always equal to the angle from A to the top of its head, even though the size of this angle will increase as the animal steps backwards. Likewise, the angle from B to the meerkat’s eyes is always equal to the angle from B to its toes, whatever the size of that angle.

  19 CATCH THE CAT

  Ten days.

  Let’s begin with an explanation of the solution when there are only four doors. In the grid opposite, each row displays the possible positions of the cat on each day. The X marks the door I will open on each day.

  On Day 1 the cat could be behind any door, so there are cats in every cell. I open the second door along. If the cat is there, game over. But if the cat is not there, I can eliminate the chance that the cat will be behind the first door on Day 2, since the only way the cat could be there is if it was behind the second door on Day 1. On Day 2, therefore, the cat can only be behind three possible doors.

  On Day 2 I’ll open the third door along. If the cat is there, game over. If not, I can eliminate the chance that the cat will be behind the fourth door along on Day 3. I can also eliminate the chance that the cat will be behind the second door on Day 3, since to get there it would have had to have moved from either doors 1 or 3, both of which we know do not conceal a cat. We have reduced the choices to two. On Day 3 I open the third door. If the cat is there, game over. If the cat is not there, it must have been behind door 1, which means that by opening the second door on Day 4 I can guarantee that the cat is caught.

  Once you work out the four-door solution, it’s not so tricky to add an extra door: you can bag the puss in six days by opening the doors 2, 3, 4, 4, 3, 2 in that order.

  A pattern is developing: start at the second door along, then open the next door to the right on Day 2, and so on, until you get to the penultimate door. Then return. When there are seven doors, try them in this order: 2, 3, 4, 5, 6, 6, 5, 4, 3, 2. This will ensnare the furtive furry one.

  If the number of doors is n, you can always catch the cat in (n – 2) x 2 days.

  20 MAN SPITES DOG

  The postman would do well to noisily circumnavigate the house, since if the dog is always straining at the leash to be as near to him as possible, it will end up winding its leash around the tree, thus reducing the effective length of the leash until the path is safe.

  21 THE GERM JAR

  Thirty minutes.

  The initial state has a single X and 30 Ys. After one minute, an X will have eaten a Y and doubled, while all the remaining Ys will have doubled. In other words, the population of X is 2 while the population of Y is 2 x 29. A useful way to visualise this, illustrated right, splits the population into two: each half has a single X and 29 Ys. A minute later the population can be split in four batches, each with a single X and 28 Ys, and a minute after than into eight (or 23) batches, each with a single X and 27 Ys. At the end of the twenty-ninth minute there will be 229 batches, each containing a single X and a single Y. After 30 minutes there will be no Ys left at all.

  22 THE FOX AND THE DUCK

  The fox’s best strategy will always be to position itself on the shore as close to the duck as possible. Conversely, the duck’s best strategy is to position itself as far as possible from the fox.

  We saw that if the duck heads in a straight line for the shore, the fox will catch it. So that plan is out.

  But consider what happens when the duck travels in concentric circles around the centre of the lake. The fox will also travel in a circle round the lake, trying at all times to be at the closest point to the duck.

  Whether or not the fox can keep up with the duck, however, depends on the size of the circle travelled by the duck. If the circular path is close to the edge of the lake, the
fox will have no trouble marking the duck. However, if the circle is a small one at the centre of the lake, the duck will be able to go one full rotation faster than the fox can.

  In fact, since the duck paddles at a quarter of the speed of the fox, both animals will take the same time to make a full rotation when the duck travels a quarter of the distance the fox does. This happens when the radius of the duck’s circle is r⁄4, a quarter of the radius of the lake. If the duck paddles in a concentric circle with a radius of less than r⁄4, the fox will not be able to keep up with it and will slowly lag behind.

  Imagine now that the duck is travelling in a concentric circle with a radius just under r⁄4 (i.e. just under 0.25r). The fox will lag behind, and after a certain time the duck will be at the position on that circle that is opposite the position of the fox. At that moment the duck will be at a distance of just under 1.25r from the fox, and just over 0.75r from the opposite shore. If the duck makes a direct line to the shore now, it will have to travel this ‘just over 0.75r’ in the same time as the fox runs πr, or 3.14r. Since the fox is four times faster, the duck will make it if ‘just over 0.75r’ is less than which is about 0.78r. Which is possible. Let’s say the duck is travelling in a circle of, say, 0.24r. It will always be 0.76r from the shore, so if it starts for the shore when it’s opposite the position of the fox, it will reach land before the fox can catch it.

  23 THE LOGICAL LIONS

  If there are 10 lions, the sheep survives.

  But if there are 11 of them, the sheep will die.

  We solve this problem by seeing what happens when the pen has a single lion in it, and then increasing the number by one each time.

  One lion, one sheep:

  With a single lion in the pen, the sheep doesn’t stand a chance. The lion will gobble it up. Result: the sheep dies.

  Two lions, one sheep:

  Neither of the lions will risk eating the sheep, since if one of them did it would get drowsy and then be eaten by the other lion. Result: the sheep lives.

  Three lions, one sheep:

  One of the three lions will happily eat the sheep, because this lion knows that even though it will get drowsy, none of the other two lions will dare eat it. If one of the other lions did eat the sheep-eater, that lion would then get drowsy and be eaten by the last remaining lion. Result: the sheep dies.

  Four lions, one sheep:

  If one of the four lions eats the sheep, it will become drowsy and the situation becomes equivalent to the situation with three lions, only with the drowsy lion in place of the sheep. Since three lions/one sheep is a scenario in which the sheep dies, none of our four logical lions will eat the sheep. Result: the sheep lives.

  You will hopefully see the pattern now. Whether or not a lion eats the sheep depends on the scenario in which there is one less lion. If the sheep in the scenario with one less lion lives, then the lion will eat the sheep, but if the sheep in the scenario with one less lion does not live, the lion will not eat the sheep.

  In other words, the mortality of the sheep flips between alive and dead each time you increase the number of lions by 1. If there is an odd number of lions the sheep will live, and if there is an even number the sheep will die. Since the problem states 10 lions, the sheep will live.

  24 TWO PIGS IN A BOX

  The smaller, subordinate pig eats better. Strength is sometimes a weakness.

  This paradoxical conclusion arises because the small pig quickly realises that when it does press the lever, all it is doing is feeding the big pig, since the big pig will be waiting by the bowl to eat up all the food. Once the big pig is by the bowl, the small pig will not be able to push it out of the way.

  The small pig has no incentive to pull the lever, so it doesn’t. That job therefore falls to the big pig. When the big pig pulls the lever, the small pig will be waiting by the bowl and will eat as much as he can before the big pig arrives and pushes him out of the way. Since the big pig will get some food, he does have some incentive to press the lever, even though the small pig will often get most of what’s in the bowl.

  25 TEN RATS AND ONE THOUSAND BOTTLES

  Our method will be to feed each rat a mixture taken from different bottles, and to work out which is the poisoned bottle by noting which rats survive and which rats die by the end of the hour. The rats must be fed these mixtures simultaneously, so that after exactly an hour we can see the death toll and deduce which bottle has the poison.

  We have 10 rats. After an hour they will be either alive or dead. There are exactly 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 210 = 1,024 possible combinations of 10 alive or dead rats, since there are 10 rats and every rat can be one of two things, alive or dead. The fact that there are 1,024 possible combinations and only 1,000 bottles means that we have more than enough combinations to specify individual bottles.

  The question now becomes how to make each unique combination of live and dead rats refer to a unique bottle. The answer is that we use binary numbers – the number base in which only 0 and 1 are used. In the usual decimal number system, the digit furthest on the right is in the ‘units’ column, and then moving left we have the ‘tens’, the ‘hundreds’, the ‘thousands’, and so on, each one being 10 times the one before. In the binary system, the units column counts 1, but moving leftwards the columns count 2, 4, 8, 16, and so on, doubling each time, as shown below.

  Decimal Binary

  1 1

  2 10

  3 11

  4 100

  … …

  998 1111100110

  999 1111100111

  1000 1111101000

  Our first job is to order all the bottles in binary notation from 1 to 1111101000. We need them all in ten-digit form, so 1 is 0000000001, and 2 is 0000000010.

  We also order the rats: we have a ‘units’ rat, a ‘twos’ rat, a ‘fours’ rat, an ‘eights’ rat, and so on up to a ‘five hundred and twelves’ rat.

  Finally, we give the wine to the rats.

  The units rat gets a cocktail that contains a sip from every bottle whose binary form has a 1 in the units column.

  The twos rat gets a cocktail that contains a sip from every bottle whose binary form has a 1 in the twos column.

  The fours rat gets a cocktail that contains a sip from every bottle whose binary form has a 1 in the fours column.

  And so on.

  If the units rat dies, we know that the binary representation of the poisoned bottle has a 1 in the units column.

  If the units rat survives, we know that the binary representation of the poisoned bottle has a 0 in the units column.

  If the twos rat dies, we know that the binary representation of the poisoned bottle has a 1 in the twos column.

  If the twos rat survives, we know that the binary representation of the poisoned bottle has a 0 in the twos column. And so on.

  In other words, in a ten-digit binary number that determines which bottle has the poison, the dead rats are the 1s and the live rats are the 0s. Voila!

  The reason that not all the rats will die is because if they did they would have encoded the binary number 1111111111, which is 1,023 in decimal, and our bottles only go up to a thousand. (In fact, it is possible to ensure two rats survive. To do this we need to order the bottles in such a way that excludes the ten binary numbers with only one 0, as well as the binary number with all 1s.)

  Tasty teasers

  Gruelling grids

  1)

  2)

  3)

  4) Here’s one shape that works:

  5) There are 20 squares. Orthogonally: nine 1 x 1s, four 2 x 2s (of which only two are shown below; the other two are found by moving these squares into the empty corners), and one 3 x 3. Diagonally, four at a 45 degree angle and two at the lesser angle.

  6)

  I’m a mathematician, get me out of here

  SURVIVAL PROBLEMS

  26 FIRE ISLAND

  Take a piece of wood from a tree near the leading edge of the fire and light it. Careful
ly walk to a point on the eastern side of the island – say 100m from the coastline. Set the forest there alight. Make sure you stay to the west of this new fire, which, aided by the wind, will move eastward at 100m per hour. The fire will burn out once it reaches the coast, providing you with 100m of safe space – although be careful not to burn your feet in the ash. The items in your rucksack were red herrings, although the Bible might come in handy as a mat.

  27 THE BROKEN STEERING WHEEL

  It is possible to turn right by turning left.

  28 WALK THE PLANK

  To save the British, a = 1, b = 11.

  To save the French, a = 9, b = 29.

  In Bachet’s version of the Josephus problem, with 30 passengers, the mnemonic Mort, tu ne falliras pas, En me livrant le trépas!! encodes the solution with its vowels. If a = 1, e = 2, i = 3, o = 4, and u = 5, the order of the vowels reveals the order in which to position the passengers around a circle. Let’s call the 15 people you want to save Friends, and the 15 you want to drown Enemies. The first four vowels in the mnemonic are o, u, e and o (4, 5, 2 and 4), so you start the ordering around the circle with 4 Friends, then 5 Enemies, then 2 Friends, then 4 Enemies, and so on.

  29 THE THREE BOXES

  [1] The key is in the white box.