Hegymászóprobléma

A matematikában hegymászóprobléma (mountain climbing problem) alatt azoknak a feltételeknek a megismerését értjük, melyet egy hegy kétdimenziós profiljának két oldalát meghatározó két függvénynek eleget kell tennie ahhoz, hogy két hegymászó a hegy két oldalán a csúcs felé elindulva, mozgásukat koordinálva úgy találkozhassanak (akár a hegy csúcsán), hogy végig azonos magasságon maradnak. A problémát ebben a formában James V. Whittaker (1966) vetette fel, nevét is tőle kapta, de története Tatsuo Homma (1952)-ig nyúlik vissza, aki egy változatát megoldotta. A problémát különböző kontextusokban újra és újra felfedezték és megoldották (ahogy az a jegyzetekben olvasható).

Az 1990-es évektől kezdve előreléptek a probléma megértésében: összekötötték a sík görbéinek gyenge Fréchet-távolságával,^[1] a számítási geometria több mozgástervezési problémájával,^[2] a beírt négyzet problémájával,^[3] polinomok félcsoportjával^[4] stb. A problémát (Goodman, Pach & Yap 1989) cikke ismertette meg a szélesebb matematikakedvelő közönséggel, amiért 1990-ben elnyerték a Mathematical Association of America Lester R. Ford-díját.^[5]

A hegymászók mozgása könnyen koordinálható a csúcsok és völgyek (helyi maximumok és minimumok) között. A nehézséget az adja, hogy a haladáshoz a hegymászóknak időnként lefelé kell indulni a hegyről – néha az egyiknek, néha a másiknak, néha mindkettőnek. Hasonlóan, időről időre a mászók valamelyikének a kiindulási pontja felé vissza kell haladnia. Sőt, mint az megfigyelték, egy n csúccsal és völggyel rendelkező hegynél a visszafordulások száma n-nek akár négyzetes függvénye is lehet.^[1] Ezek a komplikációk a problémát intuitívan kevéssé átláthatóvá és néha egészen bonyolulttá teszik, elméletben és a gyakorlatban is.

(Huneke 1969) a következőt bizonyította:

Tegyük fel, hogy ${\displaystyle f}$ és ${\displaystyle g}$ folytonos függvények ${\displaystyle [0,1]}$ értelmezési tartománnyal és ${\displaystyle [0,1]}$ értékkészlettel, ahol ${\displaystyle f(0)=g(0)=0}$ és ${\displaystyle f(1)=g(1)=1}$, és egyik függvény sem állandó egyik intervallumon sem. Ekkor létezik az ${\displaystyle s}$ és ${\displaystyle t}$ folytonos függvény, mindkettő ${\displaystyle [0,1]}$ értelmezési tartománnyal és ${\displaystyle [0,1]}$ értékkészlettel, ahol ${\displaystyle s(0)=t(0)=0}$, ${\displaystyle s(1)=t(1)=1}$, és melyekre ${\displaystyle f\circ s\,=\,g\circ t}$, ahol „${\displaystyle \circ }$” a függvénykompozíció jelölése.

Másrészről, Huneke eredménye nyilvánvalóan nem általánosítható tetszőleges folytonos függvényre. Ha ugyanis ${\displaystyle f}$ egy intervallumon konstans értéket vesz föl, míg ${\displaystyle g}$ végtelen sokszor oszcillál egy magasság körül, akkor az első mászónak végtelen sokszor kell előre-hátra haladnia, így soha nem érve fel a csúcsra.

A szakaszosan lineáris esetnél nincsenek ilyen korlátozások. Ekkor a hegymászók mindig képesek úgy koordinálni a haladásukat, hogy felérjenek a csúcsra, tekintet nélkül arra, hogy vannak-e konstans magasságú intervallumok.^[6]

Tegyük föl, hogy mindkét függvény szakaszosan lineáris és nem tartalmaznak konstans magasságú intervallumot (fennsíkot).

Vegyük az összes olyan ${\displaystyle (x,y)}$ páros halmazát, hogy ha az első mászó ${\displaystyle x}$-ben, a második ${\displaystyle y}$-ban található, akkor azonos magasságon vannak. Ha ezeket a pontpárokat a sík pontjai Descartes-koordinátaiként értelmezzük, akkor a halmaz szakaszok uniójából áll. Felfogható egy olyan ${\displaystyle G}$ irányítatlan gráf lerajzolásaként, melynek minden csúcsa egy szakasz végpontjának vagy egy metszéspontnak, az élek pedig két csúcsot összekötő szakasznak felelnek meg.

Ez a gráf nem feltétlenül összefüggő. Különböző fajta csúcsai lehetnek:

• A ${\displaystyle (0,0)}$ csúcs fokszáma (az illeszkedő élek száma) egy: a két mászó csak egy irányba indulhat, fölfelé. Hasonlóan, az ${\displaystyle (1,1)}$ helyen a fokszám egy, mivel a mászók csak lefelé mehetnek.
• Ahol egyik mászó sincs se völgyben, se hegycsúcson, a fokszám kettő: elindulhatnak mindketten lefelé, vagy mindketten fölfelé.
• Ha az egyik mászó hegycsúcson vagy völgyben van, a másik pedig nem, a fokszám megintcsak kettő: a hegycsúcson vagy völgyben lévő mászó csak egyetlen irányba indulhat, a másiknak pedig követnie kell őt.
• Ahol mindkét mászó hegycsúcson van, vagy mindkét mászó völgyben, négy a fokszám: mindkét mászó egymástól függetlenül eldöntheti, merre induljon.
• A ${\displaystyle G}$-t meghatározó ${\displaystyle (x,y)}$ csúcspárok között előfordulhatnak olyanok, ahol az egyik mászó hegycsúcson, a másik völgyben van. Ezek a pontok a ${\displaystyle G}$ izolált csúcsaiként értelmezhetők: egyik mászó sem tud mozdulni, a fokszám tehát nulla.

A kézfogás-lemma szerint egy irányítatlan gráf minden összefüggő komponense páros számú páratlan fokszámú csúcsot tartalmaz. Mivel kizárólag a ${\displaystyle (0,0)}$ és az ${\displaystyle (1,1)}$ csúcs fokszáma páratlan, ennek a két csúcsnak ugyanabba az összefüggő komponensbe kell tartozniuk. Ezért ${\displaystyle G}$-ben léteznie kell ${\displaystyle (0,0)}$-ból ${\displaystyle (1,1)}$-be vezető útnak. Hegymászónyelvre lefordítva, a gráfban ez az út megmutatja, hogyan koordinálhatják a mászók mozgásukat a hegycsúcsig.

A szakaszonként lineáris, de fennsíkokat (konstans magasságú intervallumot) is tartalmazó eset bizonyítása a fentihez hasonló, de kissé bonyolultabb esetvizsgálatot tartalmaz. Alternatívaként előállítható az olyan módosított függvényekhez tartozó út, melyben az állandó magasságú intervallumok egy-egy pontba sűrűsödnek, majd ez az út kiterjeszthető az eredeti függvényekre.

Ez a szócikk részben vagy egészben a Mountain climbing problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• Baird, B. B. & Magill, K. D., Jr. (1997), "Green's ${\displaystyle {\mathcal {R}}}$, ${\displaystyle {\mathcal {D}}}$ and ${\displaystyle {\mathcal {H}}}$ relations for generalized polynomials", Semigroup Forum 55 (3): 267–293, DOI 10.1007/PL00005929.
• Buchin, Kevin; Buchin, Maike & Knauer, Christian et al. (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", American Mathematical Monthly 96 (6): 494–510, doi:10.2307/2323971, <http://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Goodman-Pach-Yap494-510.pdf>.
• Homma, Tatsuo (1952), "A theorem on continuous functions", Kōdai Mathematical Seminar Reports 4: 13–16, DOI 10.2996/kmj/1138843207.
• Huneke, John Philip (1969), "Mountain climbing", Transactions of the American Mathematical Society 139: 383–391, DOI 10.2307/1995331.
• 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.
• Keleti, Tamás (1993), "The mountain climbers' problem", Proceedings of the American Mathematical Society 117 (1): 89–97, DOI 10.2307/2159702.
• Lipiński, J. S. (1957), "Sur l'uniformisation des fonctions continues", Bull. Acad. Polon. Sci. Cl. III 5: 1019–1021, LXXXV.
• McKiernan, M. A. (1985), "Mountain climbing: an alternate proof", Aequationes Mathematicae 28 (1-2): 132–134, DOI 10.1007/BF02189402.
• Mioduszewski, J. (1962), "On a quasi-ordering in the class of continuous mappings of a closed interval into itself", Colloquium Mathematicum 9: 233–240.
• Pak, Igor (2010), Lectures on Discrete and Polyhedral Geometry, p. 39, <http://www.math.ucla.edu/~pak/book.htm>.
• Sikorski, R. & Zarankiewicz, K. (1955), "On uniformization of functions. I", Fundamenta Mathematicae 41: 339–344.
• Tucker, Alan (1995), "The parallel climbers puzzle", Math Horizons 3 (2): 22–24, <http://www.maa.org/sites/default/files/pdf/upload_library/22/Evans/november_1995_22.pdf>.
• Whittaker, James V. (1966), "A mountain-climbing problem", Canadian Journal of Mathematics 18: 873–882, DOI 10.4153/CJM-1966-087-x..

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