Farmer Crossing a River

Date: 09/24/2001 at 02:50:17
From: Bobby 
Subject: The River Problem

A farmer is taking his prize lettuce, lion, llama, and pet leviathan 
(a unique creature that eats llamas and lions unless a lettuce is 
present) to market. A boat awaits him to cross a river, but he can 
only take one item at a time. How can the farmer cross the river, 
without the llama eating the lettuce, the lion eating the llama, and 
the leviathan eating the llama and the lion?

Date: 09/24/2001 at 13:43:33
From: Doctor Ian
Subject: Re: The River Problem

Hi Bobby,

We begin with everything on one side of the river:

  ((far let lio lla lev) ())

The first interior ()'s indicate things on one side of the river, the 
second ()'s indicate things on the other side. 

At the end, we have everything on the other side of the river:

  (() (far let lio lla lev))

We need to connect these two states with a series of transformations, 
each of which involves moving the farmer and zero or on other things 
to the side opposite where he is at the moment.  

For example, here are all the possible transitions from the initial 
state:
                               
  ((far let lio lla lev) ())  
     |
     +->  ((let lio lla lev) (far))     
     |
     +->  ((lio lla lev) (far let))     
     |
     +->  ((let lla lev) (far lio))     
     |
     +->  ((let lio lev) (far lla))     
     |
     +->  ((let lio lla) (far lev))     

Note that some of these states are not legal. For example, if he takes 
the lettuce over, the leviathan is left alone with the lion and the 
llama. In fact, when we look closely, we see that most of the states 
are not legal.

  ((far let lio lla lev) ())  
     |
     +->  ((let lio lla lev) (far))     No: lla eats let
     |
     +->  ((lio lla lev) (far let))     No: lev eats lio, lla
     |
     +->  ((let lla lev) (far lio))     No: lla eats let
     |
     +->  ((let lio lev) (far lla))     Okay
     |
     +->  ((let lio lla) (far lev))     No: lio eats lla

So now we can do the same thing, starting from the only possible 
state:

  ((far let lio lla lev) ())  
     |
     +->  ((let lio lla lev) (far))     No: lla eats let
     |
     +->  ((lio lla lev) (far let))     No: lev eats lio, lla
     |
     +->  ((let lla lev) (far lio))     No: lla eats let
     |
     +->  ((let lio lev) (far lla))     Okay
     |       |
     |       +->  ((let lio lev far) (lla))   Okay. 
     |
     +->  ((let lio lla) (far lev))     No: lio eats lla

Note that we can ignore states that duplicate previous states. (Do you 
see why?) So we don't have to consider the farmer bringing the llama 
back across the river with him. 

You can continue doing this, 

  ((far let lio lla lev) ())  
     |
     +->  ((let lio lla lev) (far))     No: lla eats let
     |
     +->  ((lio lla lev) (far let))     No: lev eats lio, lla
     |
     +->  ((let lla lev) (far lio))     No: lla eats let
     |
     +->  ((let lio lev) (far lla))     Okay
     |       |
     |       +->  ((let lio lev far) (lla))   Okay. 
     |               |
     |               +-> ((lio lev) (far let lla))  No: lev eats lio
     |               |
     |               +-> ((let lev) (far lio lla))  Okay.
     |               |
     |               + ...
     |
     +->  ((let lio lla) (far lev))     No: lio eats lla

and eventually one of two things will happen. Either you'll get to the 
point where _all_ the possible transformations go back to previously 
explored states, in which case no solution is possible. Or you'll find 
that one of the legally reachable states has everything on the other 
side of the river, in which case you've found a solution to the 
problem. 

Note that there may be solutions that involve splitting the lettuce, 
although it's not clear that the person who made up the puzzle would 
accept them.

I hope this helps. Write back if you'd like to talk about this some 
more, or if you have any other questions. 

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