Problema da ponte e da tocha
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].
História[editar | editar código-fonte]
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]
Solução[editar | editar código-fonte]
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:
| 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[editar | editar código-fonte]
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]
Ligações externas[editar | editar código-fonte]
Referências
- ↑ a b «MURDEROUS MATHS BRAINBENDERS». Consultado em 8 de fevereiro de 2008
- ↑ a b Gleb Gribakin. «Some simple and not so simple maths problems». Consultado em 8 de fevereiro de 2008
- ↑ PETERSON, Ivars. Science News, 164, #24 (13 de dezembro de 2003) Tricky Crossings http://www.sciencenews.org/articles/20031213/mathtrek.asp Tricky Crossings Verifique valor
|url=(ajuda). Consultado em 7 de fevereiro de 2008 Em falta ou vazio|título=(ajuda) - ↑ «The Bridge Crossing Puzzle». Consultado em 4 de outubro de 2010. Arquivado do original em 31 de maio de 2008
- ↑ SILLKE, Torsten (Setembro de 2001). «Crossing the bridge in an hour». Consultado em 9 de fevereiro de 2008
- ↑ LEVMORE, Saul X.; COOK, Elizabeth Early (1981). Super strategies for puzzles and games. Garden City, New York: Doubleday & Company. ISBN 0-385-17165-X
- ↑ ROTE, Günter (2002). «Crossing the bridge at night» (PDF). Bulletin of the European Association for Theoretical Computer Science. pp. 241–246
- ↑ ERWIG, Martin. «Escape from Zurg» (PDF)