Travessias

O lobo a cabra e a couve Ilustração do livro "Problem Solving Through Recreational Mathematics", 1980 Um lobo, uma cabra e uma couve têm de atravessar um rio num barco que transporta um de cada vez, incluindo o barqueiro. Como é que o barqueiro os levará para o outro lado de forma que a cabra não coma a couve e o lobo não coma a cabra?

Como é evidente neste problema, o lobo não pode ser deixado sozinho com a cabra, nem a cabra com a couve.

Ilustração da capa do livro  Introduction to the Design and Analysis of Algorithms de Anany Levitin 

A primeira versão escrita do problema

A primeira versão escrita deste problema é atribuída a Alcuino de York (Problema 18 de Propositiones ad Acuendos Juvenes, século IX). 

Na sua resolução, Alcuino começa por transportar a cabra, depois volta para transportar o lobo para a outra margem, trazendo a cabra de volta, depois leva a couve, voltando por fim para vir buscar a cabra. 

Ilustração do manuscrito Ormesby Psalter do séc. XIII (Oxford, Bodleian Library MS Douce 366, fol. 89r )

O problema na cultura popular

Segundo Marcia Ascher, o problema encontra-se sob a forma de enigma popular em várias culturas: gaulesa, russa, italiana, romana, saxónica, americana, africana. De acordo com cada uma das culturas, as personagens do problema variam.
O problema deve ter chegado à América via Europa , mas neste país as personagens mudam, e o problema aparece da seguinte forma num tratado de aritmética do século XVIII:

A raposa, o ganso e o cesto de milho Um fazendeiro tinha de atravessar o rio com uma raposa, um ganso e um cesto de milho. O seu barco só podia transportar um objecto além do homem. Quantas viagens é que ele fez?

É possível resolver este problema, on-line em:

http://britton.disted.camosun.bc.ca/foxduck/foxduck.htm

Ou fazer o download de um programa, com este problema em:

http://www.delphiforfun.org/Programs/FoxDuckCorn.htm

Marcia Ascher dá-nos conta de várias versões do folclore africano, das personagens da sua história e de outras pequenas alterações, eis alguns exemplos:

   Cabo Verde –as personagens são um lobo, uma cabra e uma couve;       
   Camarões – as personagens são um tigre, um carneiro e uma braçada de junco, o rio é substituído por uma ribeira, e o meio de passagem deixa de ser um barco para passar a ser um tronco de árvore; 

   Argélia – as personagens são um chacal, uma cabra e uma molho de feno, mas neste caso o barco pode transportar dois objectos além do barqueiro; 

  Libéria – as personagens são um leopardo, um bode e um feixe de folhas de mandioca; mas o barco transporta além do barqueiro dois objectos; 

  Zâmbia – os objectos a transportar no barco passam a ser quatro: um leopardo, uma cabra, um rato e um cesto de grãos de kafir; mas o barco só pode transportar um objecto além do barqueiro. Ao aumentar o número de objectos de 3 para 4, o problema torna-se impossível; na tradição oral, o homem acaba por desistir de atravessar o rio; 

  Quénia – a versão é bem diferente das anteriores. Nela três homens casaram recentemente.  Os três casais querem atravessar o rio para ir ao mercado O barco só pode transportar duas pessoas. Mas nenhum dos homens quer deixar a sua mulher com outro homem, nem no barco nem na praia. Todos os homens e mulheres sabem remar.

Puzzle vendido por Rudolf Ackermann em Londres, entre 1798-1826, o envelope continha as figuras do lobo da cabra e da couve e dos três maridos ciumentos e as suas mulheres, assim como o barco.

Ivars Peterson relata a seguinte variante, que aparece na  Rússia, no séc. XX:

Três soldados e dois rapazes Três soldados têm de atravessar um rio que não tem ponte. Dois rapazes concordaram em ajudar os soldados, Mas o barco é tão pequeno que só dá para um soldado ou para os dois rapazes. Um soldado e um rapaz não podem estar no barco ao mesmo tempo. Dado que nenhum dos soldados sabe nadar, parece que nestas circunstâncias apenas um soldado consegue atravessar o rio. No entanto, os três soldados acabam por conseguir atravessar o rio e devolvem o barco aos rapazes. Como é que conseguiram?

Outras versões do problema

A versão popular do Quénia aparece igualmente em Alcuino (problema 17), neste aos três casais recém casados são “substituídos” por 3 pares de irmãos:

