Good Will Hunting Second Math Problem

The movie Good Will Hunting was about a secret math genius played by Matt Damon. The plot turns on the main character Will solving a very difficult math problem that stumped the MIT math professors for two years. Not only was the problem actually quite easy, but the character in the movie still got it wrong.

The problem as posted on the chalkboard was “Draw all homeomorphically irreducible trees of size n=10.”

Let me try to put that in plain simple English. It is asking for all possible diagrams consisting of ten dots, connected by lines, where no line can have exactly two lines extending from it (otherwise it would be reducible) and there can be no closed loops (otherwise it wouldn’t be a tree). “Homeomorphically irreducible” means that it doesn’t matter at what angles the lines are, just how many lines extend from each dot.

In the movie, Will produces only eight of the ten trees. Let me show you a way to systematically work out the answer. The way I will do it is to think of the trees as family trees, starting with the head of the family.

Solution 1 – Nine children. This is the only solution with only two generations.

Solution 2 – Three children with grandchildren split 6/0/0

Note that there cannot be exactly two children, because then you could go from one child to the parent and then to the other child, which would be reducible.

Solution 3 – Three children with grandchildren split 4/2/0

Note that nobody can have one child, otherwise the tree would be reducible.

Solution 4 – Three children with grandchildren split 3/3/0

Solution 5 – Three children with grandchildren split 2/2/2

Solution 6 – Four children with grandchildren split 5/0/0/0

Solution 7 – Four children with grandchildren split 3/2/0/0

<

Remember, children can’t have one child, lest the tree would be reducible.

Solution 8 – Five children with grandchildren split 4/0/0/0

You might consider five children with grandchildren split 2/2/0/0, but this would be homeomorphically reducible to the same tree as solution 3 (this took me a while to see).

Solution 9 –Three grandchildren, with grandchildren split 2/0/0. One of the two grandchildren has four great-grandchildren.

Solution 10 -- Three grandchildren, with grandchildren split 2/2/0. One of the two grandchildren has two great-grandchildren.

 

 

I realize I am using some hand waving logic to get at all ten solutions. However, at least I got to all ten, unlike Will in the movie.

Next week I plan to address another movie where the math scene was done well – Mean Girls.

Related Links:

The problem in Good Will Hunting – YouTube video by Numberfile

Solution at MathProblems.info