Quebra-cabeça de travessia de rio

Um quebra-cabeça de travessia do rio é um tipo de quebra-cabeça de transporte, no qual o objetivo é levar itens de uma margem para outra. A dificuldade do quebra-cabeça surge a partir de restrições sobre quais ou quantos itens podem ser transportados ao mesmo tempo, ou a partir de quais ou quantos itens podem seguramente ser deixados juntos em uma margem.^[1] As definições podem variar cosmeticamente, por exemplo, substituindo o rio por uma ponte^[1]. Os primeiros problemas conhecidos de travessia do rio ocorrem no manuscrito Propositiones ad Acuendos Juvenes, tradicionalmente atribuídos a Alcuíno. Os primeiros exemplares deste manuscrito datam do século IX; Ele contém três problemas de travessia do rio, incluindo o problema do fazendeiro, o lobo, o carneiro e a alface e o problema dos maridos ciumentos.^[2]

Quebra-cabeças de travessia do rio bem conhecidos incluem:

• O problema do fazendeiro, o lobo, o carneiro e a alface em que um fazendeiro deve transportar um lobo, um carneiro e uma alface de um lado para o outro do rio usando um barco que só pode conter um item para além do fazendeiro, sujeito às restrições de que o lobo não pode ser deixado sozinho com o carneiro, e o carneiro e não pode ser deixado sozinho com a alface.
• O problema dos maridos ciumentos, em que três casais devem atravessar um rio com um barco que pode conter no máximo duas pessoas, sujeito a restrição de que nenhuma mulher pode estar na presença de outro homem a não ser que seu marido também esteja presente. Este problema é equivalente ao problema dos canibais e missionários, em que três missionários e três canibais precisam atravessar um rio, com a restrição de que a qualquer momento quando tanto missionários quanto canibais estão em pé em uma das margens, o número de canibais não pode ultrapassar os missionários.
• O problema da ponte e da tocha.
• Propositio de viro et muliere ponderantibus plaustrum. Neste problema, ocorrendo também nas Propositiones ad Acuendos Juvenes, um homem e uma mulher de igual peso, juntamente com dois filhos, cada um com metade de seu peso, querem atravessar um rio com um barco que só pode carregar o peso de um adulto.^[3]

Esses problemas podem ser analisados usando métodos da teoria dos grafos,^[4][5] por programação dinâmica,^[6] ou por programação inteira.^[3]

Referências

1. PETERSON, Ivars (2003). «Tricky crossings». Science News. 164 (24). Consultado em 7 de fevereiro de 2008
2. PRESSMAN, Ian; SINGMASTER, David. «"The Jealous Husbands" and "The Missionaries and Cannibals"». The Mathematical Gazette, 73, #464 (Junho 1989), pp. 73–81. Consultado em 2 de outubro de 2010 !CS1 manut: Nomes múltiplos: lista de autores (link)
3. Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas (1995), Alcuin's Transportation Problems and Integer Programming, Preprint SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin, consultado em 6 de outubro de 2010, cópia arquivada em |arquivourl= requer |arquivodata= (ajuda) 🔗.
4. Schwartz, Benjamin L. (1961), «An analytic method for the "difficult crossing" puzzles», Mathematics Magazine, 34 (4): 187–193, doi:10.2307/2687980.
5. Csorba, Péter; Hurkens, Cor A. J.; Woeginger, Gerhard J. (2008), «The Alcuin number of a graph», Algorithms: ESA 2008, Lecture Notes in Computer Science, 5193, Springer-Verlag, pp. 320–331, doi:10.1007/978-3-540-87744-8_27.
6. Bellman, Richard (1962), «Dynamic programming and "difficult crossing" puzzles», Mathematical Association of America, Mathematics Magazine, 35 (1): 27–29, doi:10.2307/2689096.