Problema de escalada de montaña

Problema matemático

Un ejemplo trivial.

En matemáticas , el problema de escalar montañas es un problema matemático que considera una cadena montañosa bidimensional (representada como una función continua ) y pregunta si es posible que dos escaladores de montañas que comienzan a nivel del mar en los lados izquierdo y derecho de la montaña se encuentren en la cumbre, manteniendo altitudes iguales en todo momento. Este problema fue nombrado y planteado en esta forma por James V. Whittaker (1966), pero su historia se remonta a Tatsuo Homma (1952), quien resolvió una versión del mismo. El problema ha sido redescubierto repetidamente y resuelto de forma independiente en diferentes contextos por varias personas (ver referencias a continuación).

Desde la década de 1990, se demostró que el problema estaba conectado con la distancia de Fréchet débil de las curvas en el plano, ^[1] varios problemas de planificación del movimiento planar en geometría computacional , ^[2] el problema del cuadrado inscrito , ^[3] semigrupo de polinomios , ^[4] etc. El problema se popularizó en el artículo de Goodman, Pach y Yap (1989), que recibió el Premio Lester R. Ford de la Asociación Matemática de Estados Unidos en 1990. ^[5]

Análisis

El problema puede reformularse preguntando si, para un par dado de funciones continuas con (correspondientes a versiones reescaladas de las caras izquierda y derecha de la montaña), es posible encontrar otro par de funciones con (las posiciones horizontales de los escaladores en el momento ) tales que las composiciones de funciones y (las altitudes de los escaladores en el momento ) sean la misma función. ${\displaystyle f,g}$ ${\displaystyle f(0)=g(0)=0,f(1)=g(1)=1}$ ${\displaystyle x_{1},x_{2}}$ ${\displaystyle x_{1}(0)=x_{2}(0)=0,x_{1}(1)=x_{2}(1)=1}$ ${\displaystyle t}$ ${\displaystyle f\circ x_{1}}$ ${\displaystyle g\circ x_{2}}$ ${\displaystyle t}$

Número finito de picos y valles

Un ejemplo que requiere volver atrás. La imagen original es un SVG animado; haga clic para verla.

Cuando solo hay un número finito de picos y valles ( máximos locales y mínimos locales ), siempre es posible coordinar los movimientos de los escaladores. ^[6] Esto se puede demostrar dibujando una especie de árbol de juego : un grafo no dirigido con un vértice etiquetado siempre que y o sea un máximo o mínimo local. Dos vértices estarán conectados por una arista si y solo si un nodo es inmediatamente accesible desde el otro; el grado de un vértice será mayor que uno solo cuando los escaladores tengan que hacer una elección no trivial desde esa posición. ${\displaystyle f,g}$ ${\displaystyle G}$ ${\displaystyle (x_{1},x_{2})}$ ${\displaystyle f(x_{1})=g(x_{2})}$ ${\displaystyle f(x_{1})}$ ${\displaystyle g(x_{2})}$

• En el vértice , el grado es uno: la única dirección posible para ambos escaladores es hacia la montaña. De manera similar, en el grado es uno, porque ambos escaladores solo pueden regresar por la montaña. ${\displaystyle (0,0)}$ ${\displaystyle (1,1)}$
• En un vértice donde un escalador está en un pico o un valle y el otro no, entonces el grado es dos: el escalador en el pico o el valle tiene dos opciones de qué camino tomar, y el otro escalador solo puede ir en un camino.
• En un vértice donde ambos escaladores están en picos o ambos escaladores están en valles, el grado es cuatro: ambos escaladores pueden elegir independientemente uno del otro qué dirección ir.
• En un vértice donde un escalador está en un pico y el otro en un valle, el grado es cero: tales posiciones son inalcanzables. (Es decir, si tal vértice existe, entonces el grafo no es conexo ). ${\displaystyle G}$

Según el lema del apretón de manos , cada componente conexo de un grafo no dirigido tiene un número par de vértices de grado impar. Dado que los únicos vértices de grado impar en todos son y , estos dos vértices deben pertenecer al mismo componente conexo. Es decir, deben contener un camino desde hasta . Ese camino indica cómo coordinar el movimiento de los escaladores hacia la cima. ${\displaystyle G}$ ${\displaystyle (0,0)}$ ${\displaystyle (1,1)}$ ${\displaystyle G}$ ${\displaystyle (0,0)}$ ${\displaystyle (1,1)}$

Se ha observado que para una montaña con n picos y valles la longitud de este camino (que corresponde aproximadamente al número de veces que uno u otro escalador debe "retroceder") puede ser tan grande como cuadrática en n . ^[1]

Esta técnica no funciona cuando se tiene un número infinito de extremos locales. En ese caso, no sería un grafo finito, por lo que el lema del apretón de manos no se aplicaría: y podrían estar conectados, pero solo por un camino con un número infinito de vértices, que posiblemente les llevaría a los escaladores "tiempo infinito" recorrer. ${\displaystyle f,g}$ ${\displaystyle G}$ ${\displaystyle (0,0)}$ ${\displaystyle (1,1)}$

