Labyrinths of Reason (18 page)

The elevator problem exists in many versions. The six people can be the ill-chosen guests at a dinner party, some of whom aren’t speaking to one another because of past feuds. If no three guests are all on speaking terms, prove there is a trio who aren’t speaking to one another at all. A bawdy version of the problem claims that, of any six residents of a college dormitory, at least three have slept with each other, or at least three have never slept with each other.

The elevator problem illustrates a branch of mathematics called
graph theory
. Graph theory enters (often unrecognized) into many problems, both recreational and practical. One of the best-known is the “gas, water, and electricity problem” popularized by Henry Ernest Dudeney, author of puzzles and riddles for newspapers and magazines around the turn of the century. The answer to the original version of the problem is that there is no answer. It is impossible to connect three dots to three other dots in the plane without at least one connection crossing another. When puzzles like this were in their heyday, no one was overly concerned that unsuspecting readers might spend hours or days on an unsolvable puzzle. Of course, Watson and Holmes’s clever solution in the previous chapter is beside the point!

Graph theory is not about the sort of graphs that show stock-market averages or annual rainfall. A graph in graph theory is a
network of points connected by lines, like the route maps of airlines you see in airports. Whether the lines are straight or wiggly makes no difference, nor does the relative position of the points. Only the topological properties of the network count—
which
points are connected by lines. All this is true enough, but it says nothing about why such things are important or useful. In a broader sense, graph theory is the study of relationships or connections between elements.

The elevator problem is easily translated into a graph. Represent the six people as dots (see diagram). Between every two dots you can draw a line representing a relationship. Let a black line mean the pair are acquaintances, and a gray line mean that they are strangers. A trio of mutual acquaintances appears as a black triangle; a trio of mutual strangers as a gray triangle. Is it possible to draw in lines between all the dots so that no all-black or all-gray triangles appear?

The proof is easy to follow. Start with Alice. We will draw five lines from Alice, representing whether she knows or doesn’t know the other five persons in the elevator. No matter what, at least three of the lines must be the same color. That’s because there are five lines and two colors. The evenest split gives you three lines of one color and two of another. Otherwise, there will be four or even five lines of one color.

We don’t know whether Alice will know at least three persons (black lines), or not know at least three persons (gray lines). Take the first eventuality. Let’s say that three black lines connect Alice
with Charlie, Edna, and Fred. How do we color the lines connecting this latter trio?

If any of these three lines are colored black, then that produces an all-black triangle: a set of three people who are mutual acquaintances. The only way to avoid an all-black triangle is to color the lines between Charlie, Edna, and Fred gray. That produces an all-gray triangle, which, of course, is a set of three persons who are strangers. Either way, the trio of acquaintances or strangers is inevitable.

If instead Alice
doesn’t
know three or more of the others, similar reasoning leads to an identical conclusion. An all-black or all-gray triangle must exist.

This is not the only case where a logic problem is equivalent to a geometric one. Complexity theory recognizes that many different types of problems are procedurally identical.

Metaphors for the scientific process are many: a riddle, a cipher, a jigsaw puzzle. Confirmation is often more like the solution of a logic puzzle than the models of induction discussed in previous chapters. A simple generalization is confirmed or refuted by any relevant observation. Most scientific theories are much more complex and must be evaluated in light of a large number of observations. You may not even be able to say if a given observation, in isolation, confirms or disconfirms.

Take the hypothesis that the earth is round. Confirming this was not a matter of assembling a large number of observations of the round earth (from astronauts?) in the absence of counterexamples. Rather, people accepted the earth’s roundness because it related and made sense of experiences that previously seemed meaningless. To the ancients, few items of trivia could have seemed as unconnected as these: the midnight sun of the Far North; the round umbra of the lunar eclipse; the way ships seem to sink beneath the waves as they recede from port. Now all are seen as logical consequences of the roundness of the earth. It is because the round-earth theory explains so many unrelated observations that it is so compelling. Only by an incredible coincidence could all these observations agree so neatly with a round earth if the earth was not in fact round.

This more subtle type of confirmation combines deduction with induction. A hypothesis has logical consequences that must first
account for past observations and then make new predictions. True predictions confirm the hypothesis. The interplay of induction and deduction is the source of paradoxes even more baffling than those discussed so far.

A
PRISONER APPEARS before a hanging judge for sentencing. “I am not allowed to dispense cruel or unusual punishment,” the judge begins, rather inauspiciously. “The harshest punishment I am permitted to recommend is hanging by the neck until dead. The gallows it must be then. Beyond that, my only freedom is in setting a date for your hanging. I am of two minds on that.

