5 homens e 5 cachorros (um cachorro para cada homem) saíram para um passeio na fazenda. Eles encontraram um rio, que possuía uma forte correnteza e era fundo. O único artifício disponível para atravessa-lo era um barco abandonado, deixado na margem em que eles estavam. Porém, o barco só suportaria três seres vivos sobre ele. Infelizmente, os cachorros são muito bravos e não podem ficar perto de outra pessoa (nem sequer momentaneamente) sem que o dono esteja perto. Um dos cachorros freqüentou uma escola de obediência altamente avançada e especializada, e, além disso, sabe manejar o barco – os outros cachorros não possuem esta habilidade.
Como os 5 homens e os 5 cachorros poderiam atravessar o rio?
Represente os homens por A, B, C, D, E, e os cachorros por a, b, c, d, e. Considere que o cachorro que sabe manejar o barco seja o cachorro ‘a’.
Assim sendo, ‘a’, ‘b’ e ‘c’ atravessam o rio. ‘a’ volta sozinho e pega o cachorro ‘d’. ‘a’ volta novamente e aguarda enquanto ‘B’, ‘C’ e ‘D’ atravessam o rio. Agora, ‘A’, ‘a’, ‘E’ e ‘e’ estão na margem inicial, e ‘B’, ‘b’, ‘C’, ‘c’, ‘D’, e ‘d’ estão do outro lado. ‘D’ e ‘d’ retornam e ‘A’ e a atravessam. ‘C’ e ‘c’ retornam e ‘C’, ‘D’ e ‘E’ atravessam. Agora, os cachorros ‘c’, ‘d’ e ‘e’ estão na margem inicial e o resto das pessoas e cachorros está do outro lado. ‘a’ volta e leva ‘c’ e ‘d’ para a outra margem. Por fim, ‘a’ volta e leva ‘e’, terminando a travessia.