So You Think You've Got Problems
Page 5
But for the executioner to answer ‘yes’, one of the alternatives must be true. It cannot be the first one, since the executioner has not answered ‘no’. It must then be the second one, so the executioner has agreed to spare your life. If your brain is still in working order, try part [2].
*
Puzzles involving the playful interplay of true and false statements date from the nineteenth century. They have become particularly relevant in the past few decades with the growth of computer science. All programming languages rely, at a basic level, on the logic of truth values.
At the turn of the twenty-first century a puzzle in a computer science PhD caused huge excitement. Not only did it reveal an astonishing result, it also had important practical applications. The puzzle is a wonderful example of a simple problem at the cutting edge of research that captured the imagination of the entire mathematical community. Before we get there, though, a warm-up puzzle.
47
THE RED AND BLUE HATS
Two prisoners are in a cell. The warden announces that they will play a game. A red or blue hat will be placed on each of their heads, with the colour of each hat determined by the flip of a coin. Each prisoner will be able to see the other one’s hat but not their own.
Once the prisoners see each other’s hats, they must guess the colour of their own hat. They will both be freed if at least one of them guesses correctly.
The prisoners are allowed to discuss a strategy before the game begins, but once the hats are on, no communication of any sort is allowed.
What strategy guarantees their freedom?
If the game involved only one prisoner guessing the colour of his hat, it would, of course, be an impossible challenge. The chance of that prisoner guessing correctly is 50 per cent, since there is an equal chance of it being either red or blue. Yet once you add a second player, the chance of at least one correct guess rises to 100 per cent, with the right strategy.
In 1998 Todd Ebert, a computer science graduate student at the University of California, included a version of the previous puzzle in his PhD thesis. He upped the number of prisoners to three. Within a few years his problem had been discussed around the world, and the buzz surrounding it was even reported in the pages of the New York Times. I’ll include it here as an extra puzzle.
The set-up is the same: Three prisoners are in a cell. The warden announces that they will play a game. A red or blue hat will be placed on each of their heads, with the colour of each hat determined by the flip of a coin. The prisoners will be able to see one another’s hats but not their own.
Here’s the twist: Once they see each other’s hats, at least one prisoner must guess the colour of his own hat. If any guesses are wrong, all three prisoners will be killed.
In other words, up to two prisoners can avoid guessing their hat colour by staying silent. Yet at least one of them needs to guess, and needs to guess correctly. Only if there are no incorrect guesses will they all survive.
As before, the prisoners are allowed to discuss what to do beforehand, but once the hats are on no communication is allowed. One obvious strategy would be for the prisoners to designate one person to always guess, and for the other two to always stay shtum. This strategy gets you a 50 per cent chance of survival, since the designated player will guess correctly half the time. Indeed, on first hearing the problem most mathematicians assumed that it was impossible to improve on 50 per cent.
Amazingly, however, there is a strategy that guarantees a survival rate of 75 per cent. (The solution is in the back.) If you play the game with 16 prisoners the result is even more stunning: the odds of survival are more than 90 per cent. The puzzle was posted on chat rooms and newsgroups and became one of the first viral puzzles of the internet age.
Fascinating and powerful ideas from computer science can be brilliantly illuminated with a good puzzle. The generalised solution to the hats problem, for example, involves the mathematics of Hamming codes, a type of error-correcting code developed for telecommunications in the 1950s. The Boyer-Moore majority vote algorithm, meanwhile, is an ingenious way to remember information with barely any computer memory, and is the solution to the following teaser.
48
THE MAJORITY REPORT
A prison warden reads out a long list of names. Some names are read out more than once. In fact, one of the names appears in the list more often than all the other names combined. (In other words, more than 50 per cent of the time a name is called out, it’s this name.) If you can identify this ‘majority name’ you will be freed.
You are not allowed a pencil and paper, so you have no way of tallying all the names. You have also suffered a knock on the head, which has resulted in an inability to keep more than one name in your working memory at any one time. That is to say, on hearing a name you can choose to remember it, but if you do so then you instantly forget the name that was in your memory before. Or you can also choose not to remember it, thus retaining the name that was in your memory before.
The prison warden allows you to use a single clicker-counter. It is set to 0. You can click up the numbers, and down the numbers, at will.
What strategy guarantees that you identify the majority name? You can assume that once you have decided on a strategy, you will not forget it as the warden begins her recital.
If there were only two different names on the list, say Smith and Jones, one strategy that would work would be to click the counter upwards on hearing Smith, and downwards on hearing Jones. Once all the names had been read out, the clicker would display a positive number if Smith was said more times, and a minus count if it was Jones.
With three or more names, the strategy is a little more complicated. You can’t just count up for one name and down for another name, since that leaves other names unaccounted for. At each step in the recital you have three pieces of current information: the name you hear, the name in your memory (which may or may not be different from the one you just heard) and the reading on the clicker. How do you combine these three pieces of information to find the name that is read out more than half the time? It is incredible to discover what can be ‘remembered’ with almost no memory at all.
Puzzles that originated in computer science are often about information. Storing it, as above, and communicating it. Prisons are convenient venues for this type of puzzle, because incarceration means restricted access to information. In the two final problems in this chapter, a group of prisoners must think up a strategy for a challenge in which the restrictions on communication are so comically severe the thought of even meeting the challenge is mind-boggling.
49
THE ROOM WITH THE LAMP
A room in a prison has a lamp. The lamp is either on or off, and can only be switched on or off by someone in the room.
The prison warden decides that every day he will select one of 23 prisoners to go into the lamp room, after which they will return to their individual cells. The warden’s selection is random, meaning that he might choose the same prisoner to go into the room several days in a row, or months might pass before a prisoner is chosen. In the long run, though, every prisoner will go into the lamp room the same number of times as every other prisoner.
The warden tells the prisoners that he will free them all as soon as one of them says ‘we have all visited the lamp room’ – provided this statement is correct. If a prisoner makes this statement, but at least one prisoner hasn’t visited the room, the warden will have all of them killed.
Before the warden chooses his first prisoner, all of the prisoners are brought together to discuss a strategy. Once they decide on their plan, they will return to their cells and will no longer be able to communicate with each other from there. The only way they can send each other messages is via the lamp: they can either leave it on or off. We can assume that no one else goes in the room apart from the prisoners, and that the lamp is always in working order.
Can you think of a strategy that will allow one of the prisoners to say, with
100 per cent certainty, ‘we have all visited the lamp room’?
Note that we do not know whether the lamp is on or off to begin with. To get you on your way, let’s simplify the problem. Assume, for a moment, that the lamp is off at the start and that there are just two prisoners, A and B.
The only way that the first prisoner to enter the room can let the other one know he has been there is by turning the switch to ‘on’. Let’s say A is the first prisoner in the room. He sees the lamp is off, and he turns it on. If he’s chosen again he leaves the lamp on, and continues to do so if he makes further visits. When B eventually enters the room, he will know that A has been there, since the lamp will be lit and only A could have turned it on. B can say with 100 per cent certainty that ‘we have all visited the room’. With two prisoners, therefore, the rule for what you do to the lamp can be summarised as:
If it is off, turn it on.
If it is on, leave it on.
Now try to solve the problem with a third prisoner, still with lamp being off from the start. This strategy can be extended to any number of prisoners. The step after that is to solve the puzzle when the prisoners don’t know the starting position.
The final puzzle in this chapter also involves a prison and a room containing an object that prisoners must interact with in a clever way. Yet rather than leaving messages for one another, they are looking for hidden information.
50
THE ONE HUNDRED DRAWERS
A cabinet with a hundred drawers, each numbered from 1 to 100, stands in an otherwise empty room in a prison. The warden enters the room, writes down the names of 100 prisoners on separate pieces of paper, and distributes the pieces of paper randomly in the cabinet so that each drawer contains the name of one prisoner.
The warden exits the room and assembles the 100 prisoners whose names she wrote on the slips of paper. She tells them that they will each be let into the cabinet room, one after the other; once in there they are permitted to open 50 drawers and look at the names on the pieces of paper inside. She adds that if every single prisoner opens the drawer containing his name, everyone will be freed. But if at least one prisoner doesn’t open the drawer with his name in it, everyone will be killed.
The prisoners are allowed to think up a strategy before they go into the cabinet room, but once the first prisoner goes in they are not allowed to communicate in any way. They cannot leave messages in the room, nor tell prisoners what they saw once they leave the room.
Can you find the strategy that gives a chance of survival of more than 30 per cent?
Of all the mathematical surprises in this book, this result is perhaps the most staggering. If a prisoner chooses 50 out of 100 boxes at random, the chance that one of these boxes contains his name is 50 out of 100, or 50 per cent. If all 100 prisoners were to choose 50 boxes at random, the probability of everyone choosing their name would be:
50 per cent of 50 per cent of 50 per cent … (repeated 100 times) … which is:
0.00000000000000000000000000008 per cent
Yet a strategy exists that improves the chances of every prisoner finding his name by a factor of more than 100 octillion.
The strategy is very simple to describe, and relies on a very interesting piece of mathematics that is fully explained in the back of the book. Even if you can’t prove that it gives the prisoners more than a 30 per cent chance of survival, have a guess as to what it might be. You will be genuinely astounded at how a collective decision can beat the odds.
Tasty teasers
Riotous riddles
Each of these puzzles relies on the solver making a mistaken assumption.
1) Two identical children born on the same day to the same mother and father are not twins.
How is this possible?
2) A certain man had great grandchildren, yet none of his grandchildren had any children.
How is this possible?
3) You are on a plane, a mile above sea level. Huge mountains lie directly ahead. The pilot does not change his course, speed or elevation. Yet you survive.
How is this possible?
4) A woman has a bucket of water in her hands. She turns it upside down, but the bucket stays full. There is no bucket lid, the water is in liquid form, and she is not relying on centrifugal force.
How is this possible?
5) A clean-shaven teenager told his parents he was going to a party, and would be back before sunrise. He got back before sunrise, and had a fully-grown beard!
How is this possible?
6) A boxer left a contest victorious, winning the national championship. Even though his trainer took all the money, the boxer was quite happy.
How is this possible?
7) Identical twins Milly and Molly always wear the same clothes. One day I saw one of them and I shouted hello. As soon as she turned to me I knew it was Milly.
How is this possible?
8) A woman working in an office is sacked from her job. The following day she shows up at the same office, where she is welcomed.
How is this possible?
9) My neighbour is 92 years old and frail. One day I invited her round to do something I was not able to do. She was able to carry out the task, even though she has no skills that I do not have.
How is this possible?
10) One day a man saw the Sun rise in the west.
How is this possible?
Cakes, cubes and a cobbler’s knife
GEOMETRY PROBLEMS
As professor of minerology at Geneva University in the early eighteenth century, Louis Albert Necker spent many hours staring at diagrams of crystalline forms. He noticed when examining these figures that they would often suffer a ‘sudden and involuntary change in [their] apparent position.’ This phenomenon is clearly seen in the image below, now known as the ‘Necker cube’. A flat figure comprising 12 lines, it could equally be a cube seen from above (in which the bottom left square is the front), or a cube seen from below (in which the top right square is the front). Since there are no clues as to the depth of the figure, its orientation when visualised in three dimensions is ambiguous. What’s fascinating about the Necker cube is that when seeing it one way, it is impossible to see it in the other way, and the perceived orientation can flip suddenly between views.
The Necker cube is an optical illusion. For me, it’s also a metaphor for the joys of geometric puzzles. The ‘sudden and involuntary change’ in its perceived orientation is analogous to the flash of insight that this type of puzzle requires. We will see many geometric puzzles in this chapter. You will stare at them, searching for clues. You will feel you are getting nowhere, when, all of a sudden, a magical sensation occurs: the thrill of realising you’ve been staring at the answer all along. Your eye just flipped between orientations. It’s a transcendent feeling. The answer was always there, hiding in plain sight. Once you look at a geometric puzzle the right way, the answer often jumps off the page.
51
THE BOX OF CALISSONS
A calisson is a French sweet made from a candied fruit marzipan topped with royal icing. Let’s assume its diamond shape is made from two equilateral triangles meeting along an edge. When you pack calissons in a hexagonal box, they fit in one of three ways: horizontally , sloping left or sloping right The image below shows the aerial view of one possible arrangement.
Without counting them, show that the number of calissons in each orientation is the same.
Problems are all the more appetising when set in the context of pâtisserie. The cake counter, in fact, throws up some delicious brain food. And to think you doubted that the puzzles in this book had any practical applications.
52
THE NIBBLED CAKE
Someone ate a thin rectangular slice of your cake. Here’s an aerial view.
How would you slice the cake with a single straight cut that divides what’s left into two equally sized portions?
In other words, draw a single line that divides the shape above into two parts of
equal area. Standing the cake on its side and cutting it into a top half and a bottom half doesn’t count. That’s cheating.
Mmmm, these cake puzzles are so moreish!
53
CAKE FOR FIVE
How do you cut a square cake into five portions of equal size? Each slice must be ‘slice-like’, meaning that the knife cuts vertically through the cake and the tip of each slice is at the cake’s centre. You have no ruler or tape measure, but you can use the horizontal grid shown here.
The previous two questions concerned equitable cutting – that is, making sure that every slice contains an equal amount of cake. In real life, we take it for granted that when we share a cake every slice must be the same. In fact, the implicit assumption of fairness has made cake-cutting the favoured example in the field of ‘fair division’, an area of maths, economics and game theory that analyses strategies for dividing things up. Geometers, on the other hand, are not always interested in slicing pastries into equal portions. Sometimes they want to know how to cut an object into the most pieces with the fewest number of cuts.
54
SHARE THE DOUGHNUT