“My impulse is to order an immediate execution and be done with it. On the other hand, that might be an undeserved kindness. You would have no time to contemplate your impending doom. I choose instead this compromise: I sentence you to hang at sunrise on one of the seven days of next week. I further instruct your executioner to make certain that you have no way of knowing in advance on which day you will be hanged. Every night, you will go to sleep
wondering if the gallows awaits the next morning, and when you do walk the last mile, it will come completely as a surprise.”

The prisoner was taken aback to find his lawyer smiling at this incredibly cruel sentence. When they got out of the courtroom, the lawyer said, “They can’t hang you.” He explained: “You are supposed to be hanged at sunrise on one of the seven days of next week. Well, they can’t hang you on Saturday. It’s the last day of the week, and if you aren’t hanged by Friday morning, then you can know with utter certainty that the day of execution is Saturday.
That
would violate the judge’s plan of not letting you know the day in advance.”

To this the prisoner agreed. The lawyer continued: “Therefore, the last day they can hang you is actually Friday. Fine. But look—they can’t hang you Friday either. Granting that Saturday is
really
out of the question, Friday is the last day they can hang you. If you make it to breakfast Thursday morning, you will know for a fact that you are to die Friday. And
that
is against the judge’s orders. Don’t you see? The same logic rules out Thursday, Wednesday, and every other day. The judge has outsmarted himself. The sentence is impossible to carry out.”

The prisoner rejoiced until Tuesday, when he was awoken from a deep sleep and sent to the gallows—quite unexpectedly.

The paradox of the “unexpected hanging” packs a double whammy. You think the paradox is that the seemingly plausible sentence can’t be carried out—and then it is. Philosopher Michael Scriven wrote of it: “I think this flavour of logic refuted by the world makes the paradox rather fascinating. The logician goes pathetically through the motions that have always worked the spell before, but somehow the monster, Reality, has missed the point and advances still.”

The paradox has the fairly unusual distinction of being inspired by a real event. It dates to a wartime (1943 or 1944) radio announcement of the Swedish Broadcasting Company:

Swedish mathematician Lennart Ekbom recognized the subtle contradiction and mentioned it to his class at Ostermalms College.
From there it soon spread around the world. It has gone through several anecdotal incarnations. Others versions talk of a “class A blackout,” a surprise military exercise to take place the following week, or a teacher’s anticipated “pop quiz.”

Shades of this paradox occur in many situations where one person’s knowledge is incomplete. E. V. Milner noticed an analogy in the New Testament parable of Dives and Lazarus. Dives, a rich man, goes to hell while poor Lazarus, who has suffered all his life, goes to heaven. Dives pleads with Abraham for mercy but is told no, the injustices suffered in life are exactly compensated for in the afterlife. Those who were fortunate in life must suffer. Milner’s paradox of Dives and Lazarus explores this somewhat ironic concept of otherworldly justice:

One minor weakness in the prisoner paradox is the possibility that the prisoner may not be hanged at all. The inevitability of the execution is essential to the prisoner’s deductions. To avoid this weakness, Michael Scriven’s 1951 analysis in the British journal
Mind
restated the paradox as an experiment with an egg. In front of you is a row of ten boxes marked No. 1 through No. 10. While your back is turned, a friend hides an egg in one of them. There is no doubt of that; the egg is there somewhere. The hider says, “Open the boxes in order. I guarantee that you will find an unexpected egg in one of them.” Of course she can’t hide the egg in box No. 10, for after opening box No. 9, you would know the egg’s location. Deductions and counterdeductions follow, as does the surprise at finding the egg in, say, box No. 6.

There is no limit on how far the prisoner’s logical daisy chain can reach. Look at this recent variation, “Hollis’s paradox” (for Martin Hollis):

Two persons on a train, A and B, each think of a number and whisper it to fellow rider C. C gets up and announces, “This is my stop. You have each thought of a different positive integer. Neither of you can deduce whose number is bigger.” C then gets off the train.

A and B continue their travel in silence. A, whose number was 157, thinks, “Obviously B didn’t choose 1. If he did, he’d know that my number was the bigger, just from C’s statement that we chose different numbers. Just as obviously, B knows I didn’t choose 1. Yeah, 1 is completely out, for both of us. The smallest number that is even a possibility is 2. But if B had 2, he’d know that I didn’t have it either. So 2’s out …”