Três homens e três irmãs Havia três homens, cada um tendo uma irmã solteira, que precisavam de atravessar um rio. Cada homem desejava as irmãs dos seus amigos. Ao chegar ao rio, encontraram um pequeno barco no qual, de cada vez, só podiam atravessar o rio duas pessoas. Como é que atravessaram o rio, de tal forma que nenhuma das irmãs seja desonrada por um dos homens.

Alcuino fornece igualmente uma versão de um casal: pai e mãe e duas crianças pequenas, no qual o barco só pode levar um adulto ou as duas crianças (problema 19).

O problema com o lobo, a cabra e a couve, aparece posteriormente no manuscrito de Chuquet (1484).  Chuquet resolve de forma semelhante a Alcuino, mas depois de transportar a cabra para a outra margem, volta e transporta a couve, depois traz a cabra de volta e transporta o lobo, por fim vem sozinho para finalmente passar a cabra para a outra margem do rio.

Pacioli em De Viribus (c. de 1500), volta a colocar o problema das três mulheres e dos três maridos ciumentos:

Três mulheres e três maridos ciumentos Três maridos e suas respectivas mulheres devem atravessar um rio numa barca que só transporta no máximo duas pessoas. Os maridos são muito ciumentos, e nenhuma mulher deve ficar com outro homem a não ser na presença do seu marido. Como farão os três casais para atravessarem o rio? Ilustração do problema, num manuscrito italiano do séc. XIV Pacioli coloca o problema para 4 ou 5 casais, mas coloca a condição do barco transportar 3 pessoas a bordo. Esta é a versão de Herny Ernest Dudeney (1857-1930) do problema para cinco casais com a condição de o barco levar 3 pessoas, no contexto de uma inundação: Durante umas inundações cinco casais ficaram cercados por água e tiveram de fugir num barco que só podia transportar três pessoas de cada vez. Cada marido era tão ciumento que  não permitia que a sua mulher estivesse no barco ou em qualquer outro local com outro homem (ou com outros homens) a não ser que ele próprio estivesse presente. Qual é a maneira mais rápida de colocar estes cinco homens e as suas mulheres em segurança?

Tartaglia (1499 – 1557) apresenta o problema para quatro casais, mas mantém a condição de do barco só levar 2 pessoas, o que torna o problema impossível!



Aparentemente a primeira generalização do problema aparece em Bachet de Méziriac (1612):

Três mulheres e três maridos ciumentos (generalização) Um número qualquer n de maridos encontra-se com as suas mulheres para passarem um rio, e avistam um barco sem barqueiro; esse barco não transporta mais do que (n – 1) pessoas. Pergunta-se como é que essas 2n pessoas passarão o rio, de tal forma que nenhuma das mulheres permaneça na companhia de outro homem, ou de outros homens, se o seu marido não estiver presente. Puzzle, feito em madeira,  Bepuzzled, 1997,  Canada

Cadet de Fontanay, em 1879, um jovem aluno do liceu de Montpellier, acrescentou uma ilha ao problema:

A ilha Um número qualquer de maridos, estão com a suas mulheres para atravessar um rio; encontram um barco tão pequeno que, que ele não leva senão duas pessoas. O rio tem uma ilha na qual eles podem descansar. Pergunta-se como é que todas as pessoas atravessam o rio, de tal forma que nenhuma das mulheres fique, seja nas duas margens, no barco ou no rio, na companhia de um ou mais homens, sem que o seu marido esteja presente.

Por sua vez Édouard Lucas (1892), generaliza o problema da seguinte forma:

Um número qualquer n de maridos encontra-se com as suas mulheres para passarem um rio, qual deve ser o número mínimo x de pessoas que um barco pode conter, para efectuar a travessia, sem barqueiro, com a condição que uma mulher não permaneça no barco ou numa das margens do rio na companhia de um ou de vários homens, sem que o seu marido esteja presente.

Muitos outros autores mudaram as personagem ou o contexto do problema ao longo da história.

Joe Jackson (1821) e Mittenzwey (1880), transformam os maridos e as mulheres, em patrões e criados:

Três patrões e três criados  Três patrões e três criados devem atravessar um rio numa barca que pode transportar no máximo duas pessoas. Nenhum dos patrões suporta os serviços dos outros dois criados; de tal forma que se algum deles for deixado com algum dos outros dois criados, infalivelmente o vaiará.

Herny Ernest Dudeney (1857-1930), apresenta a seguinte versão:

O oficial e os seus soldados Durante a debandada turca na Trácia, um pequeno destacamento viu-se confrontado com um largo e fundo rio. No entanto, descobriram um barco com duas crianças a remar. Era tão pequeno que só podia transportar as duas crianças ou um adulto.   Como é que o oficial e os seus 357 soldados atravessaram o rio e deixaram as duas crianças na posse do seu barco? E quantas vezes teve o barco de passar de uma margem para  a outra?

