Problema do fazendeiro, o lobo, o carneiro e a alface
O problema do fazendeiro, o lobo, o carneiro e a alface (também conhecido com outros nomes variantes como o problema do lobo, da galinha e o saco de milho, o problema da raposa, o ganso, e o saco de feijão, o problema do lobo, a cabra, e o repolho, etc.) é um clássico quebra-cabeça de travessia de rio. Ele remonta pelo menos ao século IX,[1] e entrou para o folclore de uma série de grupos étnicos.[2]
A história[editar | editar código-fonte]
Era uma vez um fazendeiro que foi ao mercado e comprou um lobo, um carneiro e uma alface. No caminho para casa, o fazendeiro chegou à margem de um rio e arrendou um barco. Mas, na travessia do rio por barco, o agricultor poderia levar apenas a si mesmo e uma única de suas compras — o lobo, o carneiro, ou a alface.
Se fossem deixados sozinhos em uma mesma margem, o lobo comeria o carneiro e o carneiro comeria a alface.
O desafio do fazendeiro é atravessar a si mesmo e as suas compras para a margem oposta do rio, deixando cada compra intacta.[3] Como ele fará isso?
Solução[editar | editar código-fonte]
O primeiro passo deve ser atravessar o carneiro para o outro lado do rio, pois qualquer outro resultará no carneiro ou na alface sendo comida. Quando o fazendeiro retorna para o lado original, ele tem a opção de trazer ou o lobo ou a alface. Se ele traz o lobo, ele deve retornar para trazer a alface, resultando na morte do carneiro pelo lobo. Se ele traz a alface, ele terá de voltar e trazer o lobo, o que resulta na alface sendo comida pelo carneiro. Aqui ele tem um dilema, resolvido trazendo-se o lobo (ou a alface) para o outro lado mas trazendo de volta o carneiro. Agora ele pode trazer a alface (ou o lobo) de volta, deixando o carneiro, e, finalmente, retornar para buscar o carneiro completando o transporte de suas compras.
Suas ações na solução são resumidas nas seguintes etapas:
| Viagem nº | Margem de saída | Viagem | Margem de chegada |
|---|---|---|---|
| (início) | fazendeiro lobo carneiro alface | ||
| 1 | lobo alface | fazendeiro carneiro → | |
| 2 | lobo alface | ←fazendeiro | carneiro |
| 3 | alface | fazendeiro lobo → | carneiro |
| 4 | alface | ← fazendeiro carneiro | lobo |
| 5 | carneiro | fazendeiro alface → | lobo |
| 6 | carneiro | ← fazendeiro | lobo alface |
| 7 | fazendeiro carneiro → | lobo alface | |
| (fim) | fazendeiro lobo carneiro alface |
ou, se levando a alface antes do lobo:
| Viagem nº | Margem de saída | Viagem | Margem de chegada |
|---|---|---|---|
| (início) | fazendeiro lobo carneiro alface | ||
| 1 | lobo alface | fazendeiro carneiro → | |
| 2 | lobo alface | ←fazendeiro | carneiro |
| 3 | lobo | fazendeiro alface → | carneiro |
| 4 | lobo | ← fazendeiro carneiro | alface |
| 5 | carneiro | fazendeiro lobo → | alface |
| 6 | carneiro | ← fazendeiro | lobo alface |
| 7 | fazendeiro carneiro → | lobo alface | |
| (fim) | fazendeiro lobo carneiro alface |
Ocorrência e variações[editar | editar código-fonte]
Este quebra-cabeças é um de uma série de quebra-cabeças de travessia de rio, onde o objetivo é mover um conjunto de itens, de uma margem à outra do rio sujeito a uma série de restrições.
Na mais antiga ocorrência conhecida do problema, no manuscrito medieval Propositiones ad Acuendos Juvenes, de Alcuíno de Iorque, os três elementos são um lobo, uma cabra e um repolho. Outras variações cosméticas do quebra-cabeça também existem, como o lobo, uma ovelha e um repolho[4];[2], p. 26; a raposa, uma galinha e grãos,[5] a raposa, um ganso e milho[6] e a pantera, um porco, e mingau.[7] A lógica do jogo, no qual há três elementos, A, B e C, em que nenhum dos A e B nem B e C podem ser deixados juntos, permanece a mesma.
O quebra-cabeças foi encontrado no folclore de afro-americanos, Camarões, as Ilhas de Cabo Verde, Dinamarca, Etiópia, Gana, Itália, Rússia, Roménia, Escócia, Sudão, Uganda, Zâmbia e Zimbabwe[2], pp. 26–27;.[8] Foi dado o número de índice H506.3 no índice de assuntos da literatura popular de Stith Thompson, e o ATU 1579 no sistema de classificação Aarne-Thompson-Uther.[9]
O quebra-cabeças era um dos favoritos de Lewis Carroll,[10] e tem sido reproduzido em várias coleções de matemática recreativa[2], p. 26..
Uma variação do quebra-cabeças também aparece no jogo Nintendo DS, Professor Layton and the Curious Village.
Em algumas partes da África, variações sobre o quebra-cabeça foram encontradas formulando que a embarcação pode transportar dois objetos em vez de apenas um, quando o enigma é enfraquecido. Desta forma, é possível introduzir a restrição adicional de que não há dois itens, incluindo A e C, que podem ser deixados juntos[2], p. 27..
Ver também[editar | editar código-fonte]
Referências
- ↑ PRESSMAN, Ian; SINGMASTER, David (Junho de 1989). «"The Jealous Husbands" and "The Missionaries and Cannibals"». The Mathematical Gazette. 73 (464). The Mathematical Association. pp. 73–81. doi:10.2307/3619658. Consultado em 8 de junho de 2009
- ↑ a b c d e ASCHER, Marcia (Fevereiro de 1990). «A River-Crossing Problem in Cross-Cultural Perspective». Mathematics Magazine. 63 (1). Mathematical Association of America. pp. 26–29. doi:10.2307/2691506. Consultado em 8 de junho de 2009
- ↑ George F., Luger (2004). Inteligência Artificial. Estruturas e Estratégias para a Solução de Problemas Complexos 4ª ed. Porto Alegre: Bookman. pp. 567–572. ISBN 85-363-0396-4
- ↑ Alcuin's Transportation Problems and Integer Programming Arquivado em 19 de julho de 2011, no Wayback Machine.,ketelyn Ralf Borndörfer, Martin Grötschel, and Andreas Löbel, preprint SC-95-27 (November 1995), Konrad-Zuse-Zentrum für Informationstechnik Berlin.
- ↑ «The Classic River Crossing Puzzle». Consultado em 2 de outubro de 2010. Arquivado do original em 17 de junho de 2008
- ↑ Mary Jane Sterling, Math Word Problems for Dummies, P.313
- ↑ Stewart, Ian (1998). The Magical Maze. [S.l.]: Phoenix. ISBN 0753805146
- ↑ 235. Three Zande Texts, E. E. Evans-Pritchard, Man, 62 (October 1962), pp. 149–152.
- ↑ "Carrying a Wolf, a Goat, and a Cabbage across the Stream. Metamorphoses of ATU 1579", Piret Voolaid, Folklore: Electronic Journal of Folklore 35 (2007), pp. 111–130. Tartu: Eesti Kirjandusmuuseum.
- ↑ p. 17, Rediscovered Lewis Carroll Puzzles, Lewis Carroll, compiled by Edward Wakeling, Courier Dover Publications, 1996, ISBN 0486288617.
Ligações externas[editar | editar código-fonte]
- Cabra repolho, e lobo Uma simulação em Java