Wilbert the Wonder Dog

Date: 11/14/2002 at 14:33:56
From: Kristen
Subject: 5 masters/5 dogs need to cross a river

Five masters and their five dogs need to cross a river. There is a 
boat that fits three beings at a time to cross it. Each dog has very 
little training and will bite another human if its master is not 
with it. So you cannot have a dog around other humans without its 
master. But you can have the dog around other dogs without its master. 
In order to cross the river you need to have one human in the boat to 
row, because dogs cannot row. Except for Wilbert the wonder dog. He is 
a special dog and can row the boat. How do you get all the dogs and 
masters across the river without anyone getting bitten?

This problem has been frustrating me for weeks. How I normally start 
is assigning each human and dog a letter. A capitol letter for the 
human and the corresponding lower case letter for the dog. I use the 
letters Aa, Bb, Cc, and Dd. And Ww for Wilbert and his master.
I have tried many different ways but I always end up with someone 
getting bitten. Your help is greatly appreciated! Thank you!

Date: 11/15/2002 at 11:29:06
From: Doctor Ian
Subject: Re: 5 masters/5 dogs need to cross a river

Hi Kristen,

The trick is how to help you solve the problem without giving too much
away, so that's what I'll try to do, by briefly describing the 
subgoals you want to reach, and leaving the steps for you to work out.
Okay? 

1. Have Wilbert take three dogs across, and come back alone. 
   (This will take more than one trip.)
   
2. Send their three owners over, and have one dog-owner pair
   come back.   

Now you have three pairs on the near side, and two pairs on the far 
side. Wilbert and his master are on the near side. That's important. 

3. Exchange Wilbert and his master for one of the other pairs.  

Again, you have three pairs on the near side... and the important
thing is that Wilbert isn't there.  

4. Take the three owners to the far side. 

Now, note that in step 1 you did this:

  ( Ww Aa Bb Cc Dd *| )  --->  ( Ww Aa B C D | b c d )
  
(where *| indicates that the boat is on the near side).  
But you're in the opposite situation now:

  ( b c d |* Ww Aa B C D )
  
So whatever you did before, you just have to undo it now, and 
the problem is solved. 
 
Does this help?  

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/17/2002 at 11:50:23
From: Kristen
Subject: Thank you (5 masters/5 dogs need to cross a river)

Dr. Ian,

Thank you so much for your help. After you started me off and gave me 
those hints I was able to figure it out. I feel much better being able 
to do it now. Thanks so much for all your help; I really appreciate 
it.

Sincerely,
Kristen