Chapter 1

THE FIFTEEN PUZZLE

“Do you know the game called the Fifteen Puzzle?” asked the man, who had introduced himself simply as “Mr. Smith.” Jule replied that he didn’t think so. “It was invented around 1870 by Sam Loyd,” the man went on, “one of America’s greatest puzzlists, and at the time it became very popular, much as Rubik’s cube did a century later.”

Jule remembered his fascination with Rubik’s cube as a teenager. The twenty-six brightly colored little cubes he had endlessly rotated searching for the elusive solution, a configuration with a single color on each of the cube’s six faces. He also recalled wondering how many different arrangements were possible. Johanna, his twin sister, believed that the number of combinations was infinite, and also that once properly scrambled it was impossible to restore the cube to its original position. He knew that she was wrong on both counts, but was unable to prove his point back then. Not until many years later, long after he had forgotten all about the game and his fascination with it, did he come across the answer in one of the dozens of mathematical articles that Rubik’s invention had spawned. “There are exactly 43,252,003,274,489,856,000 different configurations, not infinitely many,” he had triumphantly announced to Johanna. But she would not quite concede defeat. “Well,” she had said after a short moment of reflection, “such a big number is almost infinity.”

The man reached into one of his pockets and produced a small wooden square with numbers on it. There was something vaguely familiar about the object but Jule could not quite tell what it was. The wooden square was in fact a frame containing smaller squares of identical size numbered from 1 to 15. These were arranged in rows of four, in sequential order starting at the upper left corner except for the last two squares, which were in reverse order, 15 followed by 14, leaving a vacant spot in the lower right corner. “The purpose of the game is to arrive at the sequential configuration 1 to 15 by sliding the squares up, down, right, or left into the empty spot one at a time,” explained the man.

Loyd’s Fifteen Puzzle starting position

Jule thought he knew what would come next, but the man put the game back in his pocket. If he intended to challenge Jule with the puzzle, he did not appear ready to do it yet. Whatever the case, Jule was certain that sooner or later he would be put through some kind of test, given the circumstances leading to his presence at Mr. Smith’s (or whatever his real name was) imposing two-story house in Highland Park, an affluent Chicago suburb of tree-lined curving streets and sprawling homes some twenty miles from the city center.

At age thirty-four, Jule Davidson had all but given up hope of ever becoming a famous mathematician. He was a rather short man with an athletic build and an easy manner. Despite his high forehead and thinning chestnut hair he considered himself good-looking, and you could grant him that, on account of his wide green eyes and well-proportioned nose. On the surface, he appeared to be reasonably happy with his teaching job at the Department of Mathematics of Indiana State University, in Terre Haute. But to his closest friends he would confess a growing discontent with the routine of an academic life that had become a little too comfortable and predictable, with its annual cycle of lectures, meetings, exams, and graduation ceremonies.

Jule secretly envied his twin sister. Johanna worked freelance as a consultant in computer security and was constantly traveling at short notice to London, Athens, or Bangkok to help some company keep two steps ahead of the next electronic intruder. And whenever a hacker gained access to sensitive data or the latest computer virus crippled one of her clients’ systems, it was up to Johanna to fix the problem—which, unlike his course in group theory or non-Euclidean geometry, was never the same. He wished he too could put his mathematical talent and logical mind to some challenging use. In the daydreams of his youth, he had often pictured himself as the hero of some fantastic voyage or adventure of the kind imagined by Jules Verne and which the popular French writer had so vividly described in his novels, prophetically anticipating many of the twentieth century’s technological marvels, from submarines to spaceships.

Actually, Davidson’s first name was originally spelled “Jules,” for he had been named after the famous author—“a literary genius and scientific visionary,” in his mother’s opinion. But he had later dropped the “s” because even if it is silent in French most people pronounced it, in effect changing his name.

One evening, while visiting canyousolveit.com, a Web site where mathematical puzzles were posted, a two-part question in probability had caught his eye, perhaps because it reminded him of a similar problem from his student days at the University of New Hampshire: A group of twelve baseball players put their caps in a bag. After the caps are well shuffled, each player picks one at random. (1) Calculate the probability that none of the players will pick his own cap; (2) What is this probability if there are infinitely many players in the group?

Not without some effort, Jule had found what he believed to be the correct answers.* For the first part of the question, he came up with 0.3679, or a 36.79 percent probability that none of the twelve players will pick his own cap. In order to answer the second part he had to find the limiting value of the probability as the number of players increases to infinity. Strange as it may seem, the probability remained practically the same regardless of the number of players. (For very few players, this is not the case; if there are only two or three players, for example, the probabilities are 0.5 and 1/3, respectively, as can be seen by a simple calculation.) Jule had calculated the probability that none of the infinitely many players would pick his own cap to be exactly 1/e or 0.367879441. . . .

The e appearing in the answer denotes a number of central importance in mathematics, a kind of universal constant. It is formally defined as the limit of the expression (1 + 1/n)ⁿ as n approaches infinity, but it is best known as the base of the natural logarithms. Its value is 2.7182 . . . (an infinite string of decimals follows). It crops up in a variety of contexts in pure mathematics and its applications to real-life situations, from the theory of complex numbers and differential equations to models of population growth, the arrangement of seeds in a sunflower, and probabilities involving baseball players exchanging their caps. Here’s another example: If $1 is invested at an interest rate of 100 percent per year compounded every hour, the amount in the account after one year will be very close to e—that is, $2.72, rounded to the nearest cent—and it will be exactly e if the interest is compounded “continuously.”

After Jule had clicked on the “Answer” button to check his solutions against those of whoever had posted the problem, a command had appeared prompting him to enter them in a box. He had done as instructed and the screen had responded with a message: Now that you have passed the first test, would you like to go on? The prize is an opportunity to help solve a 2,500-year-old enigma.

