El problema del alpinismo es un problema matemático que considera una cordillera bidimensional (representada como una función continua) y plantea la cuestión de si es posible que dos alpinistas, partiendo desde el nivel del mar en los flancos izquierdo y derecho de la montaña, se encuentren en la cima, manteniendo la misma altitud en todo momento. Se ha demostrado que cuando la cordillera tiene un número finito de picos y valles, siempre es posible coordinar los movimientos de los alpinistas, pero esto no se cumple necesariamente cuando tiene un número infinito de picos y valles.
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.
Sea una cordillera con tres picos y dos valles. Se trazan líneas horizontales por cada pico o valle. Cada escalador parte desde el mar en las posiciones 0. El escalador rojo se mueve por la parte izquierda en el intervalo [0,1] y el escaldor azul se mueve por la parte derecha en el intervalo [1,0].
.Así el rojo está en la posición 2/7 y el verde en la posición 6/7. Al estar el rojo en un pico, el azul puede estar en alguna de las tres posiciones. Los estados vienen dados por el par formado por las posiciones de los escaladores; así la posición de la figura es (2/7,6/7), pero podrían ser los estados (2/7,4/7) y (2/7,2/7). Si el azul baja al valle, el rojo tiene dos opciones como se muestra con trazo grueso.
El ascenso correcto es: el escalador rojo sube al pico (1), luego baja al valle (2), el escalador azul sube al pico (3), luego baja al valle (4) y finalmente ambos, llegan a la cumbre (5).
¿Por qué esa es la ruta correcta?
Para ello establecemos un grafo donde los vértices son los estados posibles y las aristas conectan el paso de un estado a otro. Entonces el camino (línea discontinua) que va desde el vértice de salida (0,0) y termina en el vértice de llegada (1,1) es la ruta correcta. Con trazo rojo se muestran las alternativas del vértice rojo de la figura anterior. Además hay dos estados por los que no se pasa (línea continua).
Las decisiones a tomar según la posición en que se encuentren los escaladores pueden ser:
- En el vértice (0, 0), el grado es uno: la única dirección posible para ambos escaladores es hacia la montaña. De manera similar, en el vértice (1, 1) el grado es uno, ya que ambos escaladores solo pueden regresar montaña abajo.
- En un vértice donde un escalador se encuentra en una cima o un valle y el otro no, el grado es dos: el escalador en la cima o el valle tiene dos opciones sobre qué camino tomar, y el otro escalador solo puede ir por un camino.
- En un vértice donde ambos escaladores se encuentran en una cima o en un valle, el grado es cuatro: ambos escaladores pueden elegir independientemente el uno del otro en qué dirección ir.
- En un vértice donde un escalador se encuentra en una cima y el otro en un valle, el grado es cero: dichas posiciones son inalcanzables. (es decir, si existe tal vértice, entonces el grafo no es conexo).
- Según el 'lema del apretón de manos': la suma de los grados de todos los vértices de un grafo conexo es siempre un número par, lo que significa que el número de personas que saludan un número impar de veces debe ser par (hay un número par de vértices de grado impar).
- Dado que los únicos vértices de grado impar son (0,0) y (1,1), estos dos vértices deben pertenecer a la misma componente conexa. Es decir, el grafo debe contener un camino desde (0,0) hasta (1,1). Este camino indica cómo coordinar el movimiento de los escaladores hacia la cima.
