Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Parallel Climbers Puzzle

fermatslibrary.com

Post reply on HN
Print view View original

11–20 of 20 posts

Re: The Parallel Climbers Puzzle

#11

Post by Jtsummers »

marlag wrote: post #9
wolfgke wrote: post #7

Earlier quoted context omitted.

> 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…

Mathematical Games, by Martin Gardner.

EDIT: Distractions abound so I hit submit before forgetting.

Why: Martin Gardner wrote on a variety of mathematical topics in fields such as geometry, graph theory, number theory, combinatorics, topology, and beyond. His writing is very approachable, and well sourced. This will help to develop a base vocabulary across the mathematical fields that you can use for further research and investigation of your own once you find the areas that interest you, along with being delightful reads just for their own sake for the mentally curious and engaged.

Re: The Parallel Climbers Puzzle

#12

Post by Chinjut »

The author takes care to make the assumption that A and Z are _global_ minima and M is a _global_ maximum. But, in reading the proof, it seems not necessary to make such strong assumptions; would it not work just as well for A and Z to be merely local minima and M to be a local maximum? (For that matter, it should work just as well for A, Z, and M to all merely be local extrema of either sort, so long as A and Z match)

Re: The Parallel Climbers Puzzle

#13

Post by skj »

Chinjut wrote: post #12

The author takes care to make the assumption that A and Z are _global_ minima and M is a _global_ maximum. But, in reading the proof, it seems not necessary to make such strong assumptions; would it not work just as well for A and Z to be merely local minima and M to be a local maximum? (For that matter, it should work just as well for A, Z, and M to all merely be local extrema of either sort, so long as A and Z matc…

If A or Z aren't global minima, there might be a spot between A and M that is lower than all those between Z and M, and therefore no path.

Re: The Parallel Climbers Puzzle

#14

Post by wolfgke »

marlag wrote: post #9
wolfgke wrote: post #7

Earlier quoted context omitted.

> 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…

> how would yo go about gaining in mathematical intuition when you are in your 40ies?

Exactly the same way that you would go if you were in your 20ies: Get the relevant textbooks that are typically recommended by professors and read them (sorry, the textbooks that I can recommend for basic studies in mathematics are all in German (my native language); only for main studies in mathematics I can tell English textbooks).

Re: The Parallel Climbers Puzzle

#15

Post by elbigbad »

SilasX wrote: post #6

Sorry 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…

I didn't get the impression that it was symmetrical from the picture, and I was browsing on a phone. I guess it could have been more clearly marked though. Plus, as the other reply noted, the "problem" wouldn't have been a problem if both sides were symmetrical.

Re: The Parallel Climbers Puzzle

#16

Post by tzs »

Jtsummers wrote: post #10
marlag wrote: post #5

Earlier 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?

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 sol…

> Practice, and read about similar puzzles/problems. Track down reprints/scans of Martin Gardner's Mathematical Games and similar publications.

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...

Re: The Parallel Climbers Puzzle

#17

Post by tgb »

elbigbad wrote: post #15
SilasX wrote: post #6

Sorry 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…

I didn't get the impression that it was symmetrical from the picture, and I was browsing on a phone. I guess it could have been more clearly marked though. Plus, as the other reply noted, the "problem" wouldn't have been a problem if both sides were symmetrical.

I don't think the comment is pointing out the difficulty in telling whether it's meant to be symmetric, it's pointing out that the symmetric case is trivial and so any example should be really different from the symmetric case in order to serve well as an example. It's hard to picture how the climbers might have any difficulty whatsoever when seeing an example that's almost trivial.

Re: The Parallel Climbers Puzzle

#18

Post by kmill »

I spent some time trying to formulate this as an intersection of two regular expressions (the language being composed of sequences of u and d -- given a sequence which goes to the top, you can figure out at least one path which gets you there, and it doesn't matter which you choose)... though it seems much harder to deal with than just saying "the graph is connected because it has exactly two vertices of odd degree."

Re: The Parallel Climbers Puzzle

#19

Post by Jtsummers »

kmill wrote: post #18

I spent some time trying to formulate this as an intersection of two regular expressions (the language being composed of sequences of u and d -- given a sequence which goes to the top, you can figure out at least one path which gets you there, and it doesn't matter which you choose)... though it seems much harder to deal with than just saying "the graph is connected because it has exactly two vertices of odd degree."

Instead of a sequence of u and d, try modeling it as:

Let's go with their ultimate "alphabet", all the pairs based on altitude. (A,Z), ... (M,M). Note all valid transitions. In fact, you have the exact same graph as they do since every transition is reversible. (A,Z) is the starting state, (M,M) is the final state. What you now want is the shortest matching string: AZ.CX.DY.EW.DU.MM. There ought to be only one in this case.

But there are actually 3 possible machines that can be constructed and need to be analyzed if you want to go with this method. C W. The case of C=W is trivial, no intermediate points are introduced. C W is the same as C I think the problem of marking it as a sequence of u and d, you'd need a metric. Some notion of how high or low each peak and valley actually are. Now, this could be discretized based on relative altitudes. Lowest is 0, next is 1, next is 2, etc. So you can ignore precision. Still greatly complicates the matter.

Re: The Parallel Climbers Puzzle

#20

Post by Chinjut »

skj wrote: post #13
Chinjut wrote: post #12

The author takes care to make the assumption that A and Z are _global_ minima and M is a _global_ maximum. But, in reading the proof, it seems not necessary to make such strong assumptions; would it not work just as well for A and Z to be merely local minima and M to be a local maximum? (For that matter, it should work just as well for A, Z, and M to all merely be local extrema of either sort, so long as A and Z matc…

If A or Z aren't global minima, there might be a spot between A and M that is lower than all those between Z and M, and therefore no path.

Yes, I realize now my error: I was reasoning in the degree calculations for the relevant graph as if "local minimum" was synonymous with "valley", and similarly for "local maximum" and "peak", but of course A and Z are examples of local minima that are not typical valleys (having escape routes on only 1 instead of 2 sides), and a similar point applies to M (construed as impassible).

In fairness, the article itself is glib about this important point (it does not discuss the degree calculation for (A, X), (X, Z), (M, X), and (X, M) in general, only for (A, Z) and (M, M) in particular).

Post reply on HN