Mountain climbing problem

Last updated December 28, 2024

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. It has been shown that when the mountain range has only a finite number of peaks and valleys, it is always possible to coordinate the climbers' movements, but this does not necessarily hold when it has an infinite number of peaks and valleys.

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">Hypercube</span> Convex polytope, the n-dimensional analogue of a square and a cube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube ; the special case for n = 4 is known as a tesseract. It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length. A unit hypercube's longest diagonal in n dimensions is equal to $.$

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

<span class="mw-page-title-main">Tetrakis hexahedron</span> Catalan solid with 24 faces

In geometry, a tetrakis hexahedron is a Catalan solid. Its dual is the truncated octahedron, an Archimedean solid.

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

In graph theory and statistics, a graphon is a symmetric measurable function $, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.$

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 the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

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]