Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

more, or if you have any other questions.

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

Associated Topics:
Middle School Logic
Middle School Puzzles
Middle School Word Problems

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search