So You Think You've Got Problems
Page 4
Are you still thinking about the Sphinx’s 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 is night and day, which replace each other endlessly as the Earth spins round the Sun.
29
THE THREE BOXES
[1] You are locked in a dungeon. By the door are three boxes: one black, one white and one red. The boxes have the following sentences written on them:
A sign by the boxes reads: ‘Of these three statements, at most one is true.’ If you are only allowed to open one box, which one do you open to find the key?
[2] Let’s say you find the key. The door opens, and leads to another dungeon, again containing three boxes:
A sign by these boxes reads: ‘Of these three statements, at least one is true and at least one is false.’ If you are only allowed to open one box, which one do you open to find the key?
From keys in boxes to a box with locks in.
30
SAFE PASSAGE
You want to send your beloved a ring using a mail service that is notorious for opening packages and stealing valuables. To ensure the ring arrives safely it must be sent in a lock box, such as the one shown on the right, which has five holes for padlocks. (A padlock in any of the five holes will lock the box securely.) You and your beloved have five padlocks each. You also have the keys for your own padlocks, but you don’t have the keys for each other’s padlocks.
If you have unlimited money for postage, how are you able to send your beloved the ring?
Solving a puzzle can be like unlocking a mystery. In these next puzzles, quite literally so.
31
CRACK THE CODE
A combination lock has a three-digit key. Use the clues below to deduce the code.
One number is correct and correctly placed
One number is correct but wrongly placed
Two numbers are correct but wrongly placed
Nothing is correct
One number is correct but wrongly placed
32
GUESS THE PASSWORD
The password to open a door consists of seven digits, no two of which are the same. So 0123456 is a possible password, for example, but 0123455 is not. The door will open if you type in a seven-digit number, and at least one of the digits matches its position in the password. For example, if the password is 0123456, the door will open if you type, say, 0234567, because both your number and the password have a 0 in the first position.
What is the smallest number of attempts you must make to guarantee that the door will open?
33
THE SPINNING SWITCHES
You are locked in a cell. On the door is a wheel, illustrated below, which has two identical buttons on it. The buttons are switches that can be pressed on and off, but there is no way to tell whether a switch is on or off.
The door will unlock when both buttons are on. At any stage you can press either one button or both buttons together. Once you have had a try, either the door will open or the wheel will spin, and when it comes to rest you won’t know which button is which.
How do you unlock the door in a maximum of three moves?
If that was too easy, try the four-switch version. The wheel now has four buttons, one in each of the four compass directions. The door will open only when all four are on. At any stage you can press one, two, three or four buttons simultaneously. If the door does not open the wheel will spin, and when it comes to rest you won’t know which button is which. What strategy will get you out? (The solution to this one is also in the Answers section.)
You’ve spent long enough alone. Let’s introduce some other people.
34
PROTECT THE SAFE
The three directors of a bank are deeply suspicious of one another, and agree a system of locks and keys for the bank’s safe, such that:
No single director can open the safe alone.
Any two directors can open the safe by pooling their keys.
What’s the smallest number of locks and keys they need to open the safe, and how do they distribute them?
Three mistrustful work colleagues also feature in a lovely puzzle about extracting information without giving anything away. How do three people find the average of their salaries without any one of them disclosing their actual salaries? (The solution is in the Answers section.) Here’s a similar problem, with extra tattoos.
35
THE SECRET NUMBER
Every gang in your area has a secret number, and the only way gang members can correctly identify fellow members of the same gang is by checking this number.
You’re thrown in prison. An inmate comes up to you and claims he’s in your gang. You’re suspicious. You’re not going to reveal your gang’s secret number, just in case the inmate is a member of a rival gang, and for the same reason the inmate isn’t going to reveal his number to you either.
Another prisoner, Lag, joins the conversation. Lag says that either of you can tell him anything, or ask him anything, and he will answer truthfully, and quietly, so that the other one doesn’t hear. (He’s also discreet, so he won’t listen to any conversations between you and the inmate).
How do you discover whether you and the inmate are in the same gang, without either of you revealing your number to each other, or even to Lag?
After Claude-Gaspard Bachet’s Problèmes Plaisants et Délectables in 1612, the next great book of puzzles was Récréations Mathématiques et Physiques, a book of maths, physics and magic tricks by the French author Jacques Ozanam. Its second edition, published in 1723, contained the following parlour game.
36
REMOVING THE HANDCUFFS
Two people are joined together by two pieces of string looped to their wrists, as shown below.
How can the people free themselves without untying or cutting the string?
Try it out yourself with a friend. In fact, why not follow the advice I read in a 1950s magic book: the next time you have a party, divide your guests into couples, join each couple with string handcuffs, and give a prize to the first pair to unlink themselves. It guarantees that couples will ‘undertake astonishing contortions in fruitless efforts’ to set themselves free.
Magic is the art of doing the seemingly impossible, and illusions are often based on mathematical surprises. The trick presented in the handcuffs puzzle is unravelled with topology, a type of geometry concerned with the properties of objects that don’t change if the objects are stretched or squeezed. To a topologist, all closed loops are the same, whatever the size or material: the metal ring on your finger, for example, is topologically identical to a hula hoop. If two closed loops are interlocked, you cannot free them without breaking one of the loops.
The handcuffs puzzle appears to involve two interlocked closed loops. But it doesn’t, and realising that is the way to the solution.
If you don’t have any friends around, here’s a topological party trick you can practise on your own.
37
THE REVERSIBLE TROUSERS
Tie a 1m length of rope between your ankles as shown below. Without cutting or untying the rope, how do you take your trousers off and put them back on inside out, with the fly on the front?
A standard challenge in escapology (once your trousers are back on correctly) is how to exit a maze. The following puzzle requires you to enter one.
38
MEGA AREA MAZE
Find the mystery area without using fractions in any of your workings.
All you need to know to solve this puzzle, by the Japanese designer Naoki Inaba, is that the area of a rectangle is equal to the product of its side lengths. I’ll start you off. The top left rectangle has an area of 35cm2 and one side of length 7cm, so we can deduce that its other side is 5cm long. From this we can deduce that the rectangle of area 20cm2 to the right of the first has sides of length 5cm and 4cm, so the rectangle of area 21cm2 below that also has a width of 4cm.
You
will then pass through almost every rectangle in the grid before reaching the mystery square.
Now that you’re in a maze, your job is to find a way out.
39
ARROW MAZE
The maze shown below is an 8 x 8 grid, and each cell contains an arrow pointing up, down, left or right. You are in the top left cell, and the only exit from the maze is the right-hand edge of the bottom right cell.
The rules of the maze state that from any cell you must move one cell in the direction of the arrow. In other words, you follow the arrow into an adjacent cell. Once you arrive in a new cell, however, the arrow in the cell you moved from is turned clockwise by 90 degrees. If you arrive in a cell that points out of the grid, you stay in that cell and the arrow is turned 90 degrees clockwise, unless you are in the bottom right cell, with the arrow pointing right, in which case you exit the grid.
Will you ever get out of the grid?
Let’s start. The arrow in the top left cell points up. You can’t get out, so the arrow in that cell turns 90 degrees clockwise. It’s now pointing right. You move to the adjacent cell, where the arrow again points right.
You could carry on like this, following the arrows on the page, to see whether you eventually escape the grid. And if you did, you would quite rightly complain that it was a really frustrating and unsatisfactory puzzle, since you have to remember the new arrow directions of every cell you pass through. My advice is not to follow the arrows or trace any particular path at all.
Instead, consider what would happen if the grid was much, much larger – say a million cells by a million cells, and if you had no idea of the original directions of the arrows. What would happen then?
40
THE TWENTY-FOUR GUARDS
A prison is surrounded by 24 guards arranged in groups of three, as shown in the diagram below, with nine guards on each side.
Prison regulations state that exactly nine guards must be along each side of the prison at all times. However:
[1] On Monday night, four of the guards sneak off to the pub.
[2] On Tuesday night, the 24 guards are joined by four other guards.
[3] On Wednesday night, the 24 guards are joined by eight other guards.
[4] On Thursday night, the 24 guards are joined by 12 other guards.
[5] On Friday night, six guards go to the cinema.
The guards never break the rules. How do they manage it?
41
THE TWO ENVELOPES
You are brought to the king, who is sitting at his desk, by a big log fire. ‘Today you will learn your fate,’ he says. ‘Either you will be executed or you will be freed.’ He points to two envelopes on his desk. ‘In one envelope is the word DEATH. In the other is the word PARDON. Choose one of them, open it, and I will act on whichever word is revealed.’
As you deliberate which envelope to choose, a guard whispers to you that both envelopes contain the word DEATH.
If he is correct, can you think of a strategy to survive?
42
THE MISSING NUMBER
You are locked up in a distant land. The mischievous monarch will only free you if you pass the following numerical test. ‘I will read aloud every number between 1 and 100 leaving one number out, and your task is to tell me the number I omitted,’ says the queen. ‘I will recite my list of 99 numbers in a random order, at a rate of one number every two seconds. I will read each number aloud only once. You have neither pen nor paper, nor any other way of recording what I say.’
You don’t have a very good memory, so memorising the list is beyond your capabilities. But you are good at arithmetic. What’s a simple strategy for finding the missing number?
You find the missing number. Now the queen – who has a penchant for puzzles involving the numbers from 1 to 100 – pits you against a fellow prisoner.
43
THE ONE HUNDRED CHALLENGE
You are to play a game against your cellmate, in which you both take turns to say a number between one and 10. The loser is the first person to reach 100. Your cellmate starts.
‘Eight,’ he says.
‘Three,’ you reply.
‘Four,’ he says.
What strategy guarantees that you will win?
Islands that appear in puzzles often have inhabitants with peculiar behavioural traits. Here we visit one that has been on the tourist trail since at least the 1950s.
44
THE FORK IN THE ROAD
You are on an island inhabited by two tribes. The members of one tribe always tell the truth. The members of the other tribe always lie. You come to a fork in the road. One branch leads to the airport, the other to the beach. You spot a local standing nearby, but you cannot tell which tribe she belongs to.
You must ask the local a single question to discover which branch leads to the airport.
What do you ask her?
The question seems to ask the impossible because, intuitively, one assumes that people who tell the truth and people who lie always give contradictory answers to the same questions. For example, if you pointed at a road and asked the local whether it was the correct route to the airport, her answer would depend on which tribe she belonged to. A truth-teller would say the opposite to a liar. If the former said yes, the latter would say no, and vice versa.
Yet there are questions that force liars to tell the truth. The ruse is to get the liar to lie about their own lie. In other words, ask the local a question about how she would answer a question.
45
BISH AND BOSH
You are on an island inhabited by two tribes. The members of one tribe always tell the truth. The members of the other tribe always lie. You come to a fork in the road. One branch leads to the airport, the other to the beach. You spot a local standing nearby, but you cannot tell which tribe he belongs to.
You want to ask him which branch leads to the airport, but your plight is complicated by the fact that even though the inhabitants of the island understand English, they cannot speak it. Instead, they reply to all English questions with the words ‘bish’ or ‘bosh’. You know that these are native words for ‘yes’ and ‘no’, but you don’t know which is ‘yes’ and which is ‘no’.
What question can you ask the local that will reveal which route goes to the airport?
Just as in the previous question, you are not trying to work out whether the local is a liar or not, nor are you trying to work out what ‘bish’ or ‘bosh’ mean. All you want to do is leave the goddam island!
Raymond Smullyan (1919–2017) was the twentieth century’s most brilliant and prolific inventor of logic puzzles, many of which were set on islands containing truth-tellers and liars. The next puzzle is one of his. It’s an example of what he calls ‘coercive logic’, since the idea is to force a person, using logic, to do the opposite of what they want to do.
46
THE LAST REQUEST
You are due to be executed tomorrow. The executioner asks if you have a last request.
‘I would like to ask you a question,’ you say. ‘All I ask is that you answer it truthfully by saying either “yes” or “no”.’
The executioner is relieved, and rather surprised, to discover that the request is so straightforward. He promises to answer the question truthfully.
[1] What question can you ask the executioner that forces him to answer ‘yes’ and spare your life?
[2] What question can you ask that forces the executioner to answer ‘no’ and spare your life?
The solutions to the fork-in-the-road problems relied on the fact that a liar will inadvertently tell the truth when lying about his own lie. The executioner problem, on the other hand, is about the inadvertent consequences of always telling the truth.
I’m going to show you an answer to [1] in the next few paragraphs, so look away now if you want to attack this problem with no help.
You probably didn’t look away. This type of logic problem is so brain-twisting it is hard to know where to sta
rt. I’ve included this one because the solution is so clever and elegant that I hope you will derive pleasure from it whether or not you figure it out.
A valid solution to [1] is: ‘Will you either answer “no” to this question or will you spare my life?’
If you were to ask this question, the executioner would have no alternative but to answer ‘yes’ and spare your life. Let’s break it down to understand why. The question is asking whether one of these two statements holds:
[1] The executioner will answer ‘no’ to the question.
[2] The executioner will spare your life.
If the executioner answers ‘no’ – that is, if none of these alternatives hold – then the executioner is not being truthful, since one of these alternatives does hold, namely the first one. The executioner has contradicted himself. The response cannot truthfully be ‘no’, so the executioner is forced to answer ‘yes’.