Transcription
Did you know that mathematicians actually kind of hate Goodwill Hunting? The entire plot of the movie revolves around Matt Damon being a math genius for solving this problem that really isn't all that hard. Pretty much anyone can do it with a few minutes of dedicated doodling. Let me show you how.
So, this was the problem. Draw all homeomorphically irreducible trees of size n equals 10. This may sound complicated, but it's actually the language itself that makes it hard. Once you translate all the technical terms, the task is actually pretty simple.
So, first, in math, a tree is a type of graph. Basically, it's a collection of points that are connected. The size of the tree is determined by the number of points or nodes that it has. In this case, that number is 10.
Next, let's talk about homeomorphically irreducible. This is just a fancy way of saying that you shouldn't be able to turn one tree into another by just rearranging it. For example, these trees may look different, but they share the exact same connections. I can turn one into the other by just moving the nodes around. This means they are homeomorphic. Similarly, this K with one long leg is also considered the same tree because a node with just two connections can be collapsed into a single line. So, in summary, this is the only homeomorphically irreducible tree with five nodes.
So, with all that math gobbledygook out of the way, really all Matt Damon had to do was draw all unique trees with 10 nodes. Let's do it together. Start with one central node that radiates out with nine connections. This has 10 nodes total and meets the criteria. There's our first tree.
Then, try it with one central node and eight connections. But, this doesn't work because either you'll recreate the last tree or you'll end up with a reducible line. This brings us to seven connections off of one central node. You know you have to add two more nodes to get to 10, and they have to go off of the same node. Otherwise, you'll create reducible lines. If you keep doing this, decreasing that initial set of connections, then adding back nodes to get to 10, you'll eventually end up with a set of 10 distinct trees. And that makes you a mathematical genius, at least according to Goodwill Hunting. Oh my god.