So You Think You've Got Problems

by Alex Bellos

  Blue Blue Blue Red 1

  For the three-player version in which at least one person must guess, and all guesses must be correct, the strategy is as follows:

  If a player sees hats of two different colours, they stay silent.

  If a player sees two hats of the same colour, they guess the opposite colour.

  The eight possible combinations of hat colours on three players are RRB, RBR, BRR, BBR, BRB, RBB, BBB, RRR. Using the above strategy, the first six combinations will result in two players passing, and a third guessing their hat colour correctly. In the final two combinations, all three will guess incorrectly. In other words, in 6 of 8 equally likely arrangements of hat colours, at least one person is guessing and no one guesses wrongly, giving the prisoners a 75 per cent chance of survival.

  To get a feel for why this works, think about the number of guesses made across all combinations of hat colours. A guess will be made 12 times. Six times the guess will be correct (once each in RRB, RBR, BRR, BBR, BRB and RBB), and six times the guess will be wrong (three times each in both BBB and RRR). The correct guesses, however, are spread across six combinations while the six incorrect ones are spread across just two combinations. It’s like you’re dividing up the good stuff across as many boxes as possible, while squeezing the bad stuff into the smallest number of boxes you can. The same approach works with more than three players, with even more impressive results. As mentioned in the main text, if you play this game with 16 prisoners, the odds of survival are more than 90 per cent.

  48 THE MAJORITY REPORT

  You should adopt this strategy:

  [1] At the start of the recital, and whenever you see that the counter is at 0, commit the name you hear to memory and click once upwards, so the counter is on 1.

  [2] When the counter is on 1 or greater, click upwards if the name you hear is the same as the one in your memory, but click downwards if the name you hear is not the one in your memory. In both cases keep the same name in your memory.

  This strategy guarantees that the name in your memory after the list has been read out is the name that has been said more than half the time.

  To get a feel for why the strategy works, let’s see what happens if the warden reads out the following list: A B C A B A A B A. She reads nine names in total, made up of three distinct names.

  Name read out Counter Name in memory

  A 1 A

  B 0 A

  C 1 C

  A 0 C

  B 1 B

  A 0 B

  A 1 A

  B 0 A

  A 1 A

  The name in your memory at the end is A, which does indeed appear more than half the time.

  49 THE ROOM WITH THE LAMP

  Let’s begin with the situation with three prisoners, A, B and C. We also know that the lamp is off at the start.

  The crucial element in the strategy, from which everything else follows, is that one prisoner will have a different role from all the others. Let’s call him the Counter, since his job will be to keep track of who has been in the room, and then to announce to the prison warden that everyone has visited it. The gist is that the regular prisoners will turn the lamp on, and that they will be tallied by the Counter, who will turn the lamp off.

  Let’s say C is the Counter. The rules for him are:

  If the lamp is off, do nothing.

  If the lamp is on, turn it off.

  While the rules for A and B are:

  If this is the first time you’ve seen the lamp switched off, turn it on.

  In all other cases, do nothing.

  In this scenario, what happens is that the lamp is turned on at some stage by either A or B, after which C switches it off. Eventually either A or B will turn it back on again (if A switched it on first, then B will switch in on next, or vice versa). When C enters the room to see the lamp on for the second time he can be sure that both the other prisoners have been in the room, and he can holler at the top of his voice, ‘We have all visited the lamp room!’

  This strategy can be extended to 23 prisoners. If the Counter follows the above rule, which is to turn the lamp off when he finds it on, and all the other prisoners follow A and B’s rules, which are to turn the lamp on the first time they find it off but otherwise to do nothing, then once the Counter has seen the lamp on 22 times he knows that everyone has visited the room.

  Now let’s investigate what the prisoners need to do when they do not know the starting state of the lamp.

  The above strategy won’t work, because the first time the Counter sees the lamp on he won’t be able to tell if it has been turned on by a prisoner, or if it is still in its original state.

  Let’s say he enters the room when the lamp is on, and that this was its original state. The Counter will turn it off, as he must, but now for him to be sure that everyone has been in the room he must wait to see the lit lamp another 22 times. In other words, he must wait until he has turned the lamp off 23 times. However, the rule ‘wait until I see an on-lamp 23 times’ cannot be a solution to the problem, because if the lamp started in the ‘off’ state, it’s impossible for him to see the lamp lit 23 times.

  The way around this problem is to keep the same rules for the Counter but to tweak the rules for the other prisoners by insisting that they turn the lamp on twice. The rules become:

  If this is the first or second time you have seen the lamp off, turn it on.

  In all other cases, do nothing.

  The Counter can now be sure that once he has seen the lit lamp 44 times, everyone has been in the room.

  If the lamp was off at the start, every other prisoner would have gone in twice. If the lamp was on at the start, every other prisoner would have gone in twice except for one, who would have gone in once. It’s possible that all the prisoners had been in the room before the Counter saw the 44th on switch, but he can only know for certain when he sees the ‘on’ switch that 44th time.

  50 THE ONE HUNDRED DRAWERS

  Before we get to the solution, here’s an introduction to the maths of permutations. It’s going to make the prisoners’ strategy much easier to understand. Let’s say we have 10 objects and we want to reorder them. One way to describe this reordering is in a table:

  Initial position 1 2 3 4 5 6 7 8 9 10

  New position 4 8 5 6 9 1 10 2 7 3

  An easy way to understand the pattern described in the table is to represent it visually. In the table 1 → 4, 4 → 6 and 6 → 1. This forms a loop, or ‘permutation cycle’. The table can be illustrated thus:

  It’s plain to see that there are three cycles, one of length 3, one of length 2, and one of length 5. There are more than 3.6 million permutations of 10 objects, and they can contain cycles of length 1 to length 10.

  Now back to the prisoners. The strategy that they must take is the following. First, they must number themselves from 1 to 100 – that is, they should order themselves into Prisoner 1, Prisoner 2, Prisoner 3, and so on.

  They then must agree to abide by these rules when they enter the room:

  [1] Each prisoner heads for the drawer with their number on it and opens it first. In other words, the first drawer that Prisoner 1 opens is drawer 1, the first drawer that Prisoner 2 opens is drawer 2, and so on.

  [2] If a prisoner opens a drawer and it contains the name of another prisoner, say Prisoner k, the next drawer they open should be drawer k. In other words, if Prisoner 1 opens a drawer with Prisoner 32’s name in it, the next drawer he should open is drawer 32. If the drawer has Prisoner 67’s name in it, the next drawer he should open is drawer 67, and so on.

  These two rules set each prisoner on a path that is equivalent to a permutation cycle.

  Here’s why. Let’s imagine there are only 10 drawers and 10 prisoners. If the top row of the table on the left is relabelled ‘drawer number’ and the bottom row is relabelled ‘prisoner number’, the table now describes one possible arrangement of the prisoners’ names in the drawers. So, for example, in drawer 1 is the name of Prisone
