Mountain climbing problem
Encyclopedia
In mathematics
, the mountain climbing problem is a problem of finding conditions two function
forming profiles of a two-dimensional
mountain
must satisfy, so that two climbers
can start on the bottom on the opposite sides of the mountain and coordinate their movements to reach to the top while always staying at the same height. This problem was named and posed in this form by James V. Whittaker in 1966, but its history goes back to Tatsuo Homma, who solved a version of it in 1952. The problem has been repeatedly rediscovered and solved independently in different context by a number of people (see the references).
In the past two decades the problem was shown to be connected to the weak Fréchet distance
of curve
s in the plane (see Buchin et al.), various planar motion planning
problems in computational geometry
(see Goodman et al.), the square peg problem (see Pak), semigroup
of polynomial
s (see Baird and Magill), etc. The problem was popularized in the article by Goodman et al., which received the MAA
writing award in 1990.
in n (see Buchin et al.). These difficulties make the problem unintuitive and sometimes rather difficult, both in theory and in practice.
To see heuristically that the result does not extend to all continuous functions, note that if
has a constant interval while 
has a highly oscillating
interval on the same level, then the first climber would be forced to go back and forth infinitely many times, and thus can never reach the top.
It is also known that for the piecewise linear functions there are no obstructions, i.e. the climbers can always coordinate their movements to get to the top (see Whittaker).
of all positions on a mountain both climbers can occupy on the same level. This graph is piecewise linear, i.e. a union of intervals, and can be viewed as a graph
in Graph theory
. Note that
may or may not be connected
. The vertices of the intervals correspond to peaks and valleys of the functions. There are three cases:
In the first case such vertex of
has two adjacent intervals, in the second case it has four, and in the last case zero. Therefore, graph 
has all vertices of even degree, except for the point 
corresponding to two climbers on the bottom and the point 
corresponding to two climbers on top of the mountain. Applying the handshaking lemma
to the connected component
of
containing 
we conclude that 
and 
are in the same connected component of 
. This implies that there is a path
from
to 
in 
. In the language of mountain climbers, this gives a way to coordinate the climbers' movement to reach the top of the mountain.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the mountain climbing problem is a problem of finding conditions two function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
forming profiles of a two-dimensional
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
mountain
Mountain
Image:Himalaya_annotated.jpg|thumb|right|The Himalayan mountain range with Mount Everestrect 58 14 160 49 Chomo Lonzorect 200 28 335 52 Makalurect 378 24 566 45 Mount Everestrect 188 581 920 656 Tibetan Plateaurect 250 406 340 427 Rong River...
must satisfy, so that two climbers
Mountaineering
Mountaineering or mountain climbing is the sport, hobby or profession of hiking, skiing, and climbing mountains. While mountaineering began as attempts to reach the highest point of unclimbed mountains it has branched into specialisations that address different aspects of the mountain and consists...
can start on the bottom on the opposite sides of the mountain and coordinate their movements to reach to the top while always staying at the same height. This problem was named and posed in this form by James V. Whittaker in 1966, but its history goes back to Tatsuo Homma, who solved a version of it in 1952. The problem has been repeatedly rediscovered and solved independently in different context by a number of people (see the references).
In the past two decades the problem was shown to be connected to the weak Fréchet distance
Fréchet distance
In mathematics, the Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves...
of curve
Curve
In mathematics, a curve is, generally speaking, an object similar to a line but which is not required to be straight...
s in the plane (see Buchin et al.), various planar motion planning
Motion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
problems in computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
(see Goodman et al.), the square peg problem (see Pak), semigroup
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation. A semigroup generalizes a monoid in that there might not exist an identity element...
of polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s (see Baird and Magill), etc. The problem was popularized in the article by Goodman et al., which received the MAA
Mathematical Association of America
The Mathematical Association of America is a professional society that focuses on mathematics accessible at the undergraduate level. Members include university, college, and high school teachers; graduate and undergraduate students; pure and applied mathematicians; computer scientists;...
writing award in 1990.
Understanding the problem
It is easy to coordinate the climbers' movement between the peaks and valleys (local maxima and minima of the functions). The difficulty is that to progress, the climbers must occasionally go down the mountain, either one or the other, or both climbers. Similarly, either one or the other climber must backtrack towards the beginning of the journey. In fact, it has been observed that for a mountain with n peaks and valleys the number of turns can be as large as quadraticQuadratic function
A quadratic function, in mathematics, is a polynomial function of the formf=ax^2+bx+c,\quad a \ne 0.The graph of a quadratic function is a parabola whose axis of symmetry is parallel to the y-axis....
in n (see Buchin et al.). These difficulties make the problem unintuitive and sometimes rather difficult, both in theory and in practice.
Formulation
The following result is due to Huneke:- Suppose
and 
are continuous functionContinuous functionIn mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
s from
to 
with 
and 
, and such that neither function is constantConstant functionIn mathematics, a constant function is a function whose values do not vary and thus are constant. For example the function f = 4 is constant since f maps any value to 4...
on an intervalInterval (mathematics)In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
. Then there exist continuous functions
and 
from 
to 
with 
, 
, and such that 
, where "
" stands for a composition of functionsFunction compositionIn mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
.
To see heuristically that the result does not extend to all continuous functions, note that if
has a constant interval while has a highly oscillatingOscillation (mathematics)
In mathematics, oscillation is the behaviour of a sequence of real numbers or a real-valued function, which does not converge, but also does not diverge to +∞ or −∞; that is, oscillation is the failure to have a limit, and is also a quantitative measure for that.Oscillation is defined as the...
interval on the same level, then the first climber would be forced to go back and forth infinitely many times, and thus can never reach the top.
It is also known that for the piecewise linear functions there are no obstructions, i.e. the climbers can always coordinate their movements to get to the top (see Whittaker).
Proof in the piecewise linear case
Consider a graphGraph of a function
In mathematics, the graph of a function f is the collection of all ordered pairs . In particular, if x is a real number, graph means the graphical representation of this collection, in the form of a curve on a Cartesian plane, together with Cartesian axes, etc. Graphing on a Cartesian plane is...
of all positions on a mountain both climbers can occupy on the same level. This graph is piecewise linear, i.e. a union of intervals, and can be viewed as a graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
in Graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Note that
may or may not be connectedConnectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
. The vertices of the intervals correspond to peaks and valleys of the functions. There are three cases:
- 1. One climber is at a peak or a valley, another climber is in between two of them,
- 2. Both climbers are at a peak or at valley.
- 3. One climber is at a peak and one is at valley.
In the first case such vertex of
has two adjacent intervals, in the second case it has four, and in the last case zero. Therefore, graph has all vertices of even degree, except for the point corresponding to two climbers on the bottom and the point corresponding to two climbers on top of the mountain. Applying the handshaking lemmaHandshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree...
to the connected component
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three connected components...
of
containing we conclude that and are in the same connected component of . This implies that there is a pathPath (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
from
to in . In the language of mountain climbers, this gives a way to coordinate the climbers' movement to reach the top of the mountain.External links
- The Parallel Mountain Climbers Problem, a description and a Java appletJava appletA Java applet is an applet delivered to users in the form of Java bytecode. Java applets can run in a Web browser using a Java Virtual Machine , or in Sun's AppletViewer, a stand-alone tool for testing applets...
solution. - MAA Writing Award