Thx! And I was being serious. For me, one problem of gaining understanding of the domain is, how do I identify that a problem is indeed a graph problem?
Practice, and read about similar puzzles/problems. Track down reprints/scans of Martin Gardner's Mathematical Games and similar publications.
In general, for identifying if something is a graph problem:
1) Through some mapping, (almost?) everything can be transformed into a graph problem of some sort. Now, that's a bit too big a set and ignores the real question.
2) How do I identify that a problem is practically solved with graphs?
Some heuristics (note, these are heuristics, particularly useful for getting started, but not at all absolutes):
Is it discrete? In the given problem from the link we have a finite number of extreme points (ends of each line segment), but an infinite number of points between. Fortunately, thanks to the problem constraint, there are only a few non-endpoints that we are concerned with. So we can safely ignore the infinity of possibilities by only examining this finite set.
Are there transitions between these states that are easily modeled as edges? In the given puzzle, absolutely. And its symmetric so an undirected graph is suitable (sometimes directed graphs would be more suitable or the only applicable solution).
After this, proving various things (like that the generalized statement that all properly constructed puzzles have a solution) will require learning some of the basic properties of graphs, and how to restate the premises (such as constraints on altitude and movement) in a graph-theoretic form. It's easy to intuit the proof now that you have a simplified, but complete, model of the problem, but harder to state it with mathematical certitude. That part really will just require more practice and exposure.
At some point you'll develop sufficient vocabulary in the field that you may not be able to prove it straight off, but you'll know what and where to look for the elements you need to construct a proof like they have.
> how do I identify that a problem is indeed a graph problem?
Mathematical intuition. To answer the next obvious question of how to buld mathematical intuition: Solve lots of math problems (I've also heard that reading "Pólya - How to Solve it" is supposed to be helpful for this; I can't say anything about it).
If you are the type of person that absolutely loved each second of each lecture that your math professor held in high school, where he/she tried to prove an equation on the black board, and you acctually managed to pay attention for long enough to acctually understand what he was talking about, and you got a real kick out of that newly gained intuition, and you now long for that type of "profound" enlightenment, how would yo go about gaining in mathematical intuition when you are in your 40ies?
Jtsummers|9 years ago
In general, for identifying if something is a graph problem:
1) Through some mapping, (almost?) everything can be transformed into a graph problem of some sort. Now, that's a bit too big a set and ignores the real question.
2) How do I identify that a problem is practically solved with graphs?
Some heuristics (note, these are heuristics, particularly useful for getting started, but not at all absolutes):
Is it discrete? In the given problem from the link we have a finite number of extreme points (ends of each line segment), but an infinite number of points between. Fortunately, thanks to the problem constraint, there are only a few non-endpoints that we are concerned with. So we can safely ignore the infinity of possibilities by only examining this finite set.
Are there transitions between these states that are easily modeled as edges? In the given puzzle, absolutely. And its symmetric so an undirected graph is suitable (sometimes directed graphs would be more suitable or the only applicable solution).
After this, proving various things (like that the generalized statement that all properly constructed puzzles have a solution) will require learning some of the basic properties of graphs, and how to restate the premises (such as constraints on altitude and movement) in a graph-theoretic form. It's easy to intuit the proof now that you have a simplified, but complete, model of the problem, but harder to state it with mathematical certitude. That part really will just require more practice and exposure.
At some point you'll develop sufficient vocabulary in the field that you may not be able to prove it straight off, but you'll know what and where to look for the elements you need to construct a proof like they have.
tzs|9 years ago
The entire set of the 15 books that collected his "Mathematical Games" columns from Scientific American are available in PDF form on a CD-ROM:
http://www.amazon.com/Martin-Gardners-Mathematical-Games-Gar...
wolfgke|9 years ago
Mathematical intuition. To answer the next obvious question of how to buld mathematical intuition: Solve lots of math problems (I've also heard that reading "Pólya - How to Solve it" is supposed to be helpful for this; I can't say anything about it).
marlag|9 years ago
If you are the type of person that absolutely loved each second of each lecture that your math professor held in high school, where he/she tried to prove an equation on the black board, and you acctually managed to pay attention for long enough to acctually understand what he was talking about, and you got a real kick out of that newly gained intuition, and you now long for that type of "profound" enlightenment, how would yo go about gaining in mathematical intuition when you are in your 40ies?