The Parallel Climbers Puzzle
fermatslibrary.com
The Parallel Climbers Puzzle
1–10 of 20 posts
Re: The Parallel Climbers Puzzle
#2Ok, so they DID make it to the top, great! Now, how does this help me get better at graph theory?
Edit: That being said, I mean no disrespect to this... 20 year old article. Hope I didn't hurt your feelings, Article. Just trying to find an entry point into this domain.
Re: The Parallel Climbers Puzzle
#3Intuitively the solution kind of makes sense.
M must always be the highest point within the range. A and Z are at the same height and are the lowest point within the range.
Imagine that the hikers are somehow connected (quantum entanglement, etc) such that one cannot physically move up or down if other cannot, and as one moves up and down the other must follow at the same height.
Perhaps a better metaphor would be if the paths are cut into a wall, and you have inserted two pegs that are connected by a horizontal backing bar behind the wall. The bar may move up and down but will always remain horizontal. The pegs can slide left and right along the bar, and up and down along the paths, but must always remain horizontally level.
Now, imagine that whenever a peg reaches a local max or min (peak or valley), a change in vertical direction may also cause a traversal along the opposite size of the peak/valley, thus allowing for forward progression.
While one peg hits a vertical stop and makes horizontal progression, the other peg will simply move up and down along the same segment.
This exercise is obviously not a mathematical proof, but does serve to make the proof feel a bit more intuitive. I'd love to construct such a "puzzle" myself and try it out on a bunch of different contours/tracks.
Re: The Parallel Climbers Puzzle
#4Ok, so they DID make it to the top, great! Now, how does this help me get better at graph theory? Edit: That being said, I mean no disrespect to this... 20 year old article. Hope I didn't hurt your feelings, Article. Just trying to find an entry point into this domain.
Assuming the question is serious I'll attempt an answer. It shows an example of how using graph theory one can solve a problem that seemingly at first has nothing to do with graphs. The proof relies on graph theoretic concepts and understanding the proof helps one get a firmer grasp on these concepts. This particular example and this particular experience may not seem helpful but done often enough you'll end up being good at graph theory.
Re: The Parallel Climbers Puzzle
#5Ok, so they DID make it to the top, great! Now, how does this help me get better at graph theory? Edit: That being said, I mean no disrespect to this... 20 year old article. Hope I didn't hurt your feelings, Article. Just trying to find an entry point into this domain.
Assuming the question is serious I'll attempt an answer. It shows an example of how using graph theory one can solve a problem that seemingly at first has nothing to do with graphs. The proof relies on graph theoretic concepts and understanding the proof helps one get a firmer grasp on these concepts. This particular example and this particular experience may not seem helpful but done often enough you'll end up being…
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?
Re: The Parallel Climbers Puzzle
#6Sorry if OT, but this article hits a pet peeve of mine: unclear examples. In the initial image for the problem, it shows a mountain that is practically symmetrical and thus doesn't convey any of the intuition for why it would be "hard" for the climbers to stay at the same height for the whole trip.
They should have used an illustration where the sides of the mountain were more obviously different.
An example should be chosen to highlight as much variation as possible so the reader can tell what is and isn't essential to the problem.
Re: The Parallel Climbers Puzzle
#7Earlier quoted context omitted.
Assuming the question is serious I'll attempt an answer. It shows an example of how using graph theory one can solve a problem that seemingly at first has nothing to do with graphs. The proof relies on graph theoretic concepts and understanding the proof helps one get a firmer grasp on these concepts. This particular example and this particular experience may not seem helpful but done often enough you'll end up being…
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?
> 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).
Re: The Parallel Climbers Puzzle
#8Sorry if OT, but this article hits a pet peeve of mine: unclear examples. In the initial image for the problem, it shows a mountain that is practically symmetrical and thus doesn't convey any of the intuition for why it would be "hard" for the climbers to stay at the same height for the whole trip. They should have used an illustration where the sides of the mountain were more obviously different. An example should b…
It wouldn't be a puzzle if the range was symmetrical so it is safe to assume it isn't.
Re: The Parallel Climbers Puzzle
#9Earlier quoted context omitted.
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?
> 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).
"Solve lots of math problems"
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?
Re: The Parallel Climbers Puzzle
#10Earlier quoted context omitted.
Assuming the question is serious I'll attempt an answer. It shows an example of how using graph theory one can solve a problem that seemingly at first has nothing to do with graphs. The proof relies on graph theoretic concepts and understanding the proof helps one get a firmer grasp on these concepts. This particular example and this particular experience may not seem helpful but done often enough you'll end up being…
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.