From the Blogosphere
Solving the Good Will Hunting Problem
Sounds simple? Well, it is.
By: Martin Kaarup
Oct. 28, 2009 12:15 AM
I've seen the movie Good Will Hunting from 1997, starring Matt Damon in the role as a mathematical gifted janitor, twice. The first time I hadn’t taken a course in graph theory, the second time I had. Regarding the mathematical aspect of the movie, it makes all the difference. The second time I could actually understand the problem the professor posed when he threw down the gauntlet. In the movie the MIT professor stated a, supposedly, very tough problem that they had worked on intensely for almost two years before they were able to solve it. It reads:
"Draw all the homeomorphically irreducible trees having 10 vertices, such that no vertex has degree 2."
In plain words, connect ten dots together with lines such that all dots are connected to at least one other dot. Further, there must only be one path from any dot to any other dot, which means that circles are not allowed. Lastly, all dots must have 1, 3, or more lines connecting it to other dots, but not 2. Now draw all the different figures that satisfies the requirement.
That's what the gifted janitor did on the white board in the hallway.
Sounds simple? Well, it is – surprisingly simple actually.
In reality, the problem is no harder than any other high school problem. The real problem is quite different, namely that we accepted it was hard because Hollywood said so. A corollary to this claim could be to check the Internet and realize that many people already have solved the problem and some even before the movie. Another corollary could be to spend the next 10 minutes or so to solve it yourself, tell someone you know that has seen the movie, and then watch their reaction.
So, the only thing left now, is to challenge you to solve the problem and to present the solution.
Last week I challenged Erik Forsberg, a senior .NET consultant from Avega Group AB in Sweden. He solved the problem before he zipped his morning coffee a third time. Can you?
I've hidden the solution from plain view here.
Reader Feedback: Page 1 of 1
Latest Cloud Developer Stories
Subscribe to the World's Most Powerful Newsletters
Subscribe to Our Rss Feeds & Get Your SYS-CON News Live!
SYS-CON Featured Whitepapers
Most Read This Week