O problema da ponte e da tocha (Também conhecido como O Trem da Meia-Noite^[1] e travessia perigosa^[2]) é 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^[3].

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?^[2]

Uma idéia ó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:

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:

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^[4]. 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^[1].

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^[5][6]. 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^[7].

Este problema tem sido usado como método para comparar a usabilidade de linguagens de programação.^[8]

• Slides sobre o problema
• Artigos discutindo o problema

Referências