Thursday, June 7, 2012

Answer: Who solves an impossible problem... by accident?

I wrote this challenge in response to a question that came up in hallway conversation at Google.  Some thought it was pure urban legend, but others swore it was true.  Being Googlers, we whipped out our phones and found that it was George Dantzig, a local Stanford mathematician from Stanford best known for his work on the Simplex Algorithm (an early linear programming system for making optimal choices).  Turns out he lived just a couple of miles away from the Googleplex and coincidentally next door to a friend of mine.  I had no idea.    
George Dantzig (link from Stanford University News)
To my surprise, this search challenge wasn't that difficult.  Most readers managed to solve it between 30 seconds and 5 minutes.  This is a great thing--even apparently crazy-hard problems can be fairly simple if you start your search properly.   

I started with the straightforward [
impossible problem solved accident ].  I was expecting to have to dig through many layers of information to find it, but as I scanned the SERP, I found the link to Snopes fairly quickly.  


I like the Snopes team--they do really excellent research, so I checked that article first.    In their article they give some very good references including his verbatim interview in "An interview with George B. Dantzig: The father of linear programming." College Math. Journal 17:292–314 (1986).

It happened because during my first year at Berkeley I arrived late one day at one of [Jerzy] Neyman's classes. On the blackboard there were two problems that I assumed had been assigned for homework. I copied them down. A few days later I apologized to Neyman for taking so long to do the homework; the problems seemed to be a little harder than usual. I asked him if he still wanted it. He told me to throw it on his desk. I did so reluctantly because his desk was covered with such a heap of papers that I feared my homework would be lost there forever. 
About six weeks later, one Sunday morning about eight o'clock, [my wife] Anne and I were awakened by someone banging on our front door. It was Neyman. He rushed in with papers in hand, all excited: "I've just written an introduction to one of your papers. Read it so I can send it out right away for publication." 
For a minute I had no idea what he was talking about. To make a long story short, the problems on the blackboard that I had solved thinking they were homework were in fact two famous unsolved problems in statistics. That was the first inkling I had that there was anything special about them. 
A year later, when I began to worry about a thesis topic, Neyman just shrugged and told me to wrap the two problems in a binder and he would accept them as my thesis.
The second of the two problems, however, was not published until after World War II. It happened this way. Around 1950 I received a letter from Abraham Wald enclosing the final galley proofs of a paper of his about to go to press in the Annals of Mathematical Statistics. Someone had just pointed out to him that the main result in his paper was the same as the second "homework" problem solved in my thesis. I wrote back suggesting we publish jointly. He simply inserted my name as coauthor into the galley proof.

Other good references:  his obituary is as good a reference as any as it's from Stanford, and a TechRepublic article providing another source. 
 

But I was curious if there were any other reports of similar solutions.  So I kept reading farther down the SERP and found recent news story about Shouryya Ray, a schoolboy who reported solved a puzzle "posed by Sir Isaac Newton that have baffled mathematicians for 350 years."  But on further searching it seems that the solution he came up with wasn't exactly new, and since it was a competition, it really wasn't an accidental solution.  


Answer:

Who: George Dantzig
Where: as a student at University of California, Berkeley
When: 1939 
How: Arriving late to a lecture by statistics professor, Jerzy Neyman, he copied down two problems from the blackboard thinking that they were homework assignments.  They were in fact open, unsolved questions.  He then solved them, but noted that they seemed harder than usual.  
What: The questions were about "Student's" Hypothesis and power functions, and the Neyman Pearson lemma. (See reference #12.)  


Search Lessons:  The biggest one for me is that even questions that seem impossible to answer can sometimes be rather quick and simple to resolve.  Don't be afraid to tackle even seemingly crazy problems!  

Search on! 

2 comments:

  1. — the importance of dotting the i's and crossing the t's in search...
    was wondering what Glen had to do with algorithms — then realized it was George and I had dropped the "T".

    Must confess that the thought of Ms. M. sitting down with Danzig, for a GoogleTalk - ala Gaga - brought a smile to my face...
    that could be the source of another urban legend for the Snopes team.

    complete with censorship - (because of the Arkansas chicken?):
    Danzig-Mother(Mayer)...

    the difference between bored & board:
    "Don't be afraid to tackle even seemingly crazy problems! "
    AR (Mayer)

    ReplyDelete
  2. Clifford Cocks discovered RSA cryptography in a similar fashion. Searching "clifford cocks cryptography" gives a few sources

    ReplyDelete