A versão actual mais conhecida do problema é a seguinte:     

Três missionários e três canibais Numa pequena ilha do Pacífico Sul, três missionários e três canibais estão encalhados, numa ilha, com apenas um pequeno barco para chegar a terra firme. Ao planificarem o transporte para terra, os missionários sabem que não podem confiar nos canibais. Por isso, para se salvaguardarem, estabelecem a regra de que os missionários nunca devem estar em menor número do que os canibais, nem na ilha, nem em terra, nem durante o transporte.

Este problema é citado por Vera Sanford  em 1927, pensa-se que tem origem no século XIX! Pode ser resolvido on-line no site:

http://cs.millersville.edu/~webster/mucs.dir/demos/miss.dir/cannibal.html

Boo Boogy Mans um puzzle  comercializado pela Sherms de Connecticut, nos anos 40 do século XX. A caixa contém 6 peças de duas cores diferentes (3 de cada cor), e um pequeno barco. No interior da caixa está desenhado um rio.  

Pesos

Leonardo Scardini, de Curitiba, no Brasil, propõe o seguinte problema que envolve o peso (massa) dos viajantes:

Três homens, pesando 50, 75 e 120 kg querem atravessar um rio, mas o barco que possuem tem capacidade máxima de 150 kg. Como devem proceder para atravessar o rio?

De acordo, com algumas fontes (não muito seguras) as primeiras versões que envolvem pesos devem-se a Tartaglia.

A seguinte versão, com pesos, é de um livro americano de 1905 (Swetz, 2012):

Um homem com a sua mulher e dois filhos pretende atravessar um rio. Têm um barco que apenas transporta 100 libras. O homem pesa 100 libras, a sua mulher pesa 100 libras e cada um dos seus filhos pesa 50 libras. Como podem todos atravessar o rio, utilizando o barco?

O tesouro

Herny Ernest Dudeney (1857-1930), apresenta a seguinte versão, que envolve o transporte de dinheiro:

Três compatriotas encontraram um tesouro, e dividiram-no entre eles: Giles ficou com £ 800,  Jasper com £ 500, e Timothy com £ 300. Voltaram ao rio onde tinham deixado um pequeno barco, mas encontraram uma dificuldade que não tinham previsto. O barco só levava dois homens, ou um homem e um saco , e eles tinham tão pouca confiança uns nos outros que nenhuma deles poderia ser deixado sozinho nem terra ou nem no barco com mais do que a sua parte do tesouro, embora duas pessoas pudessem ficar com mais do as suas partes. Qual é o menor número de vezes em que eles podem atravessar o rio?

Novas versões do problema

Novas versões deste problema podem ser imaginadas por todos.
Esta é a versão apresentada por Ken Johnson e Ted Herr no livro Problem Solving Strategies: Crossing the River with Dogs and Other Mathematical Adventures.

Cinco elementos de uma família e os seus cinco cães (cada elemento da família é dono de um cão), estavam a fazer uma caminhada quando encontraram um rio que tinham de atravessar. Alugaram um barco que apenas transportava três coisas: pessoas ou cães. Infelizmente, os cães eram temperamentais. Cada um deles só se sentia bem com o seu dono e não podia estar ficar com outra pessoa, nem mesmo momentaneamente, a não ser que o seu dono estivesse presente. No entanto, os cães podiam estar perto de outros cães. A travessia teria sido impossível, se não fosse o cão da Lisa ter frequentado uma escola e saber comandar o barco. Mais nenhum cão eram assim tão bem educado.
De que forma é que a travessia do rio foi feita, e quantas viagens é que fizeram?

Alguns leitores deste sítio propuseram novas versões deste problemas, a seguinte curiosamente envolve igualmente cães:

Um grupo de pessoas precisa atravessar um rio em um pequeno barco. Desse grupo fazem parte um agricultor (A), uma ama (B), duas meninas (m1 e m2), dois meninos (g1 e g2), um cachorro (c) e o treinador de cães (T). A travessia tem algumas regras que precisam ser obedecidas: O barquinho só tem 2 lugares e só as pessoas adultas (identificadas com letras maiúsculas) podem operá-lo, ou seja, toda travessia tem que ter pelo menos um adulto. O Agricultor não pode ficar com as meninas sem que a ama esteja por perto. A ama não pode ficar com os meninos sem o agricultor estar por perto. O cachorro morde qualquer pessoa se o treinador não estiver por perto. Tente levar todo o grupo para o outro lado do rio como menor número de viagens possível.

Criação: 04-12-2002   Última atualização: 12-12-2013