The Good Will Hunting math problem
Poll
 | 3 votes (20%) | ||
| | 3 votes (20%) | ||
| | 1 vote (6.66%) | ||
| No votes (0%) | |||
| No votes (0%) | |||
| | 3 votes (20%) | ||
| | 1 vote (6.66%) | ||
| | 1 vote (6.66%) | ||
| | 3 votes (20%) | ||
| | 1 vote (6.66%) |
15 members have voted
August 30th, 2016 at 11:22:42 AM
permalink
The movie Good Will Hunting presents a math problem that allegedly took the entire MIT math department two years to solve. When Will (the janitor) solved it overnight it became the whole plot of the movie of finding out who this mysterious genius is. The movie doesn't dwell on the question. In fact, you have to freeze the screen and study the chalkboard to read it. Here it is math lingo first:
Draw all homeomorphically irreducible trees of size n=10.
Here is my attempt to put it in plain simple English.
Using only straight lines, draw all figures where the sum of intersections and dead ends equals 10. You may not have any closed loops. You may also not have two equivalent figures. Any intersection must have at least three paths leading from it.
What do I mean by "equivalent," you might ask. It means if you can move the pieces, while leaving the intersections alone, any way you wish and it won't create any new figures.
I'll start you out with an example:
I'll just tell you there are a total of 10. Can you find the other 9? Please, no searching. There are a bunch of YouTube videos on this so it would be too easy to cheat. See if you're smarter than the whole MIT math department *ahem* by solving it yourself in less than two years.
The question for the poll is how many can you get?
Draw all homeomorphically irreducible trees of size n=10.
Here is my attempt to put it in plain simple English.
Using only straight lines, draw all figures where the sum of intersections and dead ends equals 10. You may not have any closed loops. You may also not have two equivalent figures. Any intersection must have at least three paths leading from it.
What do I mean by "equivalent," you might ask. It means if you can move the pieces, while leaving the intersections alone, any way you wish and it won't create any new figures.
I'll start you out with an example:
I'll just tell you there are a total of 10. Can you find the other 9? Please, no searching. There are a bunch of YouTube videos on this so it would be too easy to cheat. See if you're smarter than the whole MIT math department *ahem* by solving it yourself in less than two years.
Be yourself.
The question for the poll is how many can you get?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 11:51:26 AM
permalink
Okay, two people have already voted they don't understand the question. I think asking it is harder than answering it.
If the question were n=8 instead of n=10 then I get four possible answers, which are below. Note the eight red dots in each figure. Does that help?
If the question were n=8 instead of n=10 then I get four possible answers, which are below. Note the eight red dots in each figure. Does that help?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 12:01:52 PM
permalink
MS Paint and about 60 seconds later:
Playing it correctly means you've already won.
August 30th, 2016 at 12:06:46 PM
permalink
Quote: RomesMS Paint and about 60 seconds later:
No. Because you have one point that has only two lines leaving from it. Any point must be an intersection of three or more points or a dead end. In other words, anything but 2.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 12:07:43 PM
permalink
Which point? I only have 3 intersections, and all 3 have 3 lines coming out from the center.
edit: Bottom middle?
edit: Bottom middle?
Playing it correctly means you've already won.
August 30th, 2016 at 2:41:42 PM
permalink
Quote: RomesWhich point? I only have 3 intersections, and all 3 have 3 lines coming out from the center.
edit: Bottom middle?
Yes, it was the bottom middle. However you're new spoiler pattern is good. For the benefit of everybody, we'll call my example pattern #1 and yours #2. Eight more to go.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 2:53:26 PM
permalink
Yeah, I'm one of those that didn't understand. And your n=8 example DOES clear things up.Quote: WizardOkay, two people have already voted they don't understand the question. I think asking it is harder than answering it.
If the question were n=8 instead of n=10 then I get four possible answers, which are below. Note the eight red dots in each figure. Does that help?
I gotta give this some thought.....
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
August 30th, 2016 at 3:04:14 PM
permalink
I need to know more about what "equivalent" means, but I can't look it up because nearly every reference to "homeomorphically irreducible" is to Good Will Hunting. So are the following two figures "equivalent" or not?
Last edited by: unnamed administrator on Apr 4, 2017
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
August 30th, 2016 at 3:08:07 PM
permalink
Quote: MathExtremistSo are the following two figures "equivalent" or not?
[spoiler][/spoiler]
Yes, they are. They call these things trees. In your example you could bend down the middle two branches on the top to the bottom. It would still be the same tree.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 3:11:18 PM
permalink
Quote: MathExtremistI need to know more about what "equivalent" means, but I can't look it up because nearly every reference to "homeomorphically irreducible" is to Good Will Hunting. So are the following two figures "equivalent" or not?
FWIW, as I understand it, your example is the same in both iterations, or equivalent. I could be wrong.
. I don't have a graphic.
1 bar, 2 points. From each end, 4 more bars, like fingers. 10 total points. Same bar, with 3 and 5 bars extending. Same bar, with 2 and 6 points extending.
That's 3 examples, and if the ends were flipped or mirrored, I believe they would be equivalent, so it's only 3.
1 bar, 2 points. From each end, 4 more bars, like fingers. 10 total points. Same bar, with 3 and 5 bars extending. Same bar, with 2 and 6 points extending.
That's 3 examples, and if the ends were flipped or mirrored, I believe they would be equivalent, so it's only 3.
Last edited by: unnamed administrator on Apr 4, 2017
If the House lost every hand, they wouldn't deal the game.
August 30th, 2016 at 3:14:42 PM
permalink
So bit took MIT in the movie 2 years and Romes 20 min. Funny how movies use big words and us lay people think it is actually something hard.
Expect the worst and you will never be disappointed.
I AM NOT PART OF GWAE RADIO SHOW
August 30th, 2016 at 3:32:14 PM
permalink
Quote: MathExtremistSo are the following two figures "equivalent" or not?
Ok, then I'm stuck on 9. I studied graph theory in college and I know about trees, I just don't know what "homeomorphically irreducible" means and I can't look it up without running the risk of having the answer spoon-fed to me.Quote:Yes, they are. They call these things trees. In your example you could bend down the middle two branches on the top to the bottom. It would still be the same tree.
Here's how I got to 9:
The "degree" of a node in a graph (or a tree) is the number of edges emanating from each node. So the example in the first post is a tree with interior (non-leaf) nodes of degrees 3,4,4.
a) We're looking for all trees with total nodes = 10 and no nodes of degree 2. They can either be 1 or >=3.
b) The solutions will have n leaf nodes (of degree 1) and k interior nodes of degree >=3, where n+k = 10.
c) In the degenerate solution of a single interior node and 9 leaves, the single interior node has degree 9.
d) In every other solution with multiple interior nodes, there is at least one edge connecting two interior nodes.
e) The sum of the degrees of the interior nodes double-counts all the shared edges between two interior nodes. Therefore, the sum of the interior node degrees for the (sole) solution with one interior node is 9, the sum of the degrees for solutions with two interior nodes is 10, three interior nodes is 11, etc.
f) Therefore, the problem is sort of related to the number of n-sized compositions of each sum:
1) For a single interior node, the sum is 9 and the single solution is 9
2) For two interior nodes, the sum is 10 and the 2-sized solutions (with minimum degree 3) are 7,3; 6,4; and 5,5
3) For three interior nodes, the sum is 11 and the 3-sized solutions are 3,3,5; 3,4,4; 3,5,3; 4,3,4. The example I posted in my last question was a tree with interior node degrees of 3,5,3. My question was whether the order of the edges coming from those nodes matters; in many data structures and algorithms it does. Here I'm going by your instruction that it doesn't.
4) For four interior nodes, the sum is 12 and the only 4-sized solution is 3,3,3,3.
Anything greater than four interior nodes can't satisfy the condition that all interior nodes have degree >=3 with only 10 total nodes, so 4 is the biggest (or most "spread out") tree that can work.
But that's only 9 distinct trees, I don't know what the last one is. I'm sure I'm missing something obvious though...
a) We're looking for all trees with total nodes = 10 and no nodes of degree 2. They can either be 1 or >=3.
b) The solutions will have n leaf nodes (of degree 1) and k interior nodes of degree >=3, where n+k = 10.
c) In the degenerate solution of a single interior node and 9 leaves, the single interior node has degree 9.
d) In every other solution with multiple interior nodes, there is at least one edge connecting two interior nodes.
e) The sum of the degrees of the interior nodes double-counts all the shared edges between two interior nodes. Therefore, the sum of the interior node degrees for the (sole) solution with one interior node is 9, the sum of the degrees for solutions with two interior nodes is 10, three interior nodes is 11, etc.
f) Therefore, the problem is sort of related to the number of n-sized compositions of each sum:
1) For a single interior node, the sum is 9 and the single solution is 9
2) For two interior nodes, the sum is 10 and the 2-sized solutions (with minimum degree 3) are 7,3; 6,4; and 5,5
3) For three interior nodes, the sum is 11 and the 3-sized solutions are 3,3,5; 3,4,4; 3,5,3; 4,3,4. The example I posted in my last question was a tree with interior node degrees of 3,5,3. My question was whether the order of the edges coming from those nodes matters; in many data structures and algorithms it does. Here I'm going by your instruction that it doesn't.
4) For four interior nodes, the sum is 12 and the only 4-sized solution is 3,3,3,3.
Anything greater than four interior nodes can't satisfy the condition that all interior nodes have degree >=3 with only 10 total nodes, so 4 is the biggest (or most "spread out") tree that can work.
But that's only 9 distinct trees, I don't know what the last one is. I'm sure I'm missing something obvious though...
Last edited by: unnamed administrator on Dec 16, 2016
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
August 30th, 2016 at 3:43:06 PM
permalink
Quote: beachbumbabsFWIW, as I understand it, your example is the same in both iterations, or equivalent. I could be wrong.
Can you elaborate on that? Are you referring to my four example for the n=8 case? If so, which two do you accuse of being equivalent?
Quote:I don't have a graphic.
Can I trouble you to make the diagrams in Paint and then upload them to any file-sharing site?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 4:10:57 PM
permalink
Never mind, I got them all:
The trick for me was to realize that there are multiple orientations of four interior nodes, something that didn't come through when I was writing them down just using numbers. The moral of the story: data representation is everything.
For what it's worth, there's no chance this actually took anyone two years.
The trick for me was to realize that there are multiple orientations of four interior nodes, something that didn't come through when I was writing them down just using numbers. The moral of the story: data representation is everything.
For what it's worth, there's no chance this actually took anyone two years.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
August 30th, 2016 at 5:23:25 PM
permalink
Quote: MathExtremistNever mind, I got them all:
Indeed you did. Congratulations!
Can you elaborate on the "four interior nodes"? I'd like to make an Ask the Wizard question out of this and it would be nice to explain how to arrive at the answer without trial and error.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 6:45:57 PM
permalink
Quote: WizardCan you elaborate on that? Are you referring to my four example for the n=8 case? If so, which two do you accuse of being equivalent?
I was replying to ME, not to you. Yours were good. He had an equivalence in his first post, and you and I answered him at the same time.
Quote:Can I trouble you to make the diagrams in Paint and then upload them to any file-sharing site?
ME has illustrated all three in the middle row of his complete answer, so it would be redundant now. I had the other nine, but can't honestly say I "saw" your original example, so I voted 9 in the poll. For me, your example was the only counter -intuitive one.
If the House lost every hand, they wouldn't deal the game.
August 30th, 2016 at 7:28:42 PM
permalink
"What is the general answer for any n?"
That's what could've made the solution so hard and spoke to Will's genius in the movie-- If I remember the movie, the professor doesn't volunteer the number of trees in the correct solution, so not only did Will have to draw the ten trees but he also had to prove that there are exactly ten and only ten trees in the answer. Drawing the ten trees even when you know there are ten trees is a challenge, but how do you prove that you've got 'em all?
Consider too that formulating an answer for any n is difficult even when you need it to be accurate for trees of size n small; for instance, the number of trees in the solution for size n=3 is zero, because any tree of size 3 would be either i) reducible (if it weren't a triangle) or ii) cyclical (if it were a triangle), both of which are disallowed.
If k were the total number of trees in the solution and n were the size of the trees, then (n,k) would be:
(0,0)
(1,1)
(2,1)
(3,0)
(4,1)
(5,1)
(6,2)
(7,2)
(8,4)
(9,5)
(10,10)
(11,14)
(12,26)
So in other words, what's the function that would generate the series:
(k sub n) = 0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26....
That's what could've made the solution so hard and spoke to Will's genius in the movie-- If I remember the movie, the professor doesn't volunteer the number of trees in the correct solution, so not only did Will have to draw the ten trees but he also had to prove that there are exactly ten and only ten trees in the answer. Drawing the ten trees even when you know there are ten trees is a challenge, but how do you prove that you've got 'em all?
Consider too that formulating an answer for any n is difficult even when you need it to be accurate for trees of size n small; for instance, the number of trees in the solution for size n=3 is zero, because any tree of size 3 would be either i) reducible (if it weren't a triangle) or ii) cyclical (if it were a triangle), both of which are disallowed.
If k were the total number of trees in the solution and n were the size of the trees, then (n,k) would be:
(0,0)
(1,1)
(2,1)
(3,0)
(4,1)
(5,1)
(6,2)
(7,2)
(8,4)
(9,5)
(10,10)
(11,14)
(12,26)
So in other words, what's the function that would generate the series:
(k sub n) = 0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26....
August 30th, 2016 at 7:45:04 PM
permalink
Quote: docbrock"What is the general answer for any n?"...
Thanks, good post. Welcome to the forum. I don't suppose you can provide a formula for the general case of n? Or prove there aren't more than 10 for n=10?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
August 30th, 2016 at 11:08:47 PM
permalink
If there are three or fewer interior nodes, they have to be in a line (or just a dot). But four can start branching -- the two orientations are (a) all four in a line and (b) a T shape. You can't have five interior nodes for n=10 because there aren't enough edges left, but for some other n>10 you will, and with five interior nodes there are three ways to arrange them: a straight line, a big T, and a cross. So the number of solutions for n nodes is going to involve the ordered partition -- if that's the right phrase -- of (# edges + # interior nodes - 1) as well as the number of ways each # of interior nodes can be arranged. From what I've just researched, there's no straightforward formula for that:Quote: WizardIndeed you did. Congratulations!
Can you elaborate on the "four interior nodes"? I'd like to make an Ask the Wizard question out of this and it would be nice to explain how to arrive at the answer without trial and error.
http://oeis.org/A000014
Edit: I think my method of counting the interior degrees leads to a proof that there are no more than 10 solutions for n=10. For interior nodes k < 4, there is only one solution per partition and there are 8 of those. For the one partition with interior nodes k=4 (3,3,3,3), there are only two ways to arrange those. That totals 10. There can't be any others.
Last edited by: MathExtremist on Aug 30, 2016
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
August 31st, 2016 at 9:50:45 PM
permalink
The argument makes intuitive sense and seems to force the conclusion that there are 10 and only 10 qualifying trees of size n=10, so I'd imagine Will could've used that line of reasoning or something like it to know that once he had the 10 trees, he had them all.
The professor in the movie did say that it took the faculty 'two years to prove' the problem, but from the looks of it Will just drew all the trees on the chalkboard; he didn't produce a proof that there were exactly 10 qualifying trees for n=10. So Will could've presumably just concluded that through intuition, if he were capable of that (just as it's intuitive that there are no solutions for n=3 or one solution for n=2), or through a more informal but still complete and valid argument.
The brief research I did also led me back to that same link and I agree, there doesn't seem to be any straightforward formula for any n.
If there isn't one though, I'd like to know how the 'tree counts' that make up the integer series listed on that link (for n=0 through n=39) were calculated, especially the larger ones as n gets closer to 39:
0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981, 21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638, 20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 1464407113
Obviously you can't draw or list every one of the 1464407113 qualifying trees for n=39.
The professor in the movie did say that it took the faculty 'two years to prove' the problem, but from the looks of it Will just drew all the trees on the chalkboard; he didn't produce a proof that there were exactly 10 qualifying trees for n=10. So Will could've presumably just concluded that through intuition, if he were capable of that (just as it's intuitive that there are no solutions for n=3 or one solution for n=2), or through a more informal but still complete and valid argument.
The brief research I did also led me back to that same link and I agree, there doesn't seem to be any straightforward formula for any n.
If there isn't one though, I'd like to know how the 'tree counts' that make up the integer series listed on that link (for n=0 through n=39) were calculated, especially the larger ones as n gets closer to 39:
0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981, 21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638, 20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 1464407113
Obviously you can't draw or list every one of the 1464407113 qualifying trees for n=39.
August 31st, 2016 at 10:34:56 PM
permalink
Quote: docbrockI'd like to know how the 'tree counts' that make up the integer series listed on that link (for n=0 through n=39) were calculated, especially the larger ones as n gets closer to 39:
I'd assume via a computer algorithm. But at the point of n=39, it was breaking the computer's limits.
August 31st, 2016 at 11:36:24 PM
permalink
Quote: tringlomaneI'd assume via a computer algorithm.
Yep, I'd agree. But wouldn't you consider that algorithm to be a formula that could solve for any n? Or would there have to be different algorithms for different ns?
September 1st, 2016 at 8:06:39 AM
permalink
Nope, this work was done long before folks like us could whip out a quick simulation using a high level language on a commodity computer.Quote: tringlomaneI'd assume via a computer algorithm. But at the point of n=39, it was breaking the computer's limits.
See:
http://arxiv.org/pdf/math/0008145.pdf, p. 13, which not only references a 1959 paper by F. Harary and G. Prins on the topic (but which I can't immediately find on the Internet) but points out that a homeomorphically-irreducible tree is the dual of a dissected polygon, and therefore of a cluster of edge-adjacent regular polygons. That's pretty cool:
That means the question on the trees is equivalent to "how many non-equivalent polygon clusters are there that fulfill n = s - k + 2, where s = total number of sides in all polygons and k = total number of polygons." It also means my intuition on the numeric representation (from my post where I set out 9 trees) has a direct geometric analog. It's easy to see how the numeric representation 3,3,3,3 (that is, four triangles) has two unique clusters:
Of course, it means that numeric representation is insufficient and incomplete, but that's a refinement for a later point.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
September 1st, 2016 at 11:13:04 PM
permalink
So it looks as though you're double-counting the shared side of each of the edge-adjacent polygons in determining s for n = s - k +2, correct?
Could you just elaborate a little about how you came up with n = s - k + 2? Particularly, why you're subtracting the total of polygons and the logic behind adding 2, which presumably is a constant for all n?
Could you just elaborate a little about how you came up with n = s - k + 2? Particularly, why you're subtracting the total of polygons and the logic behind adding 2, which presumably is a constant for all n?
September 2nd, 2016 at 7:04:23 AM
permalink
To be honest, I just eyeballed it. But working backwards, the number of total sides of the 1-polygon case is still one fewer than n, so start with s+1. Then summing the sides of any additional polygons will lead to double-counting the shared sides, so you need to subtract those. If there are k polygons, that's k-1 sides to subtract, so s+1-(k-1) = s-k+2.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
September 3rd, 2016 at 9:06:52 AM
permalink
September 3rd, 2016 at 9:28:28 AM
permalink
See this:
http://math.unideb.hu/media/horvath-gabor/publications/gwh2.pdf
See section 5, starting at the bottom of p. 11.
http://math.unideb.hu/media/horvath-gabor/publications/gwh2.pdf
See section 5, starting at the bottom of p. 11.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
September 3rd, 2016 at 10:55:09 AM
permalink
Thanks for showing the 8 result. I could see a pattern and found the first 9 fairly easily and then saw the 10th!
I thought about it differently - consider the problem as a backbone of major roads joining a number of towns and then where each town has some minor road dead-ends. If the town is at the end of the major road it needs two minor road dead-ends, however a town in the middle could have only one minor road dead-end.
1 (i) No major road, one town has nine dead ends.
3 (ii) Major road connects two towns, this leaves 8 dead ends which can be (6-2) (5-3) or (4-4) - i.e. ways to have two integers adding up to 8 where both >=2..
4 (iii) Major road connects three towns. The major road must be A-B-C (as looping isn't allowed). This leaves
7 dead ends where the end towns must have >=2 and the middle >=1. (4-1-2) (3-1-3) (3-2-2) (2-3-2) - i.e. ways to have three integers adding up to 7 where a and c >=2, b >=1.
(iv) Major road connects four towns,
1 (a) Road goes A-B-C-D (i.e. all in long line). Similar logic shows total=6, so only solution is (2 1 1 2)
1 (b) Road goes A-B B-C B-D (i.e. the major road forms a "T" shape). The town in the middle doesn't need any minor roads (although for larger puzzles it could) and the other three are at the end of the road so nead >=2 minor roads. Only solution is A C and D have two minor roads each (2 0 2 2).
(v) Various methods of having major road connecting five towns uses up too many nodes to leave 2 for each end point - so no further solutions.
Hope this logic helps shows the proof. Here's my working with the 10th Eureka solution at the top!
I thought about it differently - consider the problem as a backbone of major roads joining a number of towns and then where each town has some minor road dead-ends. If the town is at the end of the major road it needs two minor road dead-ends, however a town in the middle could have only one minor road dead-end.
1 (i) No major road, one town has nine dead ends.
3 (ii) Major road connects two towns, this leaves 8 dead ends which can be (6-2) (5-3) or (4-4) - i.e. ways to have two integers adding up to 8 where both >=2..
4 (iii) Major road connects three towns. The major road must be A-B-C (as looping isn't allowed). This leaves
7 dead ends where the end towns must have >=2 and the middle >=1. (4-1-2) (3-1-3) (3-2-2) (2-3-2) - i.e. ways to have three integers adding up to 7 where a and c >=2, b >=1.
(iv) Major road connects four towns,
1 (a) Road goes A-B-C-D (i.e. all in long line). Similar logic shows total=6, so only solution is (2 1 1 2)
1 (b) Road goes A-B B-C B-D (i.e. the major road forms a "T" shape). The town in the middle doesn't need any minor roads (although for larger puzzles it could) and the other three are at the end of the road so nead >=2 minor roads. Only solution is A C and D have two minor roads each (2 0 2 2).
(v) Various methods of having major road connecting five towns uses up too many nodes to leave 2 for each end point - so no further solutions.
Hope this logic helps shows the proof. Here's my working with the 10th Eureka solution at the top!
November 1st, 2017 at 8:07:57 PM
permalink
Just to briefly resurrect an old thread, I watched the movie the other day and I went to that page - http://oeis.org/A000014 - because I was reminded of this. If you scroll down a bit, there's a line that says "formula" and then an example to go with it. It's way too complicated for me to comprehend, but maybe some other folks will. It looks like there's also some coding that you can put into Maple to have the program calculate the series for any n >= 0.
Also, I noticed an interesting plot hole - when the professor chases Will away from the chalkboard and then confirms that Will's solution is true, there are only eight trees on the board - not the full ten.
Also, I noticed an interesting plot hole - when the professor chases Will away from the chalkboard and then confirms that Will's solution is true, there are only eight trees on the board - not the full ten.
November 1st, 2017 at 8:44:24 PM
permalink
Quote: docbrockAlso, I noticed an interesting plot hole - when the professor chases Will away from the chalkboard and then confirms that Will's solution is true, there are only eight trees on the board - not the full ten.
That's true. I mention this omission on my page of math problems, problem 220.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 2nd, 2017 at 5:07:46 AM
permalink
Oh WTF THIS IS BULLS***!!!
I was trying it and got 5 of them done. Then I was like, these do seem homeopathically nonreducible or whatever the lingo is, so I figured the 5 I'd done were all the same. I was thinking up a sixth one, and was like F this, these are probably all the same and I'm wasting my time. Then again I don't really know what half those words mean.
Then I google it and realize my first 5 were good and the sixth I was thinking up was there too! That makes me mad, because I see 2 more I know I would have figured out and two that I likely wouldn't have gotten unless I spent more time (and not writing it on the back of an old Palms mailer with a sharpie like the damn hobo that I am).
Edit: apparently i shouldn't post a pic that has my info n stuff on it. From this picture (top left, to right, then middle left to right, etc. numbered, I got:
Thinking of #1, & #2. I wrote out 3, 6, 7, 8, and 10.
1 being top left, 8 being the round ball, 10 being the last one. And 7 is directly above 10.
Lower one on far left I wouldn't have figured out without more time. The one on bottom row, to the left, I wouldn't have done because I'd have thought it was pathomagically unreducibale with #6.
I was trying it and got 5 of them done. Then I was like, these do seem homeopathically nonreducible or whatever the lingo is, so I figured the 5 I'd done were all the same. I was thinking up a sixth one, and was like F this, these are probably all the same and I'm wasting my time. Then again I don't really know what half those words mean.
Then I google it and realize my first 5 were good and the sixth I was thinking up was there too! That makes me mad, because I see 2 more I know I would have figured out and two that I likely wouldn't have gotten unless I spent more time (and not writing it on the back of an old Palms mailer with a sharpie like the damn hobo that I am).
Edit: apparently i shouldn't post a pic that has my info n stuff on it. From this picture (top left, to right, then middle left to right, etc. numbered, I got:
Thinking of #1, & #2. I wrote out 3, 6, 7, 8, and 10.
1 being top left, 8 being the round ball, 10 being the last one. And 7 is directly above 10.
Lower one on far left I wouldn't have figured out without more time. The one on bottom row, to the left, I wouldn't have done because I'd have thought it was pathomagically unreducibale with #6.
Last edited by: RS on Nov 2, 2017
November 2nd, 2017 at 5:17:57 PM
permalink
Quote: WizardThat's true. I mention this omission on my page of math problems, problem 220.
I didn't know this site existed. I have a mathematician friend of mine that would love this -- I'll pass it along to him.
November 2nd, 2017 at 8:48:53 PM
permalink
Quote: docbrockI didn't know this site existed. I have a mathematician friend of mine that would love this -- I'll pass it along to him.
Please do. That is my first web page. Wizard of Odds is actually a spin-off of it, because it originally had so many problems related to probability in casino games.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
