O problema da ponte e da tocha (Também conhecido como O Trem da Meia-Noite e travessia perigosa ) é um quebra-cabeças lógico que trata de quatro pessoas, uma ponte e uma tocha. É um dos problemas da categoria dos quebra-cabeças de travessia de rio, onde um número de elementos devem mover-se através de um rio, com algumas restrições .
História Quatro pessoas chegam a um rio no meio da noite. Há uma ponte estreita, mas ela só pode aguentar duas pessoas ao mesmo tempo. Porque é noite, a tocha deve ser usada para atravessar a ponte. A pessoa A pode atravessar a ponte em um minuto, a B em 2 minutos, a C em 5 minutos, e a D em 8 minutos. Quando duas pessoas atravessam a ponte juntos, eles devem se mover no ritmo da pessoa mais lenta. A questão é: todos eles poderão atravessar a ponte em 15 minutos ou menos?
Solução Uma ideia óbvia primeiramente é que o custo de retornar com a tocha para as demais pessoas esperando para atravessar é uma despesa inevitável que deve ser minimizada. Esta estratégia faz de A o candidato a portador da tocha, transportando cada pessoa do outro lado da ponte:
Tempo decorrido Lado inicial Ação Lado final 0 minutos A B C D 2 minutos C D A e B cruzam o rio, levando 2 minutos A B 3 minutos A C D A retorna, levando 1 minuto B 8 minutos D A e C cruzam o rio, levando 5 minutos A B C 9 minutos A D A retorna, gastando 1 minuto B C 17 minutos A e D cruzam o rio, levando 8 minutos A B C D
Essa estratégia não permite uma travessia em 15 minutos. Para encontrar a solução correta, é preciso perceber que forçar os dois mais lentos a atravessar o rio individualmente, desperdiça o tempo que pode ser economizado se ambos cruzarem juntos:
Tempo decorrido Lado inicial Ação Lado final 0 minutos A B C D 2 minutos C D A e B cruzam o rio, gastando 2 minutos A B 3 minutos A C D A retorna, gastando 1 minuto B 11 minutos A C e D cruzam o rio, gastando 8 minutos B C D 13 minutos A B B retorna, gastando 2 minutos C D 15 minutos A e B cruzam o rio, gastando 2 minutos A B C D
Variações e história Existem diversas variações, com variações estéticas, como as pessoas com nomes diferentes, ou variação nos tempos de passagem ou limite de tempo. A tocha em si pode se apagar em um curto espaço de tempo e assim servir de limite de tempo. Em uma variação do chamada O Trem da Meia-Noite, por exemplo, a pessoa D precisa de 10 minutos, em vez de 8 para atravessar a ponte, e as pessoas A, B, C e D, agora chamados de quatro irmãos Gabrianni, têm 17 minutos para pegar o trem da meia-noite.
O quebra-cabeças é conhecido ter aparecido tão cedo quanto 1981, no livro Super Strategies For Puzzles and Games. Nesta versão do quebra-cabeça, A, B, C e D levam 5, 10, 20 e 25 minutos, respectivamente, para cruzar o rio, e o prazo é de 60 minutos. Em todas estas variações, a estrutura e a solução do quebra-cabeças permanece a mesma.
No caso onde há um número arbitrário de pessoas com tempos arbitrários para a travessia, e a capacidade da ponte permanecendo igual a duas pessoas, o problema foi completamente analisado por métodos teoréticos de grafos.
Este problema tem sido usado como método para comparar a usabilidade de linguagens de programação.
Ligações externas Slides sobre o problema Artigos discutindo o problema
Categoria:Quebra-cabeças Categoria:Jogos de lógica