Siga-nos

Perfil

Expresso

Solução para o problema “Travessia da ponte”

  • 333

Na passada sexta-feira deixámos AQUI um problema. Hoje apresentamos-lhe a solução.

Recordamos o enunciado do problema. Quatro amigos pretendem atravessar uma ponte de madeira. É noite e é por isso indispensável usar uma lanterna na travessia. A ponte pode apenas suportar o peso de duas pessoas e existe apenas uma lanterna. O Pedro demora 10 minutos na travessia da ponte, a Ana demora 5 minutos, o Carlos demora 2 e a Sara 1 minuto. Como devem os quatro amigos organizar as viagens, de modo a atravessarem todos a ponte no mínimo tempo possível?

Este problema foi usado nas entrevistas de emprego da Microsoft. O tempo mínimo para os 4 amigos efectuarem a travessia da ponte é 17 minutos. Diversos leitores apresentaram soluções corretas para este problema. Um modo de organizar as viagens é o seguinte:

- Viagem 1 (ida): Carlos e Sara, 2 minutos;
- Viagem 2 (regresso): Carlos, 2 minutos;
- Viagem 3 (ida): Pedro e Ana, 10 minutos;
- Viagem 4 (regresso): Sara, 1 minuto;
- Viagem 5 (ida): Carlos e Sara, 2 minutos.

Tempo total gasto: 17 minutos

  • O problema desta sexta-feira ficou famoso por ter sido usado nas entrevistas de emprego da Microsoft