It had taken Jule three days to solve four other problems and answer a battery of short, nonmathematical questions such as: What do the words “live,” “record,” and “lead” have in common? and Estimate the number of words (on average) uttered by an American male during his lifetime, assuming he lives to age seventy-eight. After he had entered his answer to the last challenge—a fiendish mathematical puzzle—a fireworks display had filled the screen and a message had appeared: Congratulations! You may be the person we’re looking for. If you’re still interested, please send resume to . . .

Jule had e-mailed his curriculum vitae the next day. Even though he feared doing so could make him the target of endless spam, the possibility that it might lead to a change in his life was worth the risk.

One week later, in early January 1998, at two o’clock in the afternoon and after a tiresome six-hour drive from Terre Haute to the shores of Lake Michigan, he was calling at the Highland Park address sent to him with the invitation for an interview. A tall, slender man in his mid-fifties with penetrating brown eyes and silvery hair opened the door and greeted him with a smile. “Mister Davidson? Please come in.” The man was impeccably dressed in a classic blue blazer, white shirt, and dark grey trousers, and was wearing a somewhat incongruous bow tie.

During the next hour or so, Jule was subjected to an extensive interrogation about his background, career, friends, and hobbies, and especially his motives for answering the enigmatic Internet message. And then, as if the interview had entered a new phase, the man had mentioned the Fifteen Puzzle and shown him the small square board on which the game was played.

“This puzzle has an interesting story,” the man said, reaching for a book with a worn-out jacket that was lying on a low table. Jule observed the precise movements of the man’s well-manicured hands, and noticed the silver ring with a facet-cut white stone on the middle finger of his left hand. Only weeks later would Jule discover the symbolic meaning of that ring.

“Would you like to hear the story?” asked the man, and without waiting for an answer began reading aloud in a theatrical tone. “In the late 1870s, the Fifteen Puzzle popped up in the United States; it spread quickly, and owing to the uncountable number of devoted players it had conquered, it became a plague. The same was observed on the other side of the ocean, in Europe. Here you could even see the passengers in horse trams with the game in their hands. In offices and shops bosses were horrified by their employees being completely absorbed by the game during office and class hours. In Paris the puzzle flourished in the open air, on the boulevards, and proliferated speedily from the capital all over the provinces. A French author of the day wrote, ‘There was hardly one country cottage where this spider hadn’t made its nest, lying in wait for a victim to flounder in its web.’ ”

There was a brief pause while the man glanced at Jule, as if to confirm that the story was having the effect he had anticipated. “In 1880,” he went on, “the puzzle fever seemed to have reached its climax. The inventor of the game suggested to the editor of a New York newspaper to offer a $1,000 reward for the solution. The editor was a little reluctant, so the inventor offered to pay the reward with his own money. The inventor was Sam Loyd. He came to be widely known as an author of amusing problems and a multitude of puzzles. The $1,000 reward for the first correct solution remained unclaimed, although everybody was busy working on it. Funny stories were told of shopkeepers who forgot for this reason to open their shops, of respectful officials who stood throughout the night under a street lamp seeking a way to solve it. Nobody wanted to give up, as everyone was confident of imminent success. It was said that navigators allowed their ships to run aground, engine drivers took their trains past stations, and farmers neglected their ploughs.”

At this point the man stopped reading and closed the book. “Do you know how the story ends?” he asked, fixing his eyes on Jule’s. “I have no idea,” Jule replied without hesitation. “Good,” said the man, with more than a hint of relief in his voice. “Then we can proceed. Please follow me.”

They entered a big room almost entirely filled with books. Most of them occupied the bookcases covering three of the four walls and many others were lying on a large table or in unsteady piles of various heights directly on the floor. The man led Jule to a computer terminal on their left, gestured for him to sit down, and then asked: “How about a little game of fifteen, Mr. Davidson?” Taking Jule’s consent for granted, the man began to explain the rules. “The game board is a virtual one, as you might have already guessed.” He pressed some keys and the puzzle’s initial configuration appeared on the screen. “The numbered squares can be moved around with the cursor—only permissible moves are allowed, of course. You will have exactly sixty minutes to solve the puzzle. Needless to say, my interest in retaining your services will greatly depend on the outcome of the game.” He expected some reaction from Jule but there was none. “Do you have any questions?” he asked after a few moments.

Jule was already focusing on the task ahead and couldn’t help remembering that for all his efforts he had never succeeded in solving Rubik’s cube. But that was back in his youth, and now it was another story—and a different game. As his thoughts drifted toward Rubik’s puzzle, he remembered reading that someone from Vietnam held the world record for solving the cube from a scrambled state in less than thirty seconds. He had not believed that possible. And yet, equally inconceivable feats were on record regarding the so-called calculating prodigies, individuals capable of performing complicated arithmetic operations in their head almost instantaneously but otherwise possessing an average intelligence. One of these, a certain Jacques Inaudi, born in Italy in 1867, was brought before the French Academy of Sciences at the age of twenty-five by the mathematician Gaston Darboux. They asked him questions such as: What day of the week was March 4, 1822? If the cube plus the square of a number equals 3,600, what is the number? Subtract 1,248,126,138,234,128,010 from 4,123, 547, 238,445,523,831. He had provided the correct answer to those and similar questions in less than thirty-five seconds.

Jule wondered how long it would have taken Inaudi to solve the Fifteen Puzzle. “What’s the fastest that someone took to find the solution?” he wanted to ask. But the man was already gone and the screen was informing him that the game would start in 25 seconds, . . . 24, . . . 23, . . .

*For hints on the solution, see appendix 1.