Problema nº 2: REPARTO A TODO TREN
Giuseppe Peanín, que es el repartidor de la pizzería matelandesa,
tiene que entregar un pedido en una casa en el mínimo tiempo posible.
Armado de paciencia, ha estudiado minuciosamente los semáforos del
barrio y ha descubierto algunas cosas. Los semáforos sólo tienen dos
colores: rojo (no se puede pasar) y verde (sí se puede pasar) que se
alternan cada dos minutos (dos minutos rojo, dos minutos verde, dos
minutos rojo…). Giuseppe tarda 2 minutos y 5 segundos en ir de un
semáforo al siguiente. Si en el momento
que sale de cualquiera de las dos salidas
del aparcamiento, la disposición de los
semáforos se acaba de cambiar a la que
se indica en el dibujo, ¿cuál es la ruta más
rápida para entregar la comida?
Explica razonadamente tu respuesta.
Solución
Menú
Solución:
Para empezar, comprobemos lo que parece evidente: en el trayecto
más rápido el motorista siempre se moverá hacía el Norte o hacía el Este.
Esto se debe a que nunca le conviene dar la vuelta a una o a dos
manzanas para evitar semáforos rojos.
Por ejemplo, si el motorista está situado donde se indica en el dibujo,
podría dar la vuelta a la manzana para evitar el semáforo R del camino
azul.
Sin dar la vuelta tarda de un
semáforo a otro 2 min 5 s, y esperando
al verde 2 min como máximo. En total:
2 (2 m 5 s) + 2 min = 6 min 10 s.
Realmente solamente tendría que esperar 1 m
55 s en el semáforo R.
Dando la vuelta, y suponiendo que
no se tiene que parar, tarda como
mínimo:
4 · (2 m 5 s) = 8 m 20 s
Enunciado
Menú
Solución:
Para empezar, comprobemos lo que parece evidente: en el trayecto
más rápido el motorista siempre se moverá hacía el Norte o hacía el Este.
Esto se debe a que nunca le conviene dar la vuelta a una o a dos
manzanas para evitar semáforos rojos.
Si le da la vuelta a dos manzanas, para evitar dos semáforos R,
seguiría siendo más rápido por más de 10 s.
Sin dar la vuelta tarda como máximo:
3 · (2 m 5 s) + 2 · (2 min) = 10 min 15 s.
Dando la vuelta sin pararse tarda:
5 · (2 m 5 s) = 10 m 25 s
Dar la vuelta a tres manzanas implicaría
en algún momento dar marchar atrás.
Enunciado
Menú
Solución:
Por tanto, el camino más rápido se traza moviéndonos hacía el N o el E.
Así pasaremos por 5 semáforos.
En segundo lugar, observemos qué ocurre cuando sale de un semáforo
donde se ha parado. Por ejemplo, en el que se indica en la figura.
Si el siguiente semáforo también tiene el mismo color. Cuando los dos
semáforos se cambien a V, el motorista
arrancará pero no llegará al 2º semáforo
hasta que se cambie otra vez. Se tendrá
que volver a parar 1 min 55 s.
Sin embargo si el 2º semáforo tiene
distinto color, llegará cuando este en V.
Justamente pasará a los 5 segundos
de haberse puesto en V.
5º
4º
3º
1º
Enunciado
Menú
2º
Solución:
Por tanto, el camino más rápido se traza moviéndonos hacía el N o el E.
Así pasaremos por 5 semáforos.
Con el siguiente semáforo ocurriría lo mismo. Si no se ha parado y el
color es distinto del 2º, lo pasará cuando este tercer semáforo lleve 10 s
en V. Si es del mismo color, se tendría que detener 1 min 50 s.
Si no se para y el 4º semáforo es de
distinto color que el 3º, lo pasará a los 15 s
de ponerse V. Si son del mismo color, se
parará 1 min 45 s.
Y con el quinto pasaría lo mismo.
5º
4º
Deducimos…
3º
1º
Enunciado
Menú
2º
Solución:
El camino más rápido debe tener el mayor número posible de
semáforos consecutivos con distinto color y siempre hacia el N o el E.
Además, mientras más semáforos pase, menos tiempo tiene que
esperar en el siguiente semáforo R.
Utilicemos el diagrama de árbol para buscar el trayecto con menos
semáforos consecutivos del mismo color,
distinguiendo si en cada cruce nos vamos
hacía el N o hacía el E.
5º
Tomaremos el primer cruce hacia el N,
en caso contrario el motorista se detendría
en el primer semáforo.
4º
3º
1º
Enunciado
Menú
2º
Solución:
El camino más rápido debe tener el mayor número posible de semáforos
consecutivos con distinto color y siempre hacía el N o el E.
Además, mientras más semáforos pase, menos tiempo tiene que esperar en
el siguiente semáforo R.
Nº de semáforos
1 1 1 2 3 3 4 3 2
2
consecutivos de igual color
4º
V
V
V
R
V
V
R
V
R
R
R
R
V
R
R
V
R
V
R
V
5º
3º
V
2º
R
1º
R
R
V
R
R
R
R
R
R
Pizzería
Salida Norte
Pizzería
Salida Este
Enunciado
R
V
4º
3º
1º
Menú
2º
Solución:
En los tres primeros recorridos, solamente se tiene que parar una vez,
pero en el que más tarde se para, es en el tercero.
4º
1
1
1
2
3
3
4
3
2
2
V
V
V
R
V
V
R
V
R
R
R
R
V
R
R
V
R
V
R
V
Nº de semáforos
consecutivos de igual color
5º
3º
V
2º
R
1º
R
R
V
R
R
R
R
R
R
Pizzería
Salida Norte
Pizzería
Salida Este
Enunciado
R
V
4º
3º
1º
Menú
2º
Solución:
EL TRAYECTO
MÁS RÁPIDO ES
EL SEÑALADO EN
EL PLANO
HEMOS ENCONTRADO LA SOLUCIÓN...
… pero ¿habrá más formas de encontrarla?
Y ¿qué pasaría si el motorista no sale a la
misma vez que se cambian los semáforos?
Enunciado
Menú
Descargar

Diapositiva 1