Quebra-cabeça de travessia de rio

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 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

  1. a b PETERSON, Ivars. (2003). "Tricky crossings". Science News 164 (24).
  2. 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.
  3. 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 .
  4. Schwartz, Benjamin L. (1961), "An analytic method for the “difficult crossing” puzzles", Mathematics Magazine 34 (4): 187–193, doi:10.2307/2687980, http://links.jstor.org/sici?sici=0025-570X%28196103%2F04%2934%3A4%3C187%3AAAMFT%22%3E2.0.CO%3B2-1 .
  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", Mathematics Magazine (Mathematical Association of America) 35 (1): 27–29, doi:10.2307/2689096, http://www.jstor.org/stable/2689096 .