r 4, in drawer 2 is the name of Prisoner 8, and so on.

  Drawer number 1 2 3 4 5 6 7 8 9 10

  Prisoner number 4 8 5 6 9 1 10 2 7 3

  If Prisoner 1 abides by the rules in this strategy, he begins by opening drawer 1, in which he finds the name of Prisoner 4. So he opens drawer 4, in which he finds the name of Prisoner 6, so he opens drawer 6, in which he finds his own name. He has gone through the cycle 1 → 4 → 6 → 1, and has found his own name after opening three drawers.

  We can see what happens to the other prisoners by following the cycles of this permutation (illustrated on the previous page.) Prisoners 4 and 6 will also find their names after three drawers, Prisoners 2 and 8 will find their names after two, and the others will find their names after five. In other words, the number of drawers a prisoner must open to find his own name is equal to the length of the permutation cycle he finds himself in. The strategy counts him round the cycle drawer by drawer, and he finds his name when he completes the cycle.

  This observation is also true when we increase the number of drawers and prisoners to 100.

  If there are 100 prisoners, and each prisoner can only open 50 drawers, every prisoner will find his own name if and only if all the permutation cycles have a length of at most 50. If the length of a cycle is longer than 50, a prisoner won’t be able to travel round it in only 50 drawer-openings.

  The strategy works, therefore, if no permutation cycles are longer than 50. In other words, in order to work out the chances of freedom for all the prisoners – that is, of everyone finding their names – we need to calculate the chances of there being no permutation cycles longer than 50 in a random permutation of 100 objects. (In other words, we need to divide the number of permutations of 100 objects that have no permutation cycles longer than 50 by the total number of permutations of 100 objects.) The maths here is too technical for a book like this one, so you’ll need to trust me that the chances of there being no permutation cycles longer than 50 are just over 30 per cent.

  The interesting behaviour of permutation cycles gives the prisoners an unexpectedly good chance of survival.

  Tasty teasers

  Riotous riddles

  1) They are two of a set of triplets.

  2) His grandchildren may have been childless, but they were still great!

  3) The plane is stationary at an airport a mile above sea level.

  4) She’s underwater.

  5) He is living in a very northerly town, in a place such as in Norway or Canada, where the sun does not rise for three months.

  6) The boxer was a dog.

  7) Molly is deaf.

  8) She worked at the job centre.

  9) She witnessed my passport application.

  10) He was piloting a plane heading west, flying faster than the rotational speed of the Earth.

  Cakes, cubes and a cobbler’s knife

  GEOMETRY PROBLEMS

  51 THE BOX OF CALISSONS

  The solution pops off the page once you visualise the image in three dimensions. Imagine that the image is not the aerial view of a hexagonal box of diamond-shaped calissons, but instead a sideways view of a stack of small cubes inside a large cube.

  It’s clearer when you shade each orientation a different way, as shown below.

  Each black calisson is the top, horizontal surface of a small cube. Each light grey calisson is a right vertical side, and each white calisson a left vertical side. If you were standing above the large cube and looked down, you would see a black 5 x 5 square made up out of all the tops of the small cubes. If you were looking at the cube from a position on the right, you would see a grey 5 x 5 square made up from all the right vertical sides of the small cubes. If you were looking at the cube from a position on the left, you would see a white 5 x 5 square made up from all the left vertical sides

  In other words, the black, grey and white diamonds each make up a face of the large cube, and therefore each of the colours must cover the same area. Since each colour contains the same number of calissons, we can deduce that the number of calissons in each orientation is the same.

  Furthermore, the number of calissons in each orientation will always be the same, irrespective of the arrangement in the box.

  52 THE NIBBLED CAKE

  The cut is the straight line that goes through the centre of the cake (shown below) and the centre of the missing slice.

  The insight needed to solve this puzzle is the realisation that any straight line through the centre of a rectangle divides the rectangle into two parts of equal area. Consider the cake before someone ate the rectangular slice. Any cut through the centre of the cake will divide it into two equal portions. Now consider what happens with the rectangular slice taken out. If the cut goes through both the centre of the cake and the centre of the space left by the slice, as shown above, it will again divide the cake into two equal portions. This is because the gap left by the eaten slice is also split into two, so the area of each of the two equal portions of cake will be reduced by the same amount, and remain of equal size. Although, of course, they don’t have the same shape, and one of the portions is made up of two pieces.

  53 CAKE FOR FIVE

  The solution is for each of the five slices to account for the same length of the cake’s perimeter. Since the perimeter of the cake is 20 units (as marked by the grid), then each of the five slices must have an edge that is four units long. So, choose a point on the perimeter and mark all the other points four units along:

  When you slice from the centre of the cake to each point you are left with five equally sized slices. You may have been trying to find five slices with the same shape – but the question did not ask for that. The slices look different, but contain the same amount of cake. (And the same amount of icing, regardless of whether or not icing is on the side of the cake.)

  We know that the slices are of equal size because the area of each slice is either a triangle or a combination of two triangles (as shown opposite). The area of a triangle is half its base times its height. The triangles that make up the slices all have the same height, which is the perpendicular distance from the perimeter to the centre (in this case 2.5 units). If the slice is a single triangle the base length is 4, and if the slice is two triangles, their base lengths add up to 4. So the area of all the slices is the same.

  In fact, the solution works for every possible whole number of cake slices. If you want to slice a square cake into 7 or 9 or n slices, divide the perimeter of the cake into 7 or 9 or n equal lengths. It’s essentially the same method you would use to divide a circular cake into any number of slices: divide the perimeter into equal sections and it all works out.

  54 SHARE THE DOUGHNUT

  Here are two solutions with three cuts. In both of them some of the pieces are very large and some are very small. For the solution with two cuts, take away any of the lines.

  55 A STAR IS BORN

  Did the title give it away? The solution creates another star out of the top triangle.

  56 SQUARING THE RECTANGLE

  The rectangle is 25cm by 16cm, so it has an area 400cm2. We know, therefore, that we are trying to create a 20cm by 20cm square. If you start the cut 20cm along the long side you may eventually deduce the solution, which is to use a ‘staircase’ cut. Cut the rectangle in a zigzag, as if drawing steps with 4cm height and 5cm width. The two pieces will now fit together perfectly.

  The butterfly keyboard of the 701 series IBM ThinkPad used this method. A staircase cut divided the keyboard into two pieces, and the edge between them zigzagged between the keys for 4 and 5, T and Y, H and J, and M and ,. When the laptop was folded up, the keyboard was a square, with 4 next to J, T next to ,, and so on. When the laptop was opened, the two pieces popped apart and fit together to make the rectangular keyboard, with 4 next to 5, T next to Y, and so on.

  57 THE SEDAN CHAIR

  58 FROM SPADE TO HEART

  59 THE BROKEN VASE

  One straight-line cut will give you two pieces, each with a single
straight side. Since the desired shape, a square, has four straight sides of equal length, you need to work out where you can make two cuts of equal length, as shown below.

  60 SQUARING THE SQUARE

  61 MRS PERKINS’S QUILT

  The smallest number of pieces is 11. A consolation prize if you got 12.

  62 THE SPHINX AND OTHER REPTILES

  63 ALAIN’S AMAZING ANIMALS

  64 THE OVERLAPPING SQUARES

  By extending the sides of the large square into the smaller one, we divide the small square into four. These four pieces have equal angles and side lengths, which makes them identical quarters. The area of the shaded part is therefore a quarter the area of the small square. Since the side of the small square is 2, the square’s area is 4, so the shaded part’s area is 1.

  65 THE CUT-UP TRIANGLE

  In diagram [1] I’ve drawn a dashed line from the intersection of the lines to the top vertex, dividing the area we want to find into A and B.

  In diagram [2], one of the shaded triangles has base l and area 7, and the other has base m and area 7. These two triangles have the same height, so we can deduce that l = m. (The height of a triangle is the perpendicular distance from the base to the opposite vertex.)