# Problema da ponte e da tocha

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.