Mountain climbing problem

Last updated December 16, 2023

In mathematics, the mountain climbing problem is a mathematical problem that considers a two-dimensional mountain range (represented as a continuous function), and asks whether it is possible for two mountain climbers starting at sea level on the left and right sides of the mountain to meet at the summit, while maintaining equal altitudes at all times. This problem was named and posed in this form by James V.Whittaker ( 1966 ), but its history goes back to TatsuoHomma ( 1952 ), who solved a version of it. The problem has been repeatedly rediscovered and solved independently in different contexts by a number of people (see references below).

Since the 1990s, the problem was shown to be connected to the weak Fréchet distance of curves in the plane,^[1] various planar motion planning problems in computational geometry,^[2] the inscribed square problem,^[3] semigroup of polynomials,^[4] etc. The problem was popularized in the article by Goodman, Pach & Yap (1989), which received the Mathematical Association of America's Lester R. Ford Award in 1990.^[5]

Analysis

The problem can be rephrased as asking whether, for a given pair of continuous functions $f,g$ with $f(0)=g(0)=0,f(1)=g(1)=1$ (corresponding to rescaled versions of the left and right faces of the mountain), it is possible to find another pair of functions $x_{1},x_{2}$ with $x_{1}(0)=x_{2}(0)=0,x_{1}(1)=x_{2}(1)=1$ (the climbers' horizontal positions at time $t$ ) such that the function compositions $f\circ x_{1}$ and $g\circ x_{2}$ (the climbers' altitudes at time $t$ ) are the same function.

Finite number of peaks and valleys

When $f,g$ have only a finite number of peaks and valleys (local maxima and local minima) it is always possible to coordinate the climbers' movements.^[6] This can be shown by drawing out a sort of game tree: an undirected graph $G$ with one vertex labeled $(x_{1},x_{2})$ whenever $f(x_{1})=g(x_{2})$ and either $f(x_{1})$ or $g(x_{2})$ is a local maximum or minimum. Two vertices will be connected by an edge if and only if one node is immediately reachable from the other; the degree of a vertex will be greater than one only when the climbers have a non-trivial choice to make from that position.

At the vertex $(0,0)$ , the degree is one: the only possible direction for both climbers to go is onto the mountain. Similarly, at $(1,1)$ the degree is one, because both climbers can only return down the mountain.
At a vertex where one climber is at a peak or a valley and the other one is not, then the degree is two: the climber at the peak or valley has two choices of which way to go, and the other climber can only go one way.
At a vertex where both climbers are at peaks or both climbers are at valleys, the degree is four: both climbers may choose independently of each other which direction to go.
At a vertex where one climber is at a peak and the other is at a valley, the degree is zero: such positions are unreachable. (That is, if such a vertex exists, then the graph $G$ is not connected.)

According to the handshaking lemma, every connected component of an undirected graph has an even number of odd-degree vertices. Since the only odd-degree vertices in all of $G$ are $(0,0)$ and $(1,1)$ , these two vertices must belong to the same connected component. That is, $G$ must contain a path from $(0,0)$ to $(1,1)$ . That path tells how to coordinate the climbers' movement to the summit.

It has been observed that for a mountain with $n$ peaks and valleys the length of this path (roughly corresponding to the number of times one or the other climber must "backtrack") can be as large as quadratic in $n$ .^[1]

This technique breaks down when $f,g$ have an infinite number of local extrema. In that case, $G$ would not be a finite graph, so the handshaking lemma would not apply: $(0,0)$ and $(1,1)$ might be connected but only by a path with an infinite number of vertices, possibly taking the climbers "infinite time" to traverse.

Infinite number of peaks and valleys

The following result is due to Huneke (1969):

Suppose

f

and

g

are continuous functions from

[0,1]

to

[0,1]

with

f(0)=g(0)=0

and

f(1)=g(1)=1

, and such that neither function is constant on an interval. Then there exist continuous functions

s

and

t

from

[0,1]

to

[0,1]

with

s(0)=t(0)=0

,

s(1)=t(1)=1

, and such that

f\circ s\,=\,g\circ t

, where "

\circ

" stands for a composition of functions.

On the other hand, it is not possible to extend this result to all continuous functions. For, if $f$ has constant height over an interval while $g$ has infinitely many oscillations passing through the same height, then the first climber may be forced to go back and forth over that interval infinitely many times, making his path to the summit infinitely long.^[6]James V.Whittaker ( 1966 ) gives a concrete example involving $x\sin(x^{-1})$ .^[6]

Notes

1 2 Buchin et al. (2007).
↑ Goodman, Pach & Yap (1989).
↑ Pak (2010).
↑ Baird & Magill (1997).
↑ "Mountain Climbing, Ladder Moving, and the Ring-Width of a Polygon", Writing Awards, Mathematical Association of America, 1990, retrieved 2015-12-19.
1 2 3 Whittaker (1966).

Related Research Articles

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

<span class="mw-page-title-main">Isomorphism</span> In mathematics, invertible homomorphism

In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".

Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory.

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

<span class="mw-page-title-main">Cantor function</span> Continuous function that is not absolutely continuous

In mathematics, the Cantor function is an example of a function that is continuous, but not absolutely continuous. It is a notorious counterexample in analysis, because it challenges naive intuitions about continuity, derivative, and measure. Though it is continuous everywhere and has zero derivative almost everywhere, its value still goes from 0 to 1 as its argument reaches from 0 to 1. Thus, in one sense the function seems very much like a constant one which cannot grow, and in another, it does indeed monotonically grow.

