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 ponte1 . 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 9; 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 da 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 precisa 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).
- ↑ PRESSMAN, Ian; SINGMASTER, David. "The Jealous Husbands" and "The Missionaries and Cannibals". The Mathematical Gazette, 73, #464 (Junho 1989), pp. 73–81.. Página visitada em 2010-10-02.
- ↑ 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, http://www.zib.de/Publications/Reports/SC-95-27.ps.Z.
- ↑ Schwartz, Benjamin L. (1961), "An analytic method for the “difficult crossing” puzzles", Mathematics Magazine 34 (4): 187–193, doi:, http://links.jstor.org/sici?sici=0025-570X%28196103%2F04%2934%3A4%3C187%3AAAMFT%22%3E2.0.CO%3B2-1.
- ↑ 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:.
- ↑ Bellman, Richard (1962), "Dynamic programming and “difficult crossing” puzzles", Mathematics Magazine (Mathematical Association of America) 35 (1): 27–29, doi:, http://www.jstor.org/stable/2689096.