Número infinito de picos y valles

El siguiente resultado se debe a Huneke (1969):

Supóngase que y son funciones continuas de hasta con y , y tales que ninguna de las funciones es constante en un intervalo . Entonces existen funciones continuas y de hasta con , , y tales que , donde " " representa una composición de funciones . ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle [0,1]}$ ${\displaystyle [0,1]}$ ${\displaystyle f(0)=g(0)=0}$ ${\displaystyle f(1)=g(1)=1}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle [0,1]}$ ${\displaystyle [0,1]}$ ${\displaystyle s(0)=t(0)=0}$ ${\displaystyle s(1)=t(1)=1}$ ${\displaystyle f\circ s\,=\,g\circ t}$ ${\displaystyle \circ }$

Por otra parte, no es posible extender este resultado a todas las funciones continuas, ya que si tiene una altura constante en un intervalo mientras que tiene infinitas oscilaciones que pasan por la misma altura, entonces el primer escalador puede verse obligado a ir y venir en ese intervalo infinitas veces, haciendo que su camino hacia la cima sea infinitamente largo. ^[6] James V. Whittaker (1966) da un ejemplo concreto que involucra a . ^[6] ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle x\sin(x^{-1})}$

Notas

1. Buchin y col. (2007).
2. Goodman, Pach y Yap (1989).
3. Pak (2010).
4. Baird y Magill (1997).
5. "Escalada de montañas, movimiento de escaleras y el ancho de anillo de un polígono", Premios de escritura , Asociación Matemática de América , 1990 , consultado el 19 de diciembre de 2015.
6. Whittaker (1966).

Referencias

• Baird, BB; Magill, KD Jr. (1997), "Green's , y relaciones para polinomios generalizados", Semigroup Forum , 55 (3): 267–293, doi :10.1007/PL00005929, MR  1469444, S2CID  120449490 ${\displaystyle {\mathcal {R}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {H}}}$.
• Buchin, Kevin; Buchin, Maike ; Knauer, cristiano; De memoria, Günter; Wenk, Carola (2007), "¿Qué tan difícil es pasear al perro?", Proc. 23º Taller europeo sobre geometría computacional (Graz, 2007) , págs. 170-173.
• Goodman, Jacob E. ; Pach, János ; Yap, Chee-K. (1989), "Escalada de montañas, movimiento de escaleras y el ancho de anillo de un polígono" (PDF) , American Mathematical Monthly , 96 (6): 494–510, doi :10.2307/2323971, JSTOR  2323971, MR  0999412.
• Homma, Tatsuo (1952), "Un teorema sobre funciones continuas", Kodai Mathematical Seminar Reports , 4 : 13–16, doi : 10.2996/kmj/1138843207 , MR  0049988.
• Huneke, John Philip (1969), "Escalada de montañas", Transactions of the American Mathematical Society , 139 : 383–391, doi : 10.2307/1995331 , JSTOR  1995331, MR  0239013.
• Jiménez López, Víctor (1999), "Una solución elemental al problema de los alpinistas", Aequationes Mathematicae , 57 (1): 45–49, doi :10.1007/s000100050069, MR  1675749, S2CID  121912365.
• Keleti, Tamás (1993), "El problema de los alpinistas", Actas de la American Mathematical Society , 117 (1): 89–97, doi :10.2307/2159702, JSTOR  2159702, MR  1123655.
• Lipiński, JS (1957), "Sur l'uniformisation des fonctions continue", Bull. Acad. Polon. Ciencia. Cl. III , 5 : 1019–1021, LXXXV, SEÑOR  0095224.
• McKiernan, MA (1985), "Escalada de montañas: una prueba alternativa", Aequationes Mathematicae , 28 (1–2): 132–134, doi :10.1007/BF02189402, MR  0781218, S2CID  120938782.
• Mioduszewski, J. (1962), "Sobre un cuasi-ordenamiento en la clase de aplicaciones continuas de un intervalo cerrado en sí mismo", Colloquium Mathematicum , 9 (2): 233–240, doi : 10.4064/cm-9-2-233-240 , MR  0143181.
• Pak, Igor (2010), Lecciones sobre geometría discreta y poliédrica, pág. 39.
• Sikorski, R.; Zarankiewicz, K. (1955), "Sobre la uniformización de funciones. I", Fundamenta Mathematicae , 41 (2): 339–344, doi : 10.4064/fm-41-2-339-344 , MR  0072465.
• Tucker, Alan (1995), "El rompecabezas de los escaladores paralelos" (PDF) , Math Horizons , 3 (2): 22–24, doi :10.1080/10724117.1995.11974954.
• Whittaker, James V. (1966), "Un problema de escalada de montaña", Revista canadiense de matemáticas , 18 : 873–882, doi : 10.4153/CJM-1966-087-x , MR  0196013, S2CID  124117059..

Enlaces externos

• El problema de los escaladores de montañas paralelas, una descripción y una solución con un applet Java .