In mathematics, especially representation theory, a quiver is another name for a multidigraph; that is, a directed graph where loops and multiple arrows between two vertices are allowed. Quivers are commonly used in representation theory: a representation $V$ of a quiver assigns a vector space $V (x)$ to each vertex $x$ of the quiver and a linear map $V (a)$ to each arrow $a$ .

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

A hyperbolic sector is a region of the Cartesian plane bounded by a hyperbola and two rays from the origin to it. For example, the two points $(a, 1/ a)$ and $(b, 1/ b)$ on the rectangular hyperbola $xy = 1$ , or the corresponding region when this hyperbola is re-scaled and its orientation is altered by a rotation leaving the center at the origin, as with the unit hyperbola. A hyperbolic sector in standard position has $a = 1$ and $b > 1$ .

In mathematics, bicubic interpolation is an extension of cubic spline interpolation for interpolating data points on a two-dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or nearest-neighbor interpolation. Bicubic interpolation can be accomplished using either Lagrange polynomials, cubic splines, or cubic convolution algorithm.

In mathematics, the Gateaux differential or Gateaux derivative is a generalization of the concept of directional derivative in differential calculus. Named after René Gateaux, a French mathematician who died at age 25 in World War I, it is defined for functions between locally convex topological vector spaces such as Banach spaces. Like the Fréchet derivative on a Banach space, the Gateaux differential is often used to formalize the functional derivative commonly used in the calculus of variations and physics.

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

In mathematics, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties and the global dynamics that result.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.$

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

An infinite-dimensional vector function is a function whose values lie in an infinite-dimensional topological vector space, such as a Hilbert space or a Banach space.

In nonstandard analysis, a discipline within classical mathematics, microcontinuity (or S-continuity) of an internal function f at a point a is defined as follows:

In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or as topological ends of topological spaces associated with the graph.

In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the upper sets of the partial order, and its dimension is the number of elements in the partial order. The order polytope is a distributive polytope, meaning that coordinatewise minima and maxima of pairs of its points remain within the polytope.

References

Baird, B. B.; Magill, K. D. Jr. (1997), "Green's ${\mathcal {R}}$ , ${\mathcal {D}}$ and ${\mathcal {H}}$ relations for generalized polynomials", Semigroup Forum , 55 (3): 267–293, doi:10.1007/PL00005929, MR 1469444, S2CID 120449490 .
Buchin, Kevin; Buchin, Maike; Knauer, Christian; Rote, Günter; Wenk, Carola (2007), "How difficult is it to walk the dog?", Proc. 23rd European Workshop on Computational Geometry (Graz, 2007), pp. 170–173.
Goodman, Jacob E.; Pach, János; Yap, Chee-K. (1989), "Mountain climbing, ladder moving, and the ring-width of a polygon" (PDF), American Mathematical Monthly , 96 (6): 494–510, doi:10.2307/2323971, JSTOR 2323971, MR 0999412 .
Homma, Tatsuo (1952), "A theorem on continuous functions", Kodai Mathematical Seminar Reports, 4: 13–16, doi: 10.2996/kmj/1138843207 , MR 0049988 .
Huneke, John Philip (1969), "Mountain climbing", Transactions of the American Mathematical Society , 139: 383–391, doi: 10.2307/1995331 , JSTOR 1995331, MR 0239013 .
Jiménez López, Víctor (1999), "An elementary solution to the mountain climbers' problem", Aequationes Mathematicae , 57 (1): 45–49, doi:10.1007/s000100050069, MR 1675749, S2CID 121912365 .
Keleti, Tamás (1993), "The mountain climbers' problem", Proceedings of the American Mathematical Society , 117 (1): 89–97, doi:10.2307/2159702, JSTOR 2159702, MR 1123655 .
Lipiński, J. S. (1957), "Sur l'uniformisation des fonctions continues", Bull. Acad. Polon. Sci. Cl. III, 5: 1019–1021, LXXXV, MR 0095224 .
McKiernan, M. A. (1985), "Mountain climbing: an alternate proof", Aequationes Mathematicae , 28 (1–2): 132–134, doi:10.1007/BF02189402, MR 0781218, S2CID 120938782 .
Mioduszewski, J. (1962), "On a quasi-ordering in the class of continuous mappings of a closed interval into itself", Colloquium Mathematicum, 9 (2): 233–240, doi: 10.4064/cm-9-2-233-240 , MR 0143181 .
Pak, Igor (2010), Lectures on Discrete and Polyhedral Geometry, p. 39.
Sikorski, R.; Zarankiewicz, K. (1955), "On uniformization of functions. I", Fundamenta Mathematicae , 41 (2): 339–344, doi: 10.4064/fm-41-2-339-344 , MR 0072465 .
Tucker, Alan (1995), "The parallel climbers puzzle" (PDF), Math Horizons , 3 (2): 22–24, doi:10.1080/10724117.1995.11974954 .
Whittaker, James V. (1966), "A mountain-climbing problem", Canadian Journal of Mathematics , 18: 873–882, doi: 10.4153/CJM-1966-087-x , MR 0196013, S2CID 124117059 ..

External links

The Parallel Mountain Climbers Problem, a description and a Java applet solution.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[FOOTNOTEBuchinBuchinKnauerRote2007-1] 1 2 Buchin et al. (2007).

[FOOTNOTEGoodmanPachYap1989-2] Goodman, Pach & Yap (1989).

[FOOTNOTEPak2010-3] Pak (2010).

[FOOTNOTEBairdMagill1997-4] Baird & Magill (1997).

[5] "Mountain Climbing, Ladder Moving, and the Ring-Width of a Polygon", Writing Awards, Mathematical Association of America, 1990, retrieved 2015-12-19.

[FOOTNOTEWhittaker1966-6] 1 2 3 Whittaker (1966).

[1]

[2]

[3]

[4]

[5]

[6]