En matemáticas , el problema del montañismo es un problema de encontrar las condiciones que deben cumplir dos funciones que forman perfiles de una montaña bidimensional , de modo que dos escaladores puedan empezar en la base de los lados opuestos de la montaña y coordinar sus movimientos para encontrarse (posiblemente en la parte superior) pero siempre a la misma altura. Este problema fue nombrado y planteado de esta forma por James V. Whittaker ( 1966 ), pero su historia se remonta a Tatsuo Homma ( 1952 ), quien resolvió una versión del mismo. Varias personas han redescubierto y resuelto repetidamente el problema de forma independiente en diferentes contextos (véanse las referencias a continuación).
En las últimas dos décadas se demostró que el problema estaba relacionado con la distancia de Fréchet débil de las curvas en el plano, [1] varios problemas de planificación del movimiento plano 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 & Yap (1989) , que recibió el premio Lester R. Ford de la Asociación Matemática de Estados Unidos en 1990. [5]
Entendiendo el problema
Es fácil coordinar el movimiento de los escaladores entre los picos y los valles ( máximos y mínimos locales de las funciones). La dificultad es que para progresar, los escaladores deben bajar ocasionalmente la montaña, ya sea uno u otro, o ambos escaladores. Del mismo modo, uno u otro escalador debe retroceder hacia el comienzo del viaje. De hecho, se ha observado que para una montaña con n picos y valles, el número de vueltas puede ser tan grande como cuadrático en n . [1] Estas complicaciones hacen que el problema sea poco intuitivo y, a veces, bastante difícil, tanto en la teoría como en la práctica.
Formulación
El siguiente resultado se debe a Huneke (1969) :
- Suponer y son funciones continuas de a con y , y tal que ninguna función sea constante en un intervalo . Entonces existen funciones continuas y de a con , , y tal que , dónde " "representa una composición de funciones .
Por otro lado, no es posible extender este resultado a todas las funciones continuas. Por si tiene altura constante durante un intervalo mientras tiene un número infinito de oscilaciones que atraviesan la misma altura, entonces el primer escalador puede verse obligado a ir de un lado a otro infinitas veces y, por lo tanto, nunca llegará a la cima.
Para las funciones lineales por partes no hay obstrucciones. En este caso, los escaladores siempre pueden coordinar sus movimientos para llegar a la cima, independientemente de que existan intervalos de altura constante. [6]
Prueba en el caso lineal por partes
Suponga que ambas funciones son lineales por partes y no tienen intervalos de altura constante.
Considere el conjunto de todos los pares para lo cual un primer escalador en y un segundo escalador en tendrían la misma altura que los demás. Si interpretamos estos pares como las coordenadas cartesianas de puntos en el plano, entonces este conjunto es una unión de segmentos de línea . Puede interpretarse como el dibujo de un gráfico no dirigido. que tiene un vértice en cada punto final o cruce de segmento de línea, y un borde para cada parte de un segmento de línea que conecta dos vértices.
Este gráfico puede estar conectado o no . Tiene vértices de los siguientes tipos:
- En el vértice el grado del vértice (el número de bordes incidentes) es uno: la única dirección posible para que ambos escaladores vayan es hacia la montaña. Del mismo modo, en el grado es uno, porque ambos escaladores solo pueden regresar montaña abajo.
- En un vértice donde ningún escalador está en un pico o en un valle, entonces el grado es dos: solo es posible que ambos escaladores suban o ambos bajen.
- En un vértice donde un escalador está en una cima o un valle y el otro no, entonces el grado es nuevamente dos: el escalador en la cima o valle tiene dos opciones de qué camino tomar, y el otro escalador solo puede ir de una sola mano.
- 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 entre sí qué dirección tomar.
- El conjunto de parejas utilizado para definir el gráfico también puede incluir puntos donde un escalador está en un pico y el otro en un valle. Estos puntos pueden interpretarse como vértices aislados de: ningún escalador puede moverse, por lo que el grado es cero.
Según el lema del protocolo de enlace , cada componente conectado de un gráfico no dirigido tiene un número par de vértices de grado impar. Dado que los únicos vértices de grado impar son y , estos dos vértices deben pertenecer al mismo componente conectado. Es decir, debe haber un camino desde a en . En el lenguaje de los escaladores, esto da una forma de coordinar el movimiento de los escaladores para llegar a la cima de la montaña.
La prueba para funciones que son lineales por partes pero que permiten intervalos de altura constante es similar, pero implica un análisis de caso más complicado. Alternativamente, se puede encontrar una ruta para funciones modificadas en la que todos los intervalos de altura constante se hayan contraído en puntos y luego extender la ruta resultante a las funciones originales.
Notas
- ^ a b Buchin y col. (2007) .
- ^ Goodman, Pach y Yap (1989) .
- ^ Pak (2010) .
- ^ Baird y Magill (1997) .
- ^ "Montañismo, escalera móvil 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.
- ^ 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.
- Buchin, Kevin; Buchin, Maike; Knauer, cristiano; Rote, 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 ; Sí, Chee-K. (1989), "Montañismo, movimiento de escalera y 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", Kōdai Mathematical Seminar Reports , 4 : 13–16, doi : 10.2996 / kmj / 1138843207 , MR 0049988.
- Huneke, John Philip (1969), "Montañismo", 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 escaladores", Aequationes Mathematicae , 57 (1): 45–49, doi : 10.1007 / s000100050069 , MR 1675749.
- Keleti, Tamás (1993), "El problema de los alpinistas", Proceedings of the American Mathematical Society , 117 (1): 89–97, doi : 10.2307 / 2159702 , JSTOR 2159702 , MR 1123655.
- Lipiński, JS (1957), "Sur l'uniformisation des fonctions continúa", Bull. Acad. Polon. Sci. Cl. III , 5 : 1019–1021, LXXXV, MR 0095224.
- McKiernan, MA (1985), "Montañismo: una prueba alternativa", Aequationes Mathematicae , 28 (1-2): 132-134, doi : 10.1007 / BF02189402 , MR 0781218.
- Mioduszewski, J. (1962), "En un cuasi-ordenamiento en la clase de asignaciones 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), Conferencias sobre geometría discreta y poliédrica , 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), "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 montañismo", Canadian Journal of Mathematics , 18 : 873–882, doi : 10.4153 / CJM-1966-087-x , MR 0196013..
enlaces externos
- El problema de los montañistas paralelos , una descripción y una solución de subprograma de Java .