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
- ↑ a b PETERSON, Ivars (2003). «Tricky crossings». Science News. 164 (24). Consultado em 7 de fevereiro de 2008
- ↑ 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
- ↑ a b 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) 🔗. - ↑ Schwartz, Benjamin L. (1961), «An analytic method for the "difficult crossing" puzzles», Mathematics Magazine, 34 (4): 187–193, doi:10.2307/2687980.
- ↑ 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.
- ↑ Bellman, Richard (1962), «Dynamic programming and "difficult crossing" puzzles», Mathematical Association of America, Mathematics Magazine, 35 (1): 27–29, doi:10.2307/2689096.