Remembering Howard Stern '79

Howard was in my probability seminar in the spring semester of our senior year, and then we went our separate ways—me to grad school in mathematics at Princeton, him to grad school in economics (I believe) at MIT. I had no further contact with him until 2012, when an out-of-the-blue e-mail appeared. "I just read the little blurb about you in the Bulletin," he wrote. "To say it's been a while since we last spoke would be an understatement."

But he quickly got down to business, and the business was a math problem! It was a problem that he had gotten interested in as a grad student, had not quite been able to solve, and over the years he had not found anyone else who could solve it. The problem, as he stated it, was this: You have a match between two backgammon teams, each with N players. According to the rules, the #1 player is supposed to play the #1 player, the #2 player is supposed to play the #2 player, etc. But what if one team decides to cheat? How can they best arrange the order of their players to win the maximum number of games (on average)? (We'll assume that the other team is honest.)

Little did I realize it, but I was hooked! At that time, it had been 17 years since I had worked seriously on a math problem, of the open-ended kind that you can't just sit down and solve in one day. It took me weeks before I even made the slightest bit of progress on Howard's problem. And yet—it wasn't an intractable problem either. Like a rock face, it had a lot of chinks in it that you could grab onto and try to climb. It took me in unforeseen directions, and when I first proved something that Howard hadn't been able to prove, it gave me the same electric jolt of excitement that I had forgotten for so long. Yes, in my current career as a writer I solve problems too, but they are of a different nature. As a writer I am merely finding the right word; as a mathematician I used to discover secrets of the universe.

I don't know how many hours I worked on his problem: 200? 300? All I can say is, they were hours when I was supposed to be writing, but I was as happy as a clam doing mathematics!

And eventually I solved it! Well, 99 percent. (I'll get to the other 1 percent in a moment.) That is, I figured out the cheating team's optimal strategy, and I was able to prove that it was the best. And it was a gorgeous solution -- unbelievable, totally unexpected, yet true. I contacted Gary Antonick, who wrote a math blog for the New York Times called "Numberplay." He generously offered to let me write about Howard's problem in his blog. That post ended up being Gary's most-discussed blog post in a year, attracting nearly 100 comments from readers. One of the readers, named Richard Chatwin, asked the same question that Howard had asked: "Can't you just solve it using the Hungarian Algorithm?"

I know I'm getting technical, but I think it's important to explain this. What Howard had done, back as a grad student in 1980, was reduce the problem to a class of problems known as linear assignment problems. And the Hungarian Algorithm is a general-purpose method for finding solutions to such problems ... on a computer. So if you give a computer a particular value of N—say, 277 players on each backgammon team—it can calculate the optimal solution for you, and quickly.

For this reason, linear assignment problems are considered "solved." But what a computer cannot do—can NEVER do—is solve an infinitely large collection of problems. In other words, it cannot tell you the optimal strategy for the cheating backgammon coach for ALL values of N. Ironically, to solve an infinite problem you need a different kind of technology: paper and pencil and a brain. The kind of solution that is considered a "solution" in the modern computer era would never have been considered a solution by Euler, or Gauss. Solving a problem means understanding it, understanding the pattern, and the Hungarian Algorithm can never give you that kind of understanding.

But I must admit that I am exaggerating a bit. For one thing, my proof was incomplete. I could only prove that my proposed strategy was optimal if N was large enough: at least 10 million backgammon players on each team. So for any practical backgammon match, I hadn't solved the problem at all!

But here's where Richard Chatwin came in. Unbeknownst to me, he had a Ph.D. from Stanford and had written a thesis on optimal algorithms for airplane flight overbooking. As Howard said, it was practically as if we had found a guy who majored in the Hungarian Algorithm. Richard soon ran into exactly the problem I told you about—you can't solve an infinitely large problem with a computer, for that you need pencil and paper! But Richard brought his insights from linear programming and vastly improved my proof, to the point where it worked for any N larger than 41. For N less than 41, we could simply program it into a computer and confirm that our strategy worked there, too.

In the end, Richard's logical rigor and his knowledge of linear programming were just what I needed. The two of us co-wrote a paper about our solution for the College Mathematics Journal, which was published in 2015. I offered to let Howard be a co-author of the paper, because it was his problem after all, but he declined.

I think that, in the end, Howard was perhaps a little bit disappointed in our solution. He really wanted the solution to come out of linear programming, and it didn't. As a result, he never really did understand our solution, and I feel sorry about that. But he was satisfied that his problem had been solved. For me, on the other hand, this experience was probably one of the top-three thrills in my career as a mathematician. For one thing, it came so long after I thought my career was over. And it was such a beautiful problem, and it gave me a chance to write for the New York Times (at least a blog post), and it gave me a chance to meet and work with a brilliant mathematical mind in Chatwin. It was the truest and best mathematical collaboration I ever experienced. All of this because of Howard's e-mail! He gave me one of the best gifts of my life.

The last time Howard wrote to me was in November of 2015, and guess what? He had a new math problem for me to solve. I have to say that this time I was far too involved in other things, and I couldn't risk getting sucked in again and spending hundreds of hours on another problem. So I had to leave the problem undisturbed, maybe to come back to it later. I had no inkling that I would never get a chance to work on "Howard's Second Problem" during his lifetime, because he died only eight months later.

I know this is an unusual reminiscence. I haven't talked about Howard's personality, or his family or his career. I simply don't know about any of these things. I never even saw him again in person; all our communications were by e-mail. Yet he gave me something completely priceless, a meeting of the minds in a realm where time and worldly concerns and death itself have no meaning, the realm of mathematics.