Five men and five dogs (each man owned a dog) went hiking. They encountered a river that was swift and deep. The only way to cross it was an abandoned boat, left ashore on their side. But it would only hold three living things. Unfortunately, the dogs were edgy and could not be near another person (not even momentarily) unless its owner was present. One of the dogs attended a highly advanced, highly specialized obedience school and therefore knew how to operate the boat -- the other dogs lack this skill.

How did the five men and the five dogs cross the river?

Call the man A, B, C, D, and E, and their dogs a, b, c, d, and e. Assume that dog a is the one that knows how to row the boat.

The dogs are okay by themselves, so put some of them across first, then their owners, then bring some dogs back to put all the owners on the 'right' side, and then just use the one 'smart' dog to bring all the dogs back across.

That's the basic method used, and here is the list of crossings (including each intermediate state):


ABCDEabcde
ABCDEde         abc  →
ABCDEde                   abc
ABCDEde     ←  a         bc
ABCDEade                  bc
ABCDEe          ad   →   bc
ABCDEe                    abcd
ABCDEe      ←  a         bcd
ABCDEae                   bcd
AEae            BCD  →   bcd
AEae                      BCDbcd
AEae        ←  Bb        CDcd
ABEabe                    CDcd
BEbe            Aa   →   CDcd
BEbe                      ACDacd
BEbe        ←  Cc        ADad
BCEbce                    ADad
bce             BCE  →   ADad
bce                       ABCDEad
bce         ←  a         ABCDEd
abce                      ABCDEd
e               abc  →   ABCDEd
e                         ABCDEabcd
e           ←  a         ABCDEbcd
ae                        ABCDEbcd
                ae   →   ABCDEbcd
                          ABCDEabcde

Posted by DJ on 2003-09-15 13:35:34