Mountain climbing problem

Mountain climbing problem
Example of the problem resolution.

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 curves 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 polynomials (see Baird and Magill), etc. The problem was popularized in the article by Goodman et al., which received the MAA writing award in 1990.

Contents

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

To see heuristically that the result does not extend to all continuous functions, note that if f has a constant interval while g 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).

Proof in the piecewise linear case

Consider a graph G 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 G may or may not be connected. 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 G has two adjacent intervals, in the second case it has four, and in the last case zero. Therefore, graph G has all vertices of even degree, except for the point (0,0) corresponding to two climbers on the bottom and the point (1,1) corresponding to two climbers on top of the mountain. Applying the handshaking lemma to the connected component of G containing (0,0) we conclude that (0,0) and (1,1) are in the same connected component of G. This implies that there is a path from (0,0) to (1,1) in G. In the language of mountain climbers, this gives a way to coordinate the climbers' movement to reach the top of the mountain.

References

  • Tatsuo Homma, A theorem on continuous functions, Kōdai Math. Semin. Rep. 1952, 13–16.
  • R. Sikorski, K. Zarankiewicz, On uniformization of functions. I. Fundam. Math. 41 (1955), 339–344.
  • J.S. Lipiński, Sur l'uniformisation des fonctions continues, Bull. Acad. Pol. Sci. Cl. III 5 (1957), 1019–1021.
  • Jerzy Mioduszewski, On a quasi-ordering in the class of continuous mappings of closed interval into itself, Colloq. Math. 9 (1962), 233–240.
  • James V. Whittaker, A mountain-climbing problem, Canad. J. Math. 18 (1966), 873–882.
  • John P. Huneke, Mountain climbing, Trans. Amer. Math. Soc. 139 (1969), 383–391.
  • M. A. McKiernan, Mountain climbing: an alternate proof, Aequationes Math. 28 (1985), no. 1–2, 132–134.
  • Jacob E. Goodman, János Pach, Chee-K. Yap, Mountain climbing, ladder moving, and the ring-width of a polygon, Amer. Math. Monthly 96 (1989), no. 6, 494–510.
  • Tamás Keleti, The mountain climbers' problem, Proc. Amer. Math. Soc. 117 (1993), no. 1, 89–97.
  • B.B. Baird, K.D. Magill, Jr., Green's R, D and H relations for generalized polynomials, Semigroup Forum 55 (1997), no. 3, 267–293.
  • Víctor Jiménez López, An elementary solution to the mountain climbers' problem, Aequationes Math. 57 (1999), no. 1, 45–49.
  • Igor Pak, Lectures on Discrete and Polyhedral Geometry, Section 5.
  • Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, and Carola Wenk, How difficult is it to walk the dog?, in Proc. 23rd European Workshop on Computational Geometry (Graz, 2007), pp. 170–173.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Mountain weasel — Conservation status Near Threa …   Wikipedia

  • Mountain Railways of India — Mountain Railways of India * UNESCO World Heritage Site …   Wikipedia

  • Moving sofa problem — The Hammersley sofa has area 2.2074... but is not the largest solution The moving sofa problem was formulated by the Austrian Canadian mathematician Leo Moser in 1966. The problem is a two dimensional idealisation of real life furniture moving… …   Wikipedia

  • Mountain bike — This article is about mountain bikes themselves. For the associated activity, see Mountain biking. A full suspension mountain bike A mountain bike or mountain bicycle (abbreviated MTB or ATB (all terrain bicycle)) is a bicycle created for off… …   Wikipedia

  • Climbing area — A climbing area is a small geographical region with a concentration of opportunities for climbing. The term is most commonly used of rock climbing areas, but there are also ice climbing areas that have the right combination of steepness and water …   Wikipedia

  • mountain — moun|tain [ mauntn ] noun count *** 1. ) a natural structure like a very big hill that is much higher than the usual level of land around it: They went walking and climbing in the mountains. spectacular mountain scenery There was still snow on… …   Usage of the words and phrases in modern English

  • mountain*/*/*/ — [ˈmaʊntɪn] noun [C] 1) a very high hill They went walking and climbing in the mountains.[/ex] There was still snow on the mountain tops.[/ex] 2) a large pile or amount of something a mountain of paperwork[/ex] • make a mountain out of a molehill… …   Dictionary for writing and speaking English

  • Glossary of climbing terms — This page describes terms and jargon related to climbing and mountaineering. Contents: Top · 0–9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipedia

  • Rock climbing — History Styles Technique Equipment and protection Grades (difficulty of climb) Terminology Belaying Abseiling …   Wikipedia

  • Slide Mountain (Ulster County, New York) — Infobox Mountain Name = Slide Mountain Photo = Slide Mountain Catskills.jpg Caption = Slide Mountain from Ashokan High Point Elevation = 4,180 feet (1,277 m) Location = New York, USA Range = Catskills Prominence = 3,300 feet (1005 m) Coordinates …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”