Hegymászóprobléma

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
Példa a probléma megoldására

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 probléma lényege[szerkesztés]

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.

Precíz megfogalmazás[szerkesztés]

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

Tegyük fel, hogy és folytonos függvények értelmezési tartománnyal és értékkészlettel, ahol és , és egyik függvény sem állandó egyik intervallumon sem. Ekkor létezik az és folytonos függvény, mindkettő értelmezési tartománnyal és értékkészlettel, ahol , , és melyekre , ahol „” 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 egy intervallumon konstans értéket vesz föl, mí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]

A szakaszosan lineáris eset bizonyítása[szerkesztés]

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 páros halmazát, hogy ha az első mászó -ben, a második -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 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 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 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 -t meghatározó 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 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 és az csúcs fokszáma páratlan, ennek a két csúcsnak ugyanabba az összefüggő komponensbe kell tartozniuk. Ezért -ben léteznie kell -ból -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.

Fordítás[szerkesztés]

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.

Jegyzetek[szerkesztés]

További információk[szerkesztés]