### Sample Problem

A man has a boat and three things: a dog, a chicken and a basket of chicken feed. He wants to cross a river, but each time he crosses he can only bring one of his things across. If he leaves the dog and chicken alone, the dog will eat the chicken. If he leaves the chicken and the chicken feed alone, the chicken will eat the feed. What is the least number of one-way trips across the river that the man needs to cross with all of his things intact?

trips

#### Solution

The man can’t leave the chicken alone with the dog or with the feed, so the chicken must be the first thing he takes along with him. After he takes the chicken across the river, he can bring the dog across, but if he left the dog and the chicken alone, the chicken would be eaten so he has to bring the chicken back, leaving the dog alone on the opposite bank. The man can then bring the chicken feed over, leaving it safely with the dog while he makes the final trip back for the chicken.

1. Cross the river with the chicken.

2. Come back alone.

3. Cross the river with the dog.

4. Come back with the chicken.

5. Cross the river with the chicken feed.

6. Come back alone.

7. Cross the river with the chicken.