Problema 8 · El ascensor extraño
Estrategia en el peor caso: contar viajes imprescindibles.
Respuesta entera de 4 cifras como máximoEn un hotel de 20 plantas los 10 primeros pisos son de color verde, del undécimo al vigésimo son rojos. El hotel no tiene escaleras y para cambiar de piso solo se puede utilizar un ascensor extraño que se comporta así: quien entra al ascensor en un piso verde irá a la planta que pide. Quien entra al ascensor en un piso rojo irá a un piso del mismo color que el que selecciona, pero no necesariamente al piso seleccionado; en cualquier caso, el ascensor cambia de planta. Sea cual sea el piso, si pedimos el ascensor, llegará libre. Una persona ha de visitar todos los pisos, empezando por el primero y volviendo de nuevo al primero. Si el ascensor se comporta en el peor de los casos, ¿cuál es el número mínimo de viajes, viajando dentro del ascensor, que tendrá que hacer para conseguir el objetivo?
Solución razonada
Idea clave: desde un piso verde controlamos perfectamente el destino; desde un piso rojo solo controlamos el color del destino.
Los viajes imprescindibles. Cada piso rojo solo se puede garantizar entrando desde un piso verde (desde un rojo, el ascensor elige). Hacen falta, pues, $10$ viajes verde → rojo, y tras cada uno hay que salir: $10$ viajes más rojo → verde (pidiendo un piso verde; aterrizamos en algún verde). Ya llevamos $20$.
Los pisos verdes. En el peor caso, todas las salidas de los pisos rojos nos dejan en el piso $1$ (o en verdes ya visitados): ningún regalo. Quedan $9$ pisos verdes por visitar ($2$ a $10$), y desde un verde vamos a cada uno con un viaje exacto: $9$ viajes más. La vuelta final al piso $1$ no cuesta ningún viaje extra: ordenamos el recorrido para que la última salida de un piso rojo (que en el peor caso nos lleva al piso $1$, el único «castigo» que el adversario repite) sea el final del trayecto — y si el adversario nos deja en otro verde, es que ese verde nos lo regaló antes, ahorrándonos un viaje que ahora gastamos en volver al $1$.