En un edificio de cinco plantas con un único ascensor con capacidad para dos personas, hay tres personas en cada planta, y todas menos una desean ir a otra planta. El ascensor parte de la planta baja (la 1) y va cargando y descargando personas hasta que todas están donde querían estar, y entonces vuelve a la planta baja. Tomando como unidad la distancia entre dos plantas contiguas, se trata de buscar el recorrido mínimo que permite llevar a cada persona a su destino (lo que equivale a minimizar la distancia recorrida, o el tiempo empleado si la velocidad del ascensor es constante). En el siguiente esquema se indica a qué planta desea ir cada una de las tres personas de cada planta (menos una de la planta 2 que no quiere cambiar):
5: 1-2-3
4: 1-3-5
3: 4-5-5
2: 1-2-4
1: 2-3-4
[spoiler]El ascensor tiene que subir 3 personas de la planta 1 a la 2, esos son 2 subidas de una planta.
Desde la planta 2 a la 3 tienen que subir 3 personas, las que están en la 1 y van a la 2 y la 3 y la que está en la 2 y va a la 4. 2 subidas más.
Desde la planta 3 a la 4 tienen que subir 5 personas, las dos que están en la 3 y van a la 5 y las que van a la 4 y están en la 1, la 2 y la 3. Otras 3 subidas.
Desde la planta 4 a la 5 tienen que subir 3 personas, las que van a la planta 5 y están en las plantas 3 y 4. 2 subidas.
En total son necesarias 9 subidas, por lo que para volver a la planta 1 hay que hacer 9 bajadas.
Es necesario recorrer 18 tramos de ascensor como mínimo. Para ver si es la respuesta se busca una solución con ese número de tramos y si existe será el mínimo:
2 3 4 / 1 2 4 / 4 5 5 / 1 3 5 / 1 2 3
2 / 1 2 4 3 4 / 4 5 5 / 1 3 5 / 1 2 3
2 / 1 2 3 / 4 5 5 4 4 / 1 3 5 / 1 2 3
2 / 1 2 3 / 4 4 4 / 1 3 5 5 5 / 1 2 3
2 / 1 2 3 / 4 4 4 / 1 3 5 / 5 5 1 2 3
2 / 1 2 3 / 4 4 4 / 1 3 5 2 3 / 5 5 1
2 / 1 2 3 / 4 4 4 / 1 2 3 3 / 5 5 5 1
2 / 1 2 3 / 4 4 4 / 1 1 2 3 3 / 5 5 5
2 / 1 2 3 / 3 3 4 4 4 / 1 1 2 / 5 5 5
2 / 1 2 3 / 3 3 4 / 4 4 1 1 2 / 5 5 5
2 / 1 2 3 / 3 3 1 2 4 / 4 4 1 / 5 5 5
2 / 1 2 3 / 3 3 1 2 / 4 4 4 1 / 5 5 5
2 / 1 2 3 / 3 3 1 1 2 / 4 4 4 / 5 5 5
2 / 2 2 1 1 3 / 3 3 1 / 4 4 4 / 5 5 5
2 / 2 2 1 1 / 3 3 3 1 / 4 4 4 / 5 5 5
2 / 2 2 1 1 1 / 3 3 3 / 4 4 4 / 5 5 5
1 1 2 / 2 2 1 / 3 3 3 / 4 4 4 / 5 5 5
1 1 / 2 2 2 1 / 3 3 3 / 4 4 4 / 5 5 5
1 1 1 / 2 2 2 / 3 3 3 / 4 4 4 / 5 5 5 [